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

Всем привет. Эту статью я написал специально к запуску курса «Алгоритмы и структуры данных» от OTUS.

---

Введение

Сортировка массива является одной из первых серьезных задач, изучаемых в классическом курсе «Алгоритмы и структуры данных» дисциплины computer science. В связи с этим задачи на написание сортировок и соответствующие вопросы часто встречаются на собеседованиях на позиции стажера или junior разработчика.

Постановка задачи

Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.

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

Одной из простейших сортировок является сортировка выбором.

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

Сортировка массива выбором осуществляется так: массив делится на две части. Одна из частей называется отсортированной, а другая неотсортированной. Алгоритм предполагает проход по всему массиву с тем, чтобы длина отсортированной части стала равна длине всего массива. В рамках каждой итерации мы находим минимум в неотсортированной части массива и меняем местами этот минимум с первым элементом неотсортированной части массива. После чего мы увеличиваем длину отсортированной части массива на единицу. Пример осуществления одной итерации представлен ниже:
1 3 5 | 8 9 6 -> 1 3 5 6 | 9 8

Реализация

Предлагаю посмотреть на реализацию данного алгоритма на языке C:

void choiseSortFunction(double A[], size_t N)
{
    for(size_t tmp_min_index = 0; tmp_min_index < N;
                                  tmp_min_index++) {
        //ищем минимум
        for(size_t k = tmp_min_index + 1; k < N; k++) {
            if (A[k] < A[tmp_min_index]) {
                double min_value = A[k];
                A[k] = A[tmp_min_index];
                A[tmp_min_index] = min_value;
            }
        }
    }
}

Анализ

Предлагаю проанализировать данный алгоритм. Тело внутреннего цикла само по себе выполняется за O(1), то есть не зависит от размера сортируемого массива. Это означает, что для понимания асимптотики алгоритма необходимо посчитать сколько раз выполняется это тело. На первой итерации внешнего цикла имеют место (n — 1) итераций внутреннего цикла. На второй итерации внешнего цикла — (n — 2) итерации внутреннего цикла. Продолжая это рассуждение и далее, мы приходим к следующему:

В процессе вычислений, мы воспользовались сначала свойствами О — нотации, а затем формулой для вычисления суммы арифметической прогрессии.

Для порядка необходимо оценить еще и дополнительную память, которая требуется для выполнения алгоритма. Здесь все гораздо проще: мы выделяли память только для счетчиков цикла и переменной — буфера, позволяющей обменивать 2 элемента массива местами. Поэтому:

В результате анализа мы пришли к тому, что временная сложность алгоритма зависит от размера входного массива квадратично. Поэтому данную сортировку относят к классу квадратичных сортировок. Результат анализа не зависит от содержания массива: он верен в лучшем, в худшем и в среднем случае.

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

Двусторонняя сортировка выбором

Некоторый интерес может представлять оптимизация алгоритма, реализованного выше: во время прохода по неотсортированной части массива можно параллельно с минимальным элементом искать максимальный. Таким образом после итерации можно уменьшать неотсортированную часть массива не на единицу, а на двойку. Асимптотического улучшения алгоритма не происходит, но тем не менее скорость его выполнения может незначительно увеличиться, число сравнений ведь также увеличивается в два раза.

Рекурсивная сортировка выбором

В качестве упражнения можно попробовать написать алгоритм не с использованием цикла, а с использованием рекурсии. На java это может выглядеть следующим образом:

public static int findMin(int[] array, int index){
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}
  
public static void selectionSort(int[] array){
    selectionSort(array, 0);
}
  
public static void selectionSort(int[] array, int left){
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}
  
public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

Итоги

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

---

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

---