Geum.ru

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

Курсовой проект - Компьютеры, программирование

Другие курсовые по предмету Компьютеры, программирование

?щие индексы массива. Проследим этот процесс на примере нашего стандартного массива (таблица 2.6).

 

Таблица 6. Пример быстрой сортировки

Начальное состояние массива8 23 5 65 |44| 33 1 6Шаг 1 (в качестве x выбирается a[5])|--------|

8 23 5 6 44 33 1 65

|---|

8 23 5 6 1 33 44 65Шаг 2 (в подмассиве a[1], a[5] в качестве x выбирается a[3])8 23 |5| 6 1 33 44 65

|--------|

1 23 5 6 8 33 44 65

|--|

1 5 23 6 8 33 44 65Шаг 3 (в подмассиве a[3], a[5] в качестве x выбирается a[4])1 5 23 |6| 8 33 44 65

|----|

1 5 8 6 23 33 44 65Шаг 4 (в подмассиве a[3], a[4] выбирается a[4])1 5 8 |6| 23 33 44 65

|--|

1 5 6 8 23 33 44 65

Алгоритм недаром называется быстрой сортировкой, поскольку для него оценкой числа сравнений и обменов является O(n?log n). На самом деле, в большинстве утилит, выполняющих сортировку массивов, используется именно этот алгоритм.

 

6. Сравнение методов

 

Для сравнения методов сортировки была написана программа, позволяющая выполнить сортировку пятью способами, по возрастанию или убыванию. Заполнение массива производится случайными данными.

 

Рис 1. Интерфейс программы.

 

После выполнения сортировки программа выводит количество сравнений и перестановок. При сравнении заполнялась таблица зависимости числа перестановок и числа сравнений от размера массива.

 

Таблица 7

МетодСравненийПерестановокКол-во163264128256163264128256Пузырёк1355272079825532895692011150364414648QuickSort70223486122827712070160399887Выбором1204962016812832640112958124249Шелла731864841348377119542007562537Вставками743151177481917525462571056456617018

На основании данных таблицы были построены графики.

 

Рис 2. Зависимость числа перестановок от размера массива

 

Рис 3. Зависимость числа сравнений от размера массива.

 

Выводы

 

По результатам замеров производительности методов можно сделать следующие выводы:

  1. Наиболее универсальным методом, является метод быстрой сортировки (QuickSort), он показывает стабильно высокие результаты на любых размерах массивов. На втором месте находится метод Шелла. Его использование может быть обосновано большее простым алгоритмом с точки зрения программиста.
  2. Метод вставки эффективен, при условии большого времени выполнения операций перестановки, так как он является абсолютным лидером по количеству перестановок, проигрывая при этом по количеству сравнений.
  3. При использовании небольших массивов данных нет большой разницы по скорости между методами сортировки, поэтому целесообразнее применять метод Пузырька или метод вставок.
  4. Исследование проводилось на массивах с большой степенью неупорядоченности. Для массивов, которые уже являются почти отсортированными, наиболее применим метод сортировки вставками.

 

Приложение

 

Блок схемы.

 

Обменная сортировка.

 

Сортировка выбором.

 

Сортировка вставкой.