heap.tech
лаборатория велосипедов
×

Selection sorting algorithm. Сортировка выбором.

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

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


Ссылка на предыдущие части:

1. Bubble sorting algorithm. Пузырьковая сортировка

Описание алгоритма

Пусть массив А состоит из 4 ячеек: [3,1,4,0]. Нужно отсортировать массив по возрастанию, то есть от меньшего к большему.
Сортировка перебором начинается с первого элемента массива. Запоминаем номер ячейки с тройкой как ячейку с минимальным значением и запускаем новый вложенный цикл - берем значение второй ячейки (в нашем случае это 1) и сравнивается со значением ячейки номер один (мы запомнили номер ячейки один как ячейку с минимальным значением). Единица меньше тройки – запоминаем новый номер ячейки, теперь это вторая ячейка. Пока вторая ячейка – это наименьшее число, но в массиве еще есть где поискать. Едем далее. Наконец мы доходим до последней ячейки, ее значение это ноль. 0 меньше 1. Ура, найдена ячейка с минимальным значением в массиве. Теперь меняем местами первый элемент и элемент с минимальным значением. И так до конца.

Реализация

function selectionSort(arr) { var indexer, temp, len = arr.length; for (var i = 0; i < len; i++) { indexer = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[indexer]) { indexer = j; } } temp = arr[i]; arr[i] = arr[indexer]; arr[indexer] = temp; } return arr; }


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

Минусы
Алгоритм всегда будет иметь одинаковое количество сравнений (N2 -1) и перестановок (N – 1).
(где N – кол-во ячеек в массиве).

Плюсы
Он простой.


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

function selectionSort(arr, byDesc) { var indexer, temp, len = arr.length; var isEquals = function (a, b) { if (byDesc) return a > b; else return a < b; }; for (var i = 0; i < len; i++) { indexer = i; for (var j = i + 1; j < len; j++) { if (isEquals(arr[j], arr[indexer])) { indexer = j; } } temp = arr[i]; arr[i] = arr[indexer]; arr[indexer] = temp; } return arr; }


Вызывать так:
selectionSort([9,4,1,6,0,2], true);
 
1603
0

Оставлять комментарии могут только зарегистрированные пользователи

пока никто не оставлял комментариев