Лекция №4 с о р т и р а н е и с м е с в а н е същност на сортирането
Изтегляне 66.88 Kb.
|
- Навигация на страницата:
- А. СОРТИРАНЕ ЧРЕЗ ВМЪКВАНЕ С НАМАЛЯВАЩА СТЪПКА
- Б. СОРТИРАНЕ ПО ДЯЛОВЕ
С О Р Т И Р А Н Е И С М Е С В А Н Е 1. Същност на сортирането СОРТИРАНЕТО е процес на пренареждане на дадено множество от обекти в определен ред. Редът за сортиране обикновено се определя от приет критерий за качеството на сортировката, а крайният резултат от решението на задачата е преадресиране на мястото на обектите в компютъра. При разработката на алгоритми и компютърни програми за сортиране на данни се появява много тясна връзка между избрания МЕТОД за сортиране и СТРУКТУРАТА на данните. Именно това е причината този проблем да бъде в основата на класификацията на методите за сортиране като: СОРТИРАНЕ НА МАСИВИ (т.нар. вътрешно сортиране) или СОРТИРАНЕ НА ПОСЛЕДОВАТЕЛНИ ФАЙЛОВЕ (т.нар. външно сортиране). 2. Сортиране на числови масиви Преди началото на сортирането, ако числовите масиви са многомерни, те трябва да бъдат приведени по определен алгоритъм в редица (вектор-ред или –стълб). Методите за сортиране на числови масиви (множества) могат условно да се класифицират в три главни категории:
2.1. СОРТИРАНЕ ЧРЕЗ ВМЪКВАНЕ СОРТИРАНЕТО ЧРЕЗ ВМЪКВАНЕ се свежда до последователно сравняване на всеки елемент и вмъкването му на подходящо място в редицата по местоназначение на обектите. Този подход е много устойчив и неговата основна слабост е бавния избор на мястото за вмъкване. Различните алгоритми се отличават преди всичко по решенията, които предлагат за решаване на този проблем. СОРТИРАНЕТО ЧРЕЗ ПРЯКО ВМЪКВАНЕ СЕ РЕАЛИЗИРА като елементите в множеството се разделят на две редици: по местозначение А1, А2, ..., Аi-1 и първоначална редица. На всяка стъпка i-тият елемент от първоначалната редица се изважда и се премества в редицата по местозначение, като се вмъква на съответното му място. Например: * Началната стойност на i е 2.
* Процесът на сравнение приключва, когато се открие по-малък или равен елемент или се достигне до левия край на редицата по местоназначение. Забележка: Алгоритъмът за пряко вмъкване лесно може да бъде подобрен, като се има предвид, че редицата по местоназначение е подредена. 2.2. СОРТИРАНЕ ЧРЕЗ СЕЛЕКЦИЯ СОРТИРАНЕТО ЧРЕЗ СЕЛЕКЦИЯ разглежда всички елементи в редицата по местоназначение на обектите и отделя този от тях, който отговаря на приетия критерий за качеството на сортировката. Отделеният елемент се разменя по място с първия (респ. последния) в редицата и се изключва по-нататък от сортировката. Различните алгоритми се отличават по бързината на селекцията (отделянето) на елемента с най-добро качество, подлежащ на поредната размяна. СОРТИРАНЕТО ЧРЕЗ ПРЯКА СЕЛЕКЦИЯ се основава на следните основни принципи: - намира се най-малкият елемент от началните елементи и разменя мястото си с първия елемент; - тази операция се повтаря за останалите N-1 елемнента, докато остане само един елемент (най-големият). Сортирането чрез пряка селекция в известен смисъл е противоположно на сортирането чрез пряко вмъкване. Пряката селекция разглежда всички елементи от първоначалната редица, за да намери такъв с най-малка стойност, който да се постави като следващ елемент в редицата по местоназначение. Докато прякото вмъкване разглежда при всяка стъпка само следващия елемент в първоначалната редица и всички елементи в редицата по местоназначение. 2.3. СОРТИРАНЕ ЧРЕЗ РАЗМЯНА СОРТИРАНЕТО ЧРЕЗ РАЗМЯНА се свежда до последователно сравняване и разменяне на двойки съседни елементи в редицата по местоназначение на обектите. Алгоритмите, използващи този подход, много често включват различни подобрения за повишаване на неговата ефективност. Независимо от това самата РАЗМЯНА НА ДВА ЕЛЕМЕНТА е доста скъпа компютърна операция и всички алгоритми запазват по-ниска ефективност на сортиране от горните два метода. Алгоритъмът за СОРТИРАНЕ ЧРЕЗ ПРЯКА РАЗМЯНА се основава на принципа на сравнение и размяна на двойки от съседни елементи, докато се сортират всички елементи. Както и при метода за сортиране чрез пряка селекция, така и тук се преминава известен брой пъти през масива, като всеки път най-големият елемент се премества в десния край на редицата. Преминаването без размяна означава, че елементите са подредени, т.е. край на сортирането. За целта се използва флаг (променливата F), който се "запалва" само при извършване на размяна при поредното преминаване. Алгоритъмът може да се подобри още, като се запомни мястото (индексът) на последната размяна. След този индекс елементите са в желания ред. Следователно следващото преминаване може да се извърши до този индекс. 2.4. НЯКОИ ПОДОБРЕНИ МЕТОДИ ЗА СОРТИРАНЕ А. СОРТИРАНЕ ЧРЕЗ ВМЪКВАНЕ С НАМАЛЯВАЩА СТЪПКА( МЕТОД НА ШЕЛ ) Подобрение на сортирането чрез пряко вмъкване е предложено от Д. Л. Шел през 1959 г. В този алгоритъм няколко пъти се изпълнява прякото вмъкване като се преминава през елементите с различна и намаляваща стъпка. Кнут показва, че един разумен избор на стъпки е редицата 1 , 4 , 13 , 40 , 121 , ... (използвана в обратен ред). Той също препоръчва редицата за избор на стъпки 1 , 3 , 7 , 15 , 31 , ... Първо, всички елементи, които са на разстояние седем позиции един от друг се групират и сортират по отделно. Този процес се нарича сортиране със стъпка 7. В пример с 10 елемента всяка група съдържа точно по два елемента. След това елементите се прегрупират така, че във всяка група те да са през три позиции и се сортират отново - сортиране със стъпка 3. Най-после при третото преминаване елементите се сортират чрез обикновено сортиране или сортиране със стъпка 1.
Нека са дадени N елемента. Един елемент от списъка се определя за основен (в нашият случай това е средният). Останалите елементи се сравняват с основния и евентуално сменят позициятя си. Когато са по-малки се разполагат в списъка преди основния, а когато са по-големи, се разполагат в списъка след него. Това подреждане представлява етап от сортировката. В края на този етап основният елемент се намира в списъка на позиция, съответстваща на мястото му в окончателния подреден списък. Списъкът е подреден на две части. Първата - от началото до основния елемент, а втората - от основния елемент до края. Само една от тях може да се обработва веднага в следващата стъпка, а другата се запомня в списъка за заявки за разделяне. Съществено е, че списъкът от заявки се подрежда по обратен ред на заявките. 3. СОРТИРАНЕ НА ПОСЛЕДОВАТЕЛНИ ФАЙЛОВЕ (СМЕСВАНЕ) Горните методи за сортиране са неприложими при условие, че данните не се събират в оперативната памет на компютъра, или се намират на външно запомнящо устройство с последователен достъп (например, магнитна лента). В този случай данните се описват като последователен файл, т.е. във всеки момент е пряко достъпен само един елемент от редицата по местоназначение на обектите. Това е много силно ограничение, което оказва влияние върху методите за сортиране на този тип данни. Почти всички по-важни методи за сортиране на последователни файлове работят чрез СЛИВАНЕ. Сливането (или обединяването) на практика означава комбиниране на две или повече редици от данни в една, която се подрежда по определен критерий на качеството (сортира) чрез непрекъснато избиране от достъпните в момента елементи. Сливането е много по-проста операция от сортирането и се използва само като допълнителна стъпка (действие) в по-сложния процес на последователното сортиране. Сливането като отделна фаза не извършва сортиране на елементи от редицата, но създава условия за ефективност на сортировката. ВЪПРОСИ И ЗАДАЧИ за самостоятелна работа 1. Разработете блокови алгоритми за привеждане във векторен вид и сортиране на числовите масиви по всички методи. Сравнете алгоритмите по сложност. а) б)
2. Разработете блокови алгоритми за сортиране на последователните файлове: 47 -13 24 1,5 -1,7 33,3 0 -25 25 14,4 -33,3 19 39,4 -13 26 14 -19 2,3 -9,7 -9,7 5 3,5 44 -36,2 34 -26 -2,3 5 13 3. Направете сравнение на методите за сортиране като ги приложите преди и след сливането на последователните файлове от задача №2. Каталог: docs -> Bachelor -> II%20Kurs -> Sem%20IV -> SAA SAA -> Вероятностни алгоритми Цел: Упражняване в създаването и програмната реализация на вероятностни алгоритми Теоретична част SAA -> Лекция №2 алгоритмично-програмни конструкции видове алгоритми SAA -> Дървета Цел SAA -> Евристически алгоритми SAA -> Цел: Запознаване с метода за създаване на ефективно по – рекурсия. Създаване и използване на рекурсивни функции при решаване на сложни задачи. Теоретична част SAA -> Лекция №3 Сложност на алгоритмите SAA -> Задача за "Ход на коня". Задача 1: Ход на коня SAA -> Усвояне на похватите за представяне на графи в по, програмна реализация на графи и решаване на задачи над графи SAA -> Сортировка чрез вмъкване Изтегляне 66.88 Kb. Сподели с приятели:
| |||||||||||||||||||||||