Сортировка выбором | |
---|---|
Действие алгоритма на примере сортировки случайных точек. | |
Предназначение | Алгоритм сортировки |
Структура данных | Массив |
Худшее время | О(n2) |
Лучшее время | О(n2) |
Среднее время | О(n2) |
Затраты памяти | О(n) всего, O(1) дополнительно |
Сортировка выбором (Selection sort) — алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время.
Шаги алгоритма:
Для реализации устойчивости алгоритма необходимо в пункте 2 минимальный элемент непосредственно вставлять в первую неотсортированную позицию, не меняя порядок остальных элементов.
Пример неустойчивой реализации:
1 #include <cstddef>
2 #include <utility>
3 using namespace std;
4
5 template<typename T>
6 void selection_sort(T array[], size_t size) {
7 for (size_t idx_i = 0; idx_i < size - 1; idx_i++) {
8 size_t min_idx = idx_i;
9 for (size_t idx_j = idx_i + 1; idx_j < size; idx_j++) {
10 if (array[idx_j] < array[min_idx]) {
11 min_idx = idx_j;
12 }
13 }
14
15 if (min_idx != idx_i) {
16 swap(array[idx_i], array[min_idx]);
17 min_idx = idx_i;
18 }
19 }
20 }
1 public static IList<int> Selection(IList<int> list)
2 {
3 for (int i = 0; i < list.Count-1; i++)
4 {
5 int min = i;
6 for (int j = i + 1; j < list.Count; j++)
7 {
8 if (list[j] < list[min])
9 {
10 min = j;
11 }
12 }
13 int dummy = list[i];
14 list[i] = list[min];
15 list[min] = dummy;
16 }
17 return list;
18 }
1 type sort_choice_list is table of integer index by binary_integer;
2 ---------------------------------------------
3 function SORT_CHOICE return sort_choice_list
4 IS
5 list sort_choise_list;
6 l_min pls_integer;
7 l_dummy pls_integer;
8 begin
9
10 for n in 1..100 loop
11 list(n):=dbms_random.random; --инициализация массива случайными числами
12 end loop;
13
14 for i in list.first..list.last loop
15 l_min:=i;
16 for j in (i + 1)..list.last loop
17 if (list(j) < list(l_min)) then
18 l_min := j;
19 end if;
20 end loop;
21 l_dummy:=list(i);
22 list(i):=list(l_min);
23 list(l_min) := l_dummy;
24 end loop;
25
26 return list;
27
28 end SORT_CHOICE;
1 public static void sort(int[] arr) {
2 for (int min = 0; min < arr.length - 1; min++) {
3 int least = min;
4 for (int j = min + 1; j < arr.length; j++) {
5 if (arr[j] < arr[least]) {
6 least = j;
7 }
8 }
9 int tmp = arr[min];
10 arr[min] = arr[least];
11 arr[least] = tmp;
12 }
13 }
1 def selection_sort(array)
2 for min in 0..array.count-2
3 least = min
4 for j in (min + 1)..array.count-1
5 if array[j] < array[least]
6 least = j
7 end
8 end
9 temp = array[min]
10 array[min] = array[least]
11 array[least] = temp
12 end
13 end
Покажем, почему данная реализация является неустойчивой.
Рассмотрим следующий массив из элементов, каждый из которых имеет два поля. Сортировка идет по первому полю.
Массив до сортировки:
{ (2, a), (2, b), (1, a) }
Уже после первой итерации внешнего цикла будем иметь отсортированную последовательность:
{ (1, a), (2, b), (2, a) }
Теперь заметим, что взаимное расположение элементов (2, a) и (2, b) изменилось. Таким образом, рассматриваемая реализация является неустойчивой.
Так как после каждого прохода по внутреннему циклу делается только один обмен, то общее число обменов равно N-1, что в N/2 раз меньше, чем в сортировке пузырьком.
Число проходов по внутреннему циклу равно N-1 даже в случае сортировки частично или полностью отсортированного массива.
Наихудший случай:
Число сравнений в теле цикла равно (N-1)*N/2.
Число сравнений в заголовках циклов (N-1)*N/2.
Число сравнений перед операцией обмена N-1.
Суммарное число сравнений N2−1.
Число обменов N-1.
Наилучший случай:
Время сортировки 10000 коротких целых чисел на одном и том же программно-аппаратном комплексе сортировкой выбором составило ≈40сек., а ещё более улучшенной сортировкой пузырьком ≈30сек.
Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента.
Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .