Давай разберемся

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

В отличие от пузырьковой сортировки, которая сравнивает соседние элементы, сортировка по выбору работает путем цикла по массиву, поиска наименьшего (или наибольшего в зависимости от того, выполняется ли сортировка по возрастанию или убывания) элемента и перемещения его в начало массива. Оттуда он перебирает каждый элемент, за исключением элементов, которые он уже установил на место, пока не пройдет весь массив.

Пошаговый пример

Ожидаемый результат

Сортировать по возрастанию
Ввод: [4, 2, 5, 1, 3, 6]
Выход: [1, 2, 3, 4, 5, 6]

Первая итерация

Давайте посмотрим на массив, чтобы найти минимальное значение, отслеживая его индекс. Начнем с первого элемента (индекс 0).

minIndex = 0
[4, 2, 5, 1, 3, 6]

4 больше 2, поэтому теперь minIndex = 1
[4, 2, 5, 1, 3, 6]

2 меньше 5, поэтому minIndex = 1
[4, 2, 5, 1, 3, 6]

2 больше 1, поэтому minIndex = 3
[4, 2, 5, 1, 3, 6]

1 меньше 3, поэтому minIndex = 3
[4, 2, 5, 1, 3, 6]

1 меньше 6, поэтому minIndex = 3
[4, 2, 5, 1, 3, 6]

Мы определили, что минимальное значение имеет индекс 3. Мы собираемся поменять местами элемент с индексом 0 на элемент с нашим minIndex. Теперь массив выглядит так:
[1, 2, 5, 4, 3, 6]

Вторая итерация

Поскольку мы уже поместили наименьшее число в индекс 0, мы начинаем итерацию с индекса 1, чтобы найти второе наименьшее число в массиве.

minIndex = 1
[1, 2, 5, 4, 3, 6]

2 ‹5, minIndex = 1
[1, 2, 5, 4, 3, 6]

2 ‹4, minIndex = 1
[1, 2, 5, 4, 3, 6]

2 ‹3, minIndex = 1
[1, 2, 5, 4, 3, 6]

2 ‹6, minIndex = 1
[1, 2, 5, 4, 3, 6]

minIndex никогда не менялся, поэтому нам не нужно выполнять свопинг.

Третья итерация

Начиная с индекса 2.

minIndex = 2
[1, 2, 5, 4, 3, 6]

5 ›4, minIndex = 3
[1, 2, 5, 4, 3, 6]

4 ›3, minIndex = 4
[1, 2, 5, 4, 3, 6]

3 ‹6, minIndex = 4
[1, 2, 5, 4, 3, 6]

Поменяйте местами 5 и 3, массив теперь выглядит так:
[1, 2, 3, 4, 5, 6]

Заключительные итерации

Несмотря на то, что наш массив уже отсортирован, мы все равно пройдем через массив еще 2 раза для индексов 3 и 4 (к тому времени, когда мы дойдем до последнего элемента с индексом 5, это должно быть максимальное значение так что нам не нужно повторять снова).

Код

Время для кода!

function selectionSort(arr){
    for(let i = 0; i < arr.length - 1; i++){
        let minIndex = i;
        for(let j = i + 1; j < arr.length; j++){
            if(arr[j] < arr[minIndex]){
                minIndex = j;
            }
        }
        if(i !== minIndex){
            let temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp; 
        }
    }
    return arr;
};

Объяснение кода

Поскольку мы знаем, что нам нужно проверить каждый элемент в массиве, мы устанавливаем цикл for на выполнение для длины массива минус 1, потому что к тому времени, когда мы дойдем до последнего элемента, мы знаем, что он отсортирован. На каждой итерации начальным значением minIndex будет число в этом индексе. Итак, для первой итерации minIndex будет 0, для второй - 1, как в нашем пошаговом примере выше.

