Сортировка выбором
Из Википедии, бесплатной энциклопедии
Сортировка выбором | |
---|---|
| |
Предназначение | Алгоритм сортировки |
Структура данных | Массив |
Худшее время | |
Лучшее время | |
Среднее время | |
Затраты памяти | |
Медиафайлы на Викискладе |
Сортировка выбором (англ. selection sort) — алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из элементов имеет время выполнения в худшем, среднем и лучшем случае , предполагая что сравнения делаются за постоянное время.
Алгоритм без дополнительного выделения памяти[править | править код]
Шаги алгоритма:
- Находим номер минимального значения в текущем списке.
- Производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции).
- Теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.
Реализация алгоритма на языках программирования[править | править код]
Далее находится пример неустойчивой реализации данного алгоритма:
C++[править | править код]
template <typename type_arr> void selection_sort(type_arr *arr, int size) { for (int i = 0; i < size - 1; i++) { int min_index = i; for (int j = i + 1; j < size; j++) { if (arr[j] < arr[min_index]) { min_index = j; } } if (min_index != i) { swap(arr[i], arr[min_index]); } } }
C#[править | править код]
public static IList<T> Selection<T>(IList<T> list) where T : IComparable<T> { for (int i = 0; i < list.Count - 1; ++i) { int min = i; for (int j = i + 1; j < list.Count; ++j) { if (list[j].CompareTo(list[min]) < 0) { min = j; } } var dummy = list[i]; list[i] = list[min]; list[min] = dummy; } return list; }
PL/SQL[править | править код]
type sort_choice_list is table of integer index by binary_integer; --------------------------------------------- function SORT_CHOICE return sort_choice_list IS list sort_choise_list; l_min pls_integer; l_dummy pls_integer; begin for n in 1..100 loop list(n):=dbms_random.random; --инициализация массива случайными числами end loop; for i in list.first..list.last loop l_min:=i; for j in (i + 1)..list.last loop if (list(j) < list(l_min)) then l_min := j; end if; end loop; l_dummy:=list(i); list(i):=list(l_min); list(l_min) := l_dummy; end loop; return list; end SORT_CHOICE;
Java[править | править код]
public static void selectionSort(int [] arr) { int n = arr.length; for(int i = 0; i<n-1; i++) { int minIndex = i; for(int j=i+1; j<n; j++) { if(arr[j]<arr[minIndex]) { minIndex = j; } } if(minIndex!=i) swap(arr,i,minIndex); } }
Ruby[править | править код]
def selection_sort(array) for min in 0..array.count-2 least = min for j in (min + 1)..array.count-1 if array[j] < array[least] least = j end end temp = array[min] array[min] = array[least] array[least] = temp end end
Swift[править | править код]
func selectionSort<Element>(_ array: inout Array<Element>) where Element: Comparable { for min in 0..<array.count - 1 { for j in min..<array.count { if array[j] < array[min] { let temp = array[min] array[min] = array[j] array[j] = temp } } } }
PascalABC.NET[править | править код]
begin var a := ArrRandom; a.Println; for var i:=0 to a.High do Swap(a[i],a[i+a[i:].IndexMin]); a.Println; end
Python[править | править код]
def select_sort(A): for i in range(len(A) - 1): min_index = i for k in range(i + 1, len(A)): if A[k] < A[min_index]: min_index = k A[i], A[min_index] = A[min_index], A[i] return A
Go[править | править код]
func selectionSort(nums []int) { n := len(nums) for i := 0; i < n; i++ { min := i for j := i + 1; j < n; j++ { if nums[j] < nums[min] { min = j } } nums[i], nums[min] = nums[min], nums[i] } }
Почему такая реализация неустойчива?[править | править код]
Покажем, почему данная реализация является неустойчивой.
Рассмотрим следующий массив из элементов, каждый из которых имеет два поля. Сортировка идет по первому полю.
Массив до сортировки: { (2, a), (2, b), (1, a) }
Уже после первой итерации внешнего цикла будем иметь отсортированную последовательность: { (1, a), (2, b), (2, a) }
Теперь заметим, что взаимное расположение элементов (2, a)
и (2, b)
изменилось.
Таким образом, рассматриваемая реализация является неустойчивой.
Сравнение с другими алгоритмами сортировки[править | править код]
Так как после каждого прохода по внутреннему циклу делается только один обмен, то общее число обменов равно , что в раз меньше, чем в сортировке пузырьком.
Число проходов по внутреннему циклу равно даже в случае сортировки частично или полностью отсортированного массива.
- Число сравнений в теле цикла равно .
- Число сравнений в заголовках циклов .
- Число сравнений перед операцией обмена .
- Суммарное число сравнений .
- Число обменов .
Время сортировки 10000 коротких целых чисел на одном и том же программно-аппаратном комплексе сортировкой выбором составило ≈ 40 секунд, а ещё более улучшенной сортировкой пузырьком ≈ 30 секунд.
Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента. Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.
Литература[править | править код]
- Левитин А. В. Глава 3. Метод грубой силы: Сортировка выбором // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 143—144. — 576 с. — ISBN 978-5-8459-0987-9
- Роберт Седжвик. Часть III. Глава 6. Элементарные методы сортировки: 6.2 Сортировка выбором // Алгоритмы на C++ = 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 алгоритмов сортировки с открытым исходным кодом