Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Обменная сортировка
Простая обменная сортировка (в просторечии называемая «методом пузырька») для массива a[1], a[2],..., a[n] работает следующим образом. Начиная с начала массива сравниваются два соседних элемента (a[ i ] и a[ i + 1]). Если выполняется условие a[ i ] > a[ i + 1], то значения элементов меняются местами. Процесс продолжается для a[ i + 1] и a[ i + 2] и т.д., пока не будет произведено сравнение a[ n – 1] и a[ n ]. Понятно, что после этого на месте a[ n ] окажется элемент массива с наибольшем значением. На втором шаге процесс повторяется, но последними сравниваются a[ n – 2] и a[ n – 1]. И так далее. На последнем шаге будут сравниваться только текущие значения a[1] и a[2]. Понятна аналогия с пузырьком, поскольку наименьшие элементы (самые «легкие») постепенно «всплывают» к верхней границе массива. Для метода простой обменной сортировки требуется число сравнений n(n – 1)/2, минимальное число пересылок 0, а среднее и максимальное число пересылок - O(n 2 ). Метод пузырька допускает три простых усовершенствования. Во-первых, можно отслеживать момент на котором массив окажется отсортированным. Если на некотором шаге не было произведено ни одного обмена, то выполнение алгоритма можно прекращать. Во-вторых, можно запоминать наименьшее значение индекса массива, для которого на текущем шаге выполнялись перестановки. Очевидно, что верхняя часть массива до элемента с этим индексом уже отсортирована, и на следующем шаге можно прекращать сравнения значений соседних элементов при достижении такого значения индекса. i: = 0; REPEAT fl: = TRUE; i: = i + 1; FOR j: = 1 TO n – i DO IF a[j] > a[j + 1] THEN BEGIN fl: = FALSE; x: = a[j]; a[j]: = a[j + 1]; a[j + 1]: = x END; UNTIL fl; Метод пузырька работает неравноправно для «легких» и «тяжелых» значений. Легкое значение попадает на нужное место за один шаг, а тяжелое на каждом шаге опускается по направлению к нужному месту на одну позицию. На этих наблюдениях основан метод шейкерной сортировки (ShakerSort). При его применении на каждом следующем шаге меняется направление последовательного просмотра. В результате на одном шаге «всплывает» очередной наиболее легкий элемент, а на другом «тонет» очередной самый тяжелый. {шейкер-сортировка по убыванию} L: = 2; R: = n; k: = n; REPEAT FOR j: = R DOWNTO L DO IF a[j – 1] < a[j] THEN BEGIN x: = a[j]; a[j]: = a[j – 1]; a[j – 1]: = x; k: = j END; L: = k + 1; FOR j: = L TO R DO IF a[j – 1] < a[j] THEN BEGIN x: = a[j]; a[j]: = a[j – 1]; a[j – 1]: = x; k: = j END; R: = k – 1; UNTIL L> R; Шейкерная сортировка позволяет сократить число сравнений (по оценке Кнута средним числом сравнений является (n 2 – n(const + ln n)), хотя порядком оценки по-прежнему остается n 2 . Число же пересылок, вообще говоря, не меняется. Шейкерную сортировку рекомендуется использовать в тех случаях, когда известно, что массив «почти упорядочен».
|