Сортировка выбором
| Сортировка выбором | |
|---|---|
 | |
| Предназначение | Алгоритм сортировки |
| Структура данных | Массив |
| Худшее время | О(n2) |
| Лучшее время | О(n2) |
| Среднее время | О(n2) |
| Затраты памяти | О(n) всего, O(1) дополнительно |
Сортировка выбором (Selection sort) — алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время.
Алгоритм без дополнительного выделения памяти[править | править код]
Шаги алгоритма:
- находим номер минимального значения в текущем списке
- производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции)
- теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы
Пример неустойчивой реализации:
1 #include <cstddef>
2 #include <utility>
3
4 using namespace std;
5
6 template<typename T>
7 void selection_sort(T array[], const size_t size)
8 {
9 for (size_t idx_i = 0; idx_i < size - 1; idx_i++)
10 {
11 size_t min_idx = idx_i;
12
13 for (size_t idx_j = idx_i + 1; idx_j < size; idx_j++)
14 {
15 if (array[idx_j] < array[min_idx])
16 {
17 min_idx = idx_j;
18 }
19 }
20
21 if (min_idx != idx_i)
22 {
23 swap(array[idx_i], array[min_idx]);
24 }
25 }
26 }
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
1 func selectionSort<Element>(_ array: inout Array<Element>) where Element: Comparable {
2 for min in 0..<array.count - 1 {
3 var least = min
4 for j in min..<array.count {
5 if array[j] < array[least] {
6 least = j
7 }
8 let temp = array[min]
9 array[min] = array[least]
10 array[least] = temp
11 }
12 }
13 }
1 begin
2 var a := ArrRandom;
3 a.Println;
4
5 for var i:=0 to a.High do
6 Swap(a[i],a[i+a[i:].IndexMin]);
7
8 a.Println;
9 end
Python 3.1
N = int(input())
a = [int(i) for i in input().split()]
k = 0
for i in range(N):
k = i - 1
num = a[i]
while a[k] > num and k >= 0:
a[k + 1], a[k] = a[k], a[k + 1]
k -= 1
print(*a)
Покажем, почему данная реализация является неустойчивой.
Рассмотрим следующий массив из элементов, каждый из которых имеет два поля. Сортировка идет по первому полю.
Массив до сортировки:
{ (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сек.
Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента.
Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.
Литература[править | править код]
- Левитин А. В. Глава 3. Метод грубой силы: Сортировка выбором // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 143—144. — 576 с. — ISBN 978-5-8459-0987-9
- Роберт Седжвик. Часть III. Глава 6. Элементарные методы сортировки: 6.2 Сортировка выбором // Алгоритмы на С++ = Algorithms in C++. — М.: «Вильямс», 2011. — С. 246-247. — ISBN 978-5-8459-1650-1.
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
См. также[править | править код]
Ссылки[править | править код]
- Статья "Сортировка выбором" на сайте algolist.manual.ru. Дата обращения 25 сентября 2012.
- Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом
 | |
|---|---|
| Теория |
|
| Обменные | |
| Выбором | |
| Вставками | |
| Слиянием | |
| Без сравнений | |
| Гибридные | |
| Прочее | |
| Непрактичные | |
