«Я придумал однопроходный алгоритм сортировки O(n), который я назвал сортировкой Сталина. Вы перебираете список элементов, проверяя, расположены ли они по порядку. Любой элемент, вышедший из строя, удаляется. В конце концов, у вас есть отсортированный список».

-Неизвестно

Введение

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

Например:

Студенты Хогвартса распределяются по разным факультетам в зависимости от их личности.

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

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

«Если вы знаете правителей, вы знаете королевство».

Прежде чем погрузиться в алгоритмы, давайте оценим встроенную функцию, предоставляемую C++ STL.

Функция Сортировать().

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

Синтаксис использования функции:

сортировать (сначала, по последнему);

Здесь
first — индекс (указатель) первого элемента в сортируемом диапазоне.
last — индекс (указатель) последнего элемента в сортируемом диапазоне.

Временная сложность функции сортировки составляет N*log2 (N), где N =последний — первый.

Итак, если вы конкурентоспособный программист, просто напишите одну строку кода, и все готово.

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

Что ж, будем готовиться. Пусть худшее придет😈.

Наиболее распространенными и обязательными алгоритмами сортировки являются:

  1. Пузырьковая сортировка
  2. Сортировка выбором
  3. Сортировка вставками
  4. Сортировка слиянием
  5. Быстрая сортировка

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

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

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

Во второй итерации мы проходим от начала до элемента в array[end-2] и так далее. После n² итераций массив сортируется.

Выполнение

Данный код сортирует массив в порядке возрастания:

// Bubble sort function in C++
void bubbleSort(int array[], int size) {
 // loop to access each array element
 for (int step = 0; step < size; ++step) {
 
     // loop to compare array elements
     for (int i = 0; i < size — step; ++i) {
     // compare two adjacent elements

        if (array[i] > array[i + 1]) {
            int temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }
     }
   }
}

Анализ

Поскольку есть два вложенных цикла, временная сложность пузырьковой сортировки составляет O(n²).

пространственная сложность пузырьковой сортировки составляет O(1).

Оптимизация

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

Это можно улучшить, используя логический флаг и изначально установив для него значение false. Мы можем проверить, что если свопы не производились, то это означает, что массив уже отсортирован, и флаг будет установлен в значение true. Если это условие выполнено, мы вырвемся из циклов и вернем массив.

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

В этом алгоритме есть две части массива:

а. Начальная часть, которая отсортирована.

б. Оставшаяся часть, которая еще не отсортирована.

Мы проходим в несортированную часть (полный массив в начале) и находим минимальный элемент. Затем мы меняем минимальный элемент местами с первым элементом несортированного массива. Минимальный элемент становится частью отсортированного массива, а длина несортированной части уменьшается на единицу.

Выполнение

Данный код сортирует массив в порядке возрастания:

// Selection sort function in C++
// function to swap the the position of two elements
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}
void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {
      // Select the minimum element in each loop.
      if (array[i] < array[min_idx])
        min_idx = i;
    }
// put min at the correct position
    swap(&array[min_idx], &array[step]);
  }
}
-4,1,3,5

Анализ

Поскольку есть два вложенных цикла, временная сложность сортировки выбором составляет O(n²).

пространственная сложность сортировки выбором составляет O(1).

3. Сортировка вставками

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

Мы предполагаем, что первая карта уже отсортирована, тогда мы выбираем несортированную карту. Если неотсортированная карта больше, чем карта в руке, она кладется справа, в противном случае — слева. Таким же образом берутся и другие несортированные карты и кладутся на свои места.

При аналогичном подходе числа сортируются вставками.

Работающий

Отсортируем заданный массив:

Шаг 1:

Будем считать, что первый элемент (3) уже отсортирован. Таким образом, сохраните второй элемент(5) в переменной key.

Мы сравниваем ключ(5) с отсортированным массивом и помещаем ключ в нужное место.

Шаг 2:

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

Шаг 3:

Теперь у нас остался только один элемент (-4). Обновляем нашу ключевую переменную и начинаем сравнивать. Аналогично шагу 2 мы сравниваем элементы и получаем отсортированный массив.

Конечным результатом будет:

-4,1,3,5

Выполнение

В следующем коде показана реализация сортировки вставками:

// Insertion sort in C++
void insertionSort(int array[], int size) {
  for (int step = 1; step < size; step++) {
    int key = array[step];
    int j = step - 1;
// Compare key with each element on the left of it until an element //smaller than it is found.
    while (key < array[j] && j >= 0) {
      array[j + 1] = array[j];
      --j;
    }
    array[j + 1] = key;
  }
}

Анализ

Временная сложность сортировки вставками составляет O(n²).

Объемная сложность сортировки вставками составляет O(n).

Сравнение

