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

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

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

При использовании этого алгоритма массив делится на две части –отсортированную и несортированную. Сортированный список находится вначале. Все элементы справа от последнего отсортированного элемента считаются несортированными.

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

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

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

Рассмотри, как сортировка выборкой работает с массивом:

 5, 2, 4, 6, 1,

Реализация сортировки выборкой

Перейдем к реализации данного алгоритма в JavaScript:

function selectionSort(inputArr) { 
    let n = inputArr.length;
        
    for(let i = 0; i < n; i++) {
        // Находим наименьшее число в правой части массива
        let min = i;
        for(let j = i; j < n; j++) {
            if(inputArr[j] < inputArr[min]) {
                min=j; 
            }
         }
         if (min != i) {
             // Заменяем элементы
             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 ) – довольно высокий показатель временной сложности алгоритма. При сортировке набора используются более быстрые алгоритмы сортировки с временной сложностью O(nlogn).

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

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

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

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

Другой вариант – двунаправленная сортировка выбором. Она выполняет ту же самую работу на 25% быстрее.

Заключение

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

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

Пожалуйста, оставьте ваши комментарии по текущей теме статьи. Мы крайне благодарны вам за ваши комментарии, дизлайки, подписки, отклики, лайки!

Данная публикация является переводом статьи «Selection Sort in JavaScript» , подготовленная редакцией проекта.

Меню