Вступление

Выборочная сортировка - один из самых простых и интуитивно понятных алгоритмов сортировки. Это нестабильный алгоритм сравнения на месте .

Это означает, что он преобразует входную коллекцию без использования вспомогательных структур данных и что вход переопределяется выходом (алгоритм на месте).

Кроме того, во время выполнения он только считывает элементы списка с помощью одной абстрактной операции сравнения, обычно с помощью оператора «меньше или равно» (алгоритм сравнения).

Наконец, порядок повторяющихся элементов не сохраняется после сортировки (нестабильный алгоритм).

Его обычно преподают на ранних этапах большинства курсов по информатике, поскольку его очень легко понять и перевести в код. Несмотря на квадратичную временную сложность, в некоторых конкретных случаях он имеет преимущества в производительности по сравнению с некоторыми более сложными алгоритмами сортировки, такими как быстрая сортировка или сортировка слиянием.

В этой статье мы объясним идею сортировки по выбору и реализуем ее на JavaScript.

После этого мы проанализируем его временную сложность и сравним с другими алгоритмами сортировки. Наконец, мы обсудим, когда это можно использовать, а когда следует избегать.

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

Этот алгоритм делит входной массив на два подсписка - отсортированный и несортированный подсписок. Отсортированный список расположен в начале коллекции, и все элементы справа от последнего отсортированного элемента считаются несортированными.

Изначально отсортированный список пуст, а остальная часть коллекции не отсортирована. Сортировка выбора просматривает несортированный подсписок и находит самый маленький или самый большой элемент.

Затем элемент заменяется крайним левым элементом несортированного подсписка. Затем отсортированный подсписок расширяется, чтобы включить этот элемент.

Это повторяется, находя подходящий элемент, меняя его местами с крайним левым элементом несортированного списка и расширяя отсортированный список, чтобы охватить его.

После каждой итерации нужно проверять на один элемент меньше, пока не будет отсортирован весь массив или список. Другими словами, после k-й итерации первые k элементов массива или списка гарантированно будут отсортированы.

Давайте посмотрим на это визуальное представление того, как Selection Sort работает с массивом:

 5, 2, 4, 6, 1, 3 

{.ezlazyload}

Выборка Сортировка Реализация

Теперь, когда мы разобрались с идеей сортировки выбора и ее визуального представления, мы можем перейти к реализации алгоритма на JavaScript:

 function selectionSort(inputArr) { 
 let n = inputArr.length; 
 
 for(let i = 0; i < n; i++) { 
 // Finding the smallest number in the subarray 
 let min = i; 
 for(let j = i+1; j < n; j++){ 
 if(inputArr[j] < inputArr[min]) { 
 min=j; 
 } 
 } 
 if (min != i) { 
 // Swapping the elements 
 let tmp = inputArr[i]; 
 inputArr[i] = inputArr[min]; 
 inputArr[min] = tmp; 
 } 
 } 
 return inputArr; 
 } 

Мы перебираем весь входной массив и для каждого элемента массива находим наименьшее число в несортированном подмассиве. Если наименьшее число не является первым в несортированном подмассиве (еще не на своем месте), мы меняем его местами с первым элементом несортированного подмассива.

Не проверяя, является ли наименьший элемент уже первым элементом несортированного подмассива, мы будем выполнять ненужные свопы.

Теперь давайте добавим входной массив и вызовем нашу функцию:

 let inputArr = [5, 2, 4, 6, 1, 3]; 
 selectionSort(inputArr); 
 console.log(inputArr); 

Результатом этого кода будет:

 (6) [1, 2, 3, 4, 5, 6] 

Сложность времени

Временную сложность сортировки выборкой нетрудно проанализировать.

В первой итерации по всему массиву из n элементов мы делаем n-1 сравнений и, возможно, одну замену. Во второй итерации мы сделаем n-2 сравнений и так далее.

Следовательно, общее количество сравнений будет (n-2) + (n-1) + ... + 1 , что в сумме дает n (n-1) / 2 = (n ^2^ -n) / 2 . Это приводит нас к времени работы O (n ^2^ ).

O (n ^2^ ) - довольно плохая временная сложность для алгоритма сортировки. При сортировке коллекции вы должны использовать более быстрые алгоритмы сортировки, такие как Quicksort или Merge Sort, с временной сложностью O (nlogn) .

Лучшая производительность сортировки выбора также составляет O (n ^2^ ) , поэтому проверка того, отсортирован ли массив или список, также действительно неэффективно.

С другой стороны, по сравнению с другими алгоритмами с квадратичной временной сложностью, такими как пузырьковая сортировка , сортировка выбора работает довольно хорошо, превосходя пузырьковую сортировку и ее варианты, а также сортировку Gnome .

Однако сортировка вставкой может быть быстрее, чем сортировка по выбору, если коллекция почти отсортирована. А сортировка вставкой практически не имеет себе равных с короткими коллекциями.

Выбор вариантов сортировки

Несмотря на то, что лучшие, худшие и средние показатели этого алгоритма равны O (n ^2^ ) , что делает его довольно неэффективным, сортировка по выбору очень важна для общей разработки алгоритмов сортировки. Фактически, это была база для некоторых очень широко используемых и эффективных алгоритмов сортировки!

Возможно, самый известный вариант - это сортировка кучей , которая внутренне использует структуру данных кучи для хранения элементов. Использование куч может ускорить поиск и удаление элементов до времени O (logn) .

Это очень полезная оптимизация, которая сокращает общее время работы с O (n ^ 2) до O (nlogn) , что считается хорошим для алгоритмов сортировки.

Другой вариант - это двунаправленная сортировка выбора , аналогичная двунаправленной сортировке. Иногда ее называют коктейльной сортировкой (опять же, она похожа на сортировку коктейлей от Bubble) и выполняет ту же работу в ~ 25% меньшем количестве сравнений.

Заключение

Выборочная сортировка - это фундаментальный и простой, поэтому неэффективный алгоритм сортировки. Он послужил основой для некоторых широко используемых и принятых алгоритмов и не очень часто используется в индустрии разработки.

Однако, если входная коллекция небольшая, сортировка по выбору - лучший вариант, чем быстрая сортировка или сортировка слиянием. Но опять же, сортировка вставкой в этих случаях оказалась более эффективной, чем сортировка по выбору.

В этой статье мы рассмотрели идею Selection Sort, реализовали ее в JavaScript, исследовали ее временную сложность и кратко упомянули некоторые из ее вариантов.