Все вышеперечисленные алгоритмы имеют временную сложность O(n²) и пространственную сложность O(1). Но чем они лучше других? Давайте посмотрим на некоторые заметные различия.

Пузырьковая сортировка

Преимущества:

  1. Для оптимизированного подхода временная сложность в лучшем случае составляет O (n).
  2. Используя оптимизированный подход, он может обнаружить уже отсортированный массив на первом проходе с временной сложностью O(N).
  3. Это стабильная сортировка: не изменяет относительный порядок элементов с одинаковыми ключами.

Недостатки:

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

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

Преимущества:

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

Недостатки:

  1. Временная сложность сортировки выбором составляет O(n²) без наилучшего сценария.

Сортировка вставками

Преимущества:

  1. Временная сложность в лучшем случае составляет O (n), когда массив уже отсортирован частично отсортированным массивом.
  2. Это стабильный метод сортировки на месте.
  3. Меньшее количество обменов, чем пузырьковая сортировка.

Недостатки:

  1. Для больших значений N сортировка вставками неэффективна.

Теперь давайте поговорим о некоторых эффективных методах сортировки.

4. Сортировка слиянием

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

Работающий:

Рассмотрим следующий несортированный массив:

Шаг 1:

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

Шаг 2 :

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

Массив длины один не может быть разделен. Таким образом, мы объединим два подмассива.

Шаг 3:

Выберите два подмассива (207) и (339) и сравните их. Выберите минимум из двух. Добавить выбранный в отсортированный массив. Поскольку первый список стал пустым, теперь мы заполним другой список отсортированным списком. Отсортированный подмассив будет выглядеть так:

Шаг 4:

Теперь, поскольку длина массива с элементом 429 равна единице, его нельзя разделить. Таким образом, мы объединим его с отсортированным массивом.

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

Снова выберите начало каждого списка (339 и 429). Найдите их минимум (339), вставьте его в отсортированный список и переместите указатель вперед. Так как первый список теперь стал пустым, мы будем вставлять все элементы второго списка в отсортированный список.

Шаг 5:

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

Выполнение:

void merge(int left[], int ls,int rs, int right[], int * arr){
    int k=0,i=0,j=0;
    while(i<ls and j<rs){
        if(left[i]<=right[j]){
            arr[k] = left[i];
            i++;
        }else{
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    while(i<ls){
        arr[k] = left[i];
        i++;k++;
    }
     while(j<ls){
        arr[k] = right[j];
        j++;k++;
    }
}
void mergeSort(int * arr, int n){
    if(n<2){
        return;
    }
    int mid = n/2;
    int ls, rs;
    if(n%2==0){
        ls = mid;
    }else{
        ls = mid + 1;
    }
    rs = mid;
    int left[ls];
    int right[rs];
    for(int i=0; i<ls ;i++){
         left[i] = arr[i];
    }
    int j=0;
    for(int i=ls ;i<n;i++){
        right[j] = arr[i];
        j++;
    }
    mergeSort(left,ls);
    mergeSort(right,rs);
    merge(left,ls, rs, right,arr);
}

Анализ:

Временная сложность сортировки слиянием составляет θ(nLogn) во всех трех случаях (наихудшем, среднем и лучшем), поскольку сортировка слиянием всегда делит массив на две половины и занимает линейное время, чтобы объединить две половины.

пространственная сложность сортировки слиянием составляет O(n).

5. Быстрая сортировка

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

Работающий:

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

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

Выполнение:

 //Taking last element as the pivot and putting the smaller elements
 //than the pivot on its left and the elements larger than it on its 
 //right side
int partition(int *arr, int start, int end){
    int pivot = arr[end];
    int pIndex = start;
    for(int i=start;i<end;i++){
        if(arr[i]<=pivot){
        swap(arr[i],arr[pIndex]);
        pIndex+=1;
        }
    }
    swap(arr[end], arr[pIndex]);
    return pIndex;
}

//function to sort the elements using quicksort

void quickSort(int *arr, int start, int end){
    if(start<end){
        int pIndex = partition(arr,start,end);
        quickSort(arr,start,pIndex-1);
        quickSort(arr,pIndex+1,end);
    }
}

Анализ:

Время, затраченное QuickSort, может быть записано как:

T(n) = T(k) + T(n-k-1) + θ(n)

T(k) + T(n-k-1) — для рекурсивных вызовов, а θ(n) — для статистической суммы.

Средняя временная сложность QuickSort составляет O (N log N). Подробный анализ временной сложности QuickSort можно найти здесь.

Пространственная сложность QuickSort составляет O (1).

Сравнение

Теперь давайте сравним два рассмотренных нами эффективных подхода: сортировку слиянием и быструю сортировку.

В следующей таблице приведено сравнение двух алгоритмов сортировки.

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