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

2024-12-08T08:00:57Z

85.172.21.146: не верно поставленные переменные приводят к тому, что код не работает

{{Алгоритм
| предназначение = [[Алгоритм сортировки]]|изображение
| подпись = Действие алгоритма на примере сортировки случайных точек.
| данные = [[Массив (программирование)|Массив]]
| время = <math>O(n^2)</math>
| лучшее-время = <math>O(n^2)</math>
| среднее-время = <math>O(n^2)</math>
| память = <math>O(1)</math>
}}
'''Сортировка выбором''' ([[Английский язык|англ.]] ''selection sort'') — [[алгоритм сортировки]]. Может быть как устойчивый, так и неустойчивый.
На массиве из <math>n</math> элементов имеет время выполнения в худшем, среднем и лучшем случае <math>O(n^2)</math>, предполагая что сравнения делаются за постоянное время.

== Алгоритм без дополнительного выделения памяти ==
[[Файл:Selection-Sort-Animation.gif|thumb|288px|Сортировка выбором]]
Шаги алгоритма:
# Находим номер минимального значения в текущем списке.
# Производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции).
# Теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.

== Реализация алгоритма на языках программирования ==
Далее находится пример [[Устойчивая сортировка|неустойчивой]] реализации данного алгоритма:

=== [[C++]] ===
<source lang="cpp" line="1">
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]);
}
}
}
</source>

=== [[C Sharp|C#]] ===

<source lang="csharp" line="1">
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;
}
</source>

=== [[PL/SQL]] ===

<source lang="plsql" line="1">
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;
</source>
=== [[Java]] ===

<source lang="java" line="1">
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);

}
}

</source>

=== [[Ruby]] ===
<syntaxhighlight lang="ruby" line="1" start="1">
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
</syntaxhighlight>
=== [[Swift (язык программирования)|Swift]] ===
<syntaxhighlight lang="swift" line="1" start="1">
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
}
}
}
}
</syntaxhighlight>
=== [[PascalABC.NET]] ===
<syntaxhighlight lang=pascal line="1">
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
</syntaxhighlight>

=== [[Python]] ===
<source lang="python" line="1">
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]:
A[k], A[min_index] = A[min_index], A[k]
return A

</source>

=== [[Go]] ===
<syntaxhighlight lang="go" line="1">
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]
}
}
</syntaxhighlight>

=== [[Rust (язык программирования)|Rust]] ===
<syntaxhighlight lang="rust" line="1">
fn selection_sort<T: Ord>(array: &mut [T]) {
let n = array.len();

for i in 0..n {
let mut min_index = i;
for j in i + 1..n {
if array[min_index] > array[j] {
min_index = j;
}
}
if min_index != i {
array.swap(i, min_index);
}
}
}
</syntaxhighlight>

=== Почему такая реализация неустойчива? ===
Покажем, почему данная реализация является неустойчивой.

Рассмотрим следующий массив из элементов, каждый из которых имеет два поля. Сортировка идет по первому полю. 
Массив до сортировки: <code>{ (2, a), (2, b), (1, a) }</code> 
Уже после первой итерации внешнего цикла будем иметь отсортированную последовательность: <code>{ (1, a), (2, b), (2, a) }</code>

Теперь заметим, что взаимное расположение элементов <code>(2, a)</code> и <code>(2, b)</code> изменилось. 
Таким образом, рассматриваемая реализация является неустойчивой.

== Сравнение с другими алгоритмами сортировки ==
Так как после каждого прохода по внутреннему циклу делается только один обмен, то общее число обменов равно <math>n-1</math>, что в <math>n/2</math> раз меньше, чем в [[Сортировка пузырьком|сортировке пузырьком]]. 
Число проходов по внутреннему циклу равно <math>n-1</math> даже в случае сортировки частично или полностью отсортированного массива.

* Число сравнений в теле цикла равно <math>(n-1)*n/2</math>.
* Число сравнений в заголовках циклов <math>(n-1)*n/2</math>.
* Число сравнений перед операцией обмена <math>n-1</math>.
* Суммарное число сравнений <math>n^2-1</math>.
* Число обменов <math>n-1</math>.

Время сортировки 10000 коротких целых чисел на одном и том же [[Программно-аппаратный комплекс|программно-аппаратном комплексе]] сортировкой выбором составило ≈ 40 секунд, а ещё более улучшенной [[Сортировка пузырьком|сортировкой пузырьком]] ≈ 30 секунд. 
[[Пирамидальная сортировка]] сильно улучшает базовый алгоритм, используя структуру данных «[[Сортирующее дерево|куча]]» для ускорения нахождения и удаления минимального элемента.
Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.

== Литература ==
* {{source|Q21694522|part=Глава 3. Метод грубой силы: Сортировка выбором|pages=143—144}}
* {{книга
|часть = '''Часть III. Глава 6. Элементарные методы сортировки: 6.2 Сортировка выбором'''
|заглавие = Алгоритмы на C++
|оригинал = Algorithms in C++
|автор = Роберт Седжвик
|ссылка =
|isbn = 978-5-8459-1650-1
|страницы = 246-247
|год = 2011
|место = М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
}}
* {{Книга:CLRS}}

== См. также ==
* [[Алгоритм сортировки#Список алгоритмов сортировки|Список алгоритмов сортировки]]
* [[Сортировка пузырьком]]
* [[Сортировка вставками]]

== Ссылки ==
* {{cite web|url=http://algolist.manual.ru/sort/select_sort.php|title=Статья "Сортировка выбором" на сайте algolist.manual.ru|accessdate=2012-09-25}}
* [https://airtucha.github.io/SortVis/ Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом]

{{wikibooks|Примеры реализации сортировки выбором|Примеры реализации сортировки выбором}}

{{Алгоритмы сортировки}}
[[Категория:Алгоритмы сортировки]]

wiki12 - Вклад [ru]

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