Информатика / Курсовая работа: Методы внутренней сортировки Обменная сортировка Сравнение с другими методами сортировки

Курсовая работа: Методы внутренней сортировки Обменная сортировка Сравнение с другими методами сортировки

1 8 23 5 65 44 33 6

Шаг 2

1 8 23 5 65 44 6 33

1 8 23 5 65 6 44 33

1 8 23 5 6 65 44 33

1 8 23 5 6 65 44 33

1 8 5 23 6 65 44 33

1 5 8 23 6 65 44 33

Шаг 3

1 5 8 23 6 65 33 44

1 5 8 23 6 33 65 44

1 5 8 23 6 33 65 44

1 5 8 6 23 33 65 44

1 5 6 8 23 33 65 44

Шаг 4

1 5 6 8 23 33 44 65

1 5 6 8 23 33 44 65

1 5 6 8 23 33 44 65

1 5 6 8 23 33 44 65

Шаг 5

1 5 6 8 23 33 44 65

1 5 6 8 23 33 44 65

1 5 6 8 23 33 44 65

Шаг 6

1 5 6 8 23 33 44 65

1 5 6 8 23 33 44 65

Шаг 7 1 5 6 8 23 33 44 65

Для метода простой обменной сортировки требуется число сравнений nx (n-1)/2, минимальное число пересылок 0, а среднее и максимальное число пересылок - O(n2 ).

Метод пузырька допускает три простых усовершенствования. Во-первых, как показывает таблица 3, на четырех последних шагах расположение значений элементов не менялось, (массив оказался уже упорядоченным). Поэтому, если на некотором шаге не было произведено ни одного обмена, то выполнение алгоритма можно прекращать. Во-вторых, можно запоминать наименьшее значение индекса массива, для которого на текущем шаге выполнялись перестановки. Очевидно, что верхняя часть массива до элемента с этим индексом уже отсортирована, и на следующем шаге можно прекращать сравнения значений соседних элементов при достижении такого значения индекса. В-третьих, метод пузырька работает неравноправно для "легких" и "тяжелых" значений. Легкое значение попадает на нужное место за один шаг, а тяжелое на каждом шаге опускается по направлению к нужному месту на одну позицию.

На этих наблюдениях основан метод шейкерной сортировки (ShakerSort). При его применении на каждом следующем шаге меняется направление последовательного просмотра. В результате на одном шаге "всплывает" очередной наиболее легкий элемент, а на другом "тонет" очередной самый тяжелый. Пример шейкерной сортировки приведен в таблице 2.4.

Таблица 4. Пример шейкерной сортировки

Начальное состояние массива 8 23 5 65 44 33 1 6
Шаг 1

8 23 5 65 44 33 1 6

8 23 5 65 44 1 33 6

8 23 5 65 1 44 33 6

8 23 5 1 65 44 33 6

К-во Просмотров: 332
Бесплатно скачать Курсовая работа: Методы внутренней сортировки Обменная сортировка Сравнение с другими методами сортировки