Оттуда нам нужно сравнить его со всеми элементами после, поэтому наш вложенный цикл for имеет j, начинающийся с i + 1. Во время итерации по остальным элементам, если какой-либо из них меньше значения в индексе i, он изменит minIndex, чтобы отразить это.

Когда мы выходим из нашего вложенного цикла for и возвращаемся в наш первый цикл, мы проверяем, равно ли minIndex по-прежнему i. Если он не равен, это означает, что в какой-то момент нашего вложенного цикла мы нашли значение, которое меньше значения в индексе i, и нам нужно поменять местами эти значения.

Подобно свопу в пузырьковой сортировке, мы объявляем переменную с именем temp, чтобы удерживать то, что в настоящее время находится с индексом i, затем мы меняем значение по индексу i на минимальное значение. После этого мы присваиваем значение, которое раньше находилось в индексе i (temp), там, где было наше минимальное значение. Эффективная замена элементов.

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

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

В отличие от пузырьковой сортировки, нам не нужно начинать с начала массива для каждой итерации, поскольку на каждом проходе мы помещаем элемент в его правильную позицию. Это означает, что внутренний цикл for будет выполняться на 1 раз меньше для каждой итерации внешнего цикла for.

Это означает, что в нашем примере с 6 элементами в нашем массиве

На первой итерации мы прошли через 5 элементов.
На второй - через 4.
На третьей - через 3.
На четвертой - через 2.
Наконец-то у нас остался один.

So 5 + 4 + 3 + 2 + 1 = 15.

Другой способ думать об этом: (6 * (6–1)) / 2 = 15.

Итак, с точки зрения нашего ввода n * (n-1) * 1/2

Однако, думая об этом с точки зрения нотации Big O, мы собираемся рассмотреть, что вызывает самый высокий темп роста, поэтому это упрощается до O (n²). В лучшем случае, в худшем случае и в среднем случае все равны O (n²), потому что независимо от того, отсортирован ли массив уже, сортировка выбора будет продолжать выполняться одинаковое количество раз на заданном входе.

Космическая сложность

Так же, как пузырьковая сортировка, сортировка по выбору выполняется на месте. Это означает, что пространство в памяти, которое занимает этот алгоритм, не зависит от ввода, что дает нам сложность пространства O (1). Другими словами, постоянное время.

Неустойчивый алгоритм сортировки

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

Однако давайте рассмотрим, что мы сортируем массив объектов, представляющих студентов. Мы хотим отсортировать их по классам, но наш текущий массив отсортирован по алфавиту. При сортировке по классам мы также хотим сохранить их в алфавитном порядке. Таким образом, все ученики 1-го класса отображаются в алфавитном порядке, за ними следуют все ученики 2-го класса в алфавитном порядке и так далее.

let studentArr = [{name: "Al Cooper" , grade: 4}, {name: "Bobby Tables" , grade: 4}, {name: "Gracie Hopper" , grade: 3}]

Если бы мы передали этот массив в сортировку выбора, он бы выводил

[{name: "Gracie Hopper" , grade: 3}, {name: "Bobby Tables" , grade: 4}, {name: "Al Cooper" , grade: 4}]

О, нет! Мы хотели, чтобы Bobby Tables появился после Эла Купера. К сожалению, сортировка выбора будет учитывать только оценку, сначала перемещая Грейси в начало списка, а Ала перемещая на свое место. Оттуда они упорядочены по классам, поэтому алгоритм больше не меняет местами. Это означает, что хотя Ал и Бобби оба учились в 4 классе, их порядок отличается от нашего исходного массива.

В заключение…

Сортировка по выбору - это еще один простой алгоритм сортировки, который обычно не используется в реальных приложениях. Это связано с тем, что, как и пузырьковая сортировка, она имеет временную сложность O (n²) и плохо масштабируется для больших списков. Его преимущества в том, что он хорошо работает с небольшими списками, и что это постоянное время. В дополнение к этому, некоторые другие алгоритмы сортировки, такие как сортировка по куче, основаны на сортировке по выбору.