метод сортування вставками;
метод сортування вибором;
метод Шелла.
2.4 Сортування бульбашковим методом
Найбільш відомою (і найбільш "безславної") є сортування бульбашковим методом. Її популярність пояснюється прикметною назвою і простотою алгоритму. Однак, ця сортування є однією з найгірших серед усіх коли-небудь придуманих сортировок. Метод заснований на тому, що в процесі виконання алгоритму більш "легкі" елементи масиву поступово "спливають". Особливістю даного методу є порівняння не кожного елемента з усіма, а порівняння в парах сусідніх елементів. Алгоритм бульбашкового сортування за зменшенням полягає в послідовних переглядах знизу вгору (від початку до кінця) масиву М. Якщо сусідні елементи такі, що виконується умова, згідно з яким елемент праворуч більше елемента зліва, то виконується обмін значеннями цих елементів. p align="justify"> Сортування бульбашковим методом використовує метод обмінного сортування. Вона заснована на виконанні в циклі операцій порівняння і при необхідності обміну сусідніх елементів. Її назва походить за подібності процесу руху бульбашок в резервуарі з водою, коли кожен пухирець знаходить свій власний рівень. Нижче показана найпростіша форма програми сортування методом бульбашки:
{сортування бульбашковим методом}
procedure Bubble (var item: DataArray; count: integer);, j: integer;: DataItem; i: = 2 to count doj: = count downto i doitem [j-1]> item [j] then: = item [j-1]; [j-1]: = item [j]; [j]: = x;;;
end; {кінець сортування бульбашковим методом}
У цьому випадку дане "item" є масивом елементів "DataItem", який сортується, а дане "count" містить число елементів у масиві.
Сортування бульбашковим методом має два циклу. Оскільки число елементів масиву задається змінною "count", зовнішній цикл викликає перегляд масиву count - 1 раз. Це забезпечує знаходження кожного елемента у своїй позицій після завершення процедури. Внутрішній цикл призначений для фактичного виконання операцій порівняння і обміну. ​​p align="justify"> Для ілюстрації роботи сортування бульбашковим методом нижче дано результати кожного етапу сортування масиву "dcab":
вихідне положення: dcab;
перший прохід: adcb;
другий прохід: abdc;
третій прохід: abc d.
При аналізі всякої сортування визначається число операцій порівняння і обміну, виконуваних в кращому, середньому і найгіршому випадках. Для сортування бульбашковим методом число порівнянь залишається незмінним, оскільки два циклу завжди виконуються задане число разів незалежно від впорядкованості вихідного масиву. Це означає, що при сортуванні бульбашковим методом завжди виконується...
