Методы сортировки массивов
Методы сортировки массивов
Сортировка массива методом "Выбора"
Сортировка массива методом "Вставки"
Сортировка вставками - достаточно простой алгоритм. Как в и любом другом алгоритме сортировки, с увеличением размера сортируемого массива увеличивается и время сортировки. Основным преимуществом алгоритма сортировки вставками является возможность сортировать массив по мере его получения.То есть имея часть массива, можно начинать его сортировать. В параллельном программирование такая особенность играет не маловажную роль.
Сортируемый массив можно разделить на две части - отсортированная часть и неотсортированная. В начале сортировки первый элемент массива считается отсортированным, все остальные - не отсортированные. Начиная со второго элемента массива и заканчивая последним, алгоритм вставляет неотсортированный элемент массива в нужную позицию в отсортированной части массива. Таким образом, за один шаг сортировки отсортированная часть массива увеличивается на один элемент, а неотсортированная часть массива уменьшается на один элемент. Рассмотрим пример сортировки по возрастанию массива из 7 чисел (см. Таблица 1):
исходный массив: 3 3 7 1 2 5 0
| шаг | отсортированная часть массива | тек. элемент | вставка | ||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | 3 | false | ||||||
| 2 | 3 | 3 | 7 | false | |||||
| 3 | 3 | 3 | 7 | 1 | true | ||||
| 4 | 1 | 3 | 3 | 7 | 2 | true | |||
| 5 | 1 | 2 | 3 | 3 | 7 | 5 | true | ||
| 6 | 1 | 2 | 3 | 3 | 5 | 7 | 0 | true | |
| - | 0 | 1 | 2 | 3 | 3 | 5 | 7 | - | - |
На каждом шаге сортировки сравнивается текущий элемент со всеми элементами в отсортированной части. На первом шаге сравнивается тройка с тройкой, они равны поэтому не меняем их местами. На втором шаге сравниваем 7 с двумя тройками,
