Что такое сортировка и зачем она нужна
Сортировка распределяет элементы в порядке, удобном для работы. Если отсортировать массив чисел в порядке убывания, то первый элемент всегда будет наибольшим, а последний наименьшим. Поэтому желательно хранить информацию упорядочено, чтобы было проще проводить над ней операции.
В данной статье вы научитесь разным техникам сортировок на языке С++. Мы затронем 7 видов:
- Пузырьковая сортировка (Bubble sort);
- Сортировка выбором (Selection sort);
- Сортировка вставками (Insertion sort);
- Быстрая сортировка (Quick sort);
- Сортировка слиянием (Merge sort);
- Сортировка Шелла (Shell sort);
- Сортировка кучей (Heap sort).
Знание этих техник поможет получить работу. На площадке LeetCode содержится более 200 задач, связанных с сортировками. 19 из них входят в топ частых вопросов на собеседованиях по алгоритмам.
1. Пузырьковая сортировка
В пузырьковой сортировке каждый элемент сравнивается со следующим. Если два таких элемента не стоят в нужном порядке, то они меняются между собой местами. В конце каждой итерации (далее называем их проходами) наибольший/наименьший элемент ставится в конец списка.
Прежде чем писать код, разберем сортировку визуально на примере массива из пяти элементов. Отсортируем его в порядке возрастания.
Проход №1
Оранжевым отмечаются элементы, которые нужно поменять местами. Зеленые уже стоят в нужном порядке.
Наибольший элемент — число 48 — оказался в конце списка.
Проход №2
Наибольший элемент уже занимает место в конце массива. Чтобы поставить следующее число по убыванию, можно пройтись лишь до 4-й позиции, а не пятой.
Проход №3
Проход №4
После четвертого прохода получаем отсортированный массив.
Функция сортировки в качестве параметров будет принимать указатель на массив и его размер. Функцией swap() элементы
меняются местами друг с другом:
#include <iostream>
using namespace std;
void bubbleSort(int list[], int listLength)
{
while(listLength--)
{
bool swapped = false;
for(int i = 0; i < listLength; i++)
{
if(list[i] > list[i + 1])
{
swap(list[i], list[i + 1]);
swapped = true;
}
}
if(swapped == false)
break;
}
}
int main()
{
int list[5] = {3,19,8,0,48};
cout << "Input array ..." << endl;
for(int i = 0; i < 5; i++)
cout << list[i] << '\t';
cout << endl;
bubbleSort(list, 5);
cout << "Sorted array ..." << endl;
for(int i = 0; i < 5; i++)
cout << list[i] << '\t';
cout << endl;
}
Сложность в лучшем случае: O(n).
Сложность в среднем случае: O(n2).
Сложность в худшем случае: O(n2).
2. Сортировка выбором
Ищем наименьшее значение в массиве и ставим его на позицию, откуда начали проход. Потом двигаемся на следующую позицию.
Возьмем тот же массив из пяти элементов и отсортируем его.
Проход №1
Зеленым отмечается наименьший элемент в подмассиве — он ставится в начало списка.
Проход №2
Число 4 — наименьшее в оставшейся части массива. Перемещаем четверку на вторую позицию после числа 0.
Проход №3
Проход №4
Напишем функцию поиска наименьшего элемента и используем ее в сортировке:
int findSmallestPosition(int list[], int startPosition, int listLength)
{
int smallestPosition = startPosition;
for(int i = startPosition; i < listLength; i++)
{
if(list[i] < list[smallestPosition])
smallestPosition = i;
}
return smallestPosition;
}
#include <iostream>
using namespace std;
int findSmallestPosition(int list[], int startPosition, int listLength)
{
int smallestPosition = startPosition;
for(int i = startPosition; i < listLength; i++)
{
if(list[i] < list[smallestPosition])
smallestPosition = i;
}
return smallestPosition;
}
void selectionSort(int list[], int listLength)
{
for(int i = 0; i < listLength; i++)
{
int smallestPosition = findSmallestPosition(list, i, listLength);
swap(list[i], list[smallestPosition]);
}
return;
}
int main ()
{
int list[5] = {12, 5, 48, 0, 4};
cout << "Input array ..." << endl;
for(int i = 0; i < 5; i++)
cout << list[i] << '\t';
cout << endl;
selectionSort(list, 5);
cout << "Sorted array ..." << endl;
for(int i = 0; i < 5; i++)
cout << list[i] << '\t';
cout << endl;
}
Сложность в любом случае: O(n2).
3. Сортировка вставками
В сортировке вставками начинаем со второго элемента. Проверяем между собой второй элемент с первым и, если надо, меняем местами. Сравниваем следующую пару элементов и проверяем все пары до нее.
Проход №1. Начинаем со второй позиции.
Число 12 больше 5 — элементы меняются местами.
Проход №2. Начинаем с третьей позиции.
Проверяем вторую и третью позиции. Затем первую и вторую.
Проход №3. Начинаем с четвертой позиции.
Произошло три смены местами.
Проход №4. Начинаем с последней позиции.
Получаем отсортированный массив на выходе.
#include <iostream>
using namespace std;
void insertionSort(int list[], int listLength)
{
for(int i = 1; i < listLength; i++)
{
int j = i - 1;
while(j >= 0 && list[j] > list[j + 1])
{
swap(list[j], list[j + 1]);
cout<<"\ndid";
j--;
}
}
}
int main()
{
int list[8]={3,19,8,0,48,4,5,12};
cout<<"Input array ...\n";
for (int i = 0; i < 8; i++)
{
cout<<list[i]<<"\t";
}
insertionSort(list, 8);
cout<<"\n\nSorted array ... \n";
for (int i = 0; i < 8; i++)
{
cout<<list[i]<<"\t";
}
return 0;
}
Сложность в лучшем случае: O(n).
Сложность в худшем случае: O(n2).
4. Быстрая сортировка
В основе быстрой сортировки лежит стратегия «разделяй и властвуй». Задача разделяется на более мелкие подзадачи. Подзадачи решаются отдельно, а потом решения объединяют. Точно так же, массив разделяется на подмассивы, которые сортируются и затем сливаются в один.
В первую очередь выбираем опорный элемент. Отметим его синим. Все значения больше опорного элемента ставятся после него, остальные — перед.
На иллюстрации массив разделяется по опорному элементу. В полученных массивах также выбираем опорный элемент и разделяем по нему.
Опорным может быть любой элемент. Мы выбираем последний в списке.
Чтобы расположить элементы большие — справа от опорного элемента, а меньшие — слева, будем двигаться от начала списка. Если число будет больше опорного, то оно ставится на его место, а сам опорный на место перед ним.
Напишем функцию разделения partition(),
которая возвращает индекс опорного элемента, и используем ее в сортировке.
int partition(int list[], int start, int pivot)
{
int i = start;
while(i < pivot)
{
if(list[i] > list[pivot] && i == pivot-1)
{
swap(list[i], list[pivot]);
pivot--;
}
else if(list[i] > list[pivot])
{
swap(list[pivot - 1], list[pivot]);
swap(list[i], list[pivot]);
pivot--;
}
else i++;
}
return pivot;
}
#include <iostream>
using namespace std;
int partition(int list[], int start, int pivot)
{
int i = start;
while(i < pivot)
{
if(list[i] > list[pivot] && i == pivot-1)
{
swap(list[i], list[pivot]);
pivot--;
}
else if(list[i] > list[pivot])
{
swap(list[pivot - 1], list[pivot]);
swap(list[i], list[pivot]);
pivot--;
}
else i++;
}
return pivot;
}
void quickSort(int list[], int start, int end)
{
if(start < end)
{
int pivot = partition(list, start, end);
quickSort(list, start, pivot - 1);
quickSort(list, pivot + 1, end);
}
}
int main()
{
int list[6]={2, 12, 5, 48, 0, 4};
cout<<"Input array ...\n";
for (int i = 0; i < 6; i++)
{
cout<<list[i]<<"\t";
}
quickSort(list, 0, 6);
cout<<"\n\nSorted array ... \n";
for (int i = 0; i < 6; i++)
{
cout<<list[i]<<"\t";
}
return 0;
}
Сложность в лучшем случае: O(n*logn).
Сложность в худшем случае: O(n2).
5. Сортировка слиянием
Сортировка слиянием также следует стратегии
«разделяй и властвуй». Разделяем исходный массив на два равных подмассива.
Повторяем сортировку слиянием для этих двух подмассивов и объединяем обратно.
Цикл деления повторяется, пока не останется по одному элементу в массиве. Затем объединяем, пока не образуем полный список.
Алгоритм сортировки состоит из четырех этапов:
- Найти середину массива.
- Сортировать массив от начала до середины.
- Сортировать массив от середины до конца.
- Объединить массив.
void merge(int list[],int start, int end, int mid);
void mergeSort(int list[], int start, int end)
{
int mid;
if (start < end){
mid=(start+end)/2;
mergeSort(list, start, mid);
mergeSort(list, mid+1, end);
merge(list,start,end,mid);
}
}
Для объединения напишем отдельную функцию
merge().
Алгоритм объединения массивов:
- Циклично проходим по двум массивам..
- В объединяемый ставим тот элемент, что меньше.
- Двигаемся дальше, пока не дойдем до конца обоих массивов.
#include <iostream>
using namespace std;
void merge(int list[],int start, int end, int mid);
void mergeSort(int list[], int start, int end)
{
int mid;
if (start < end){
mid=(start+end)/2;
mergeSort(list, start, mid);
mergeSort(list, mid+1, end);
merge(list,start,end,mid);
}
}
void merge(int list[],int start, int end, int mid)
{
int mergedList[8];
int i, j, k;
i = start;
k = start;
j = mid + 1;
while (i <= mid && j <= end) {
if (list[i] < list[j]) {
mergedList[k] = list[i];
k++;
i++;
}
else {
mergedList[k] = list[j];
k++;
j++;
}
}
while (i <= mid) {
mergedList[k] = list[i];
k++;
i++;
}
while (j <= end) {
mergedList[k] = list[j];
k++;
j++;
}
for (i = start; i < k; i++) {
list[i] = mergedList[i];
}
}
int main()
{
int list[8]={3,19,8,0,48,4,5,12};
cout<<"Input array ...\n";
for (int i = 0; i < 8; i++)
{
cout<<list[i]<<"\t";
}
mergeSort(list, 0, 7);
cout<<"\n\nSorted array ... \n";
for (int i = 0; i < 8; i++)
{
cout<<list[i]<<"\t";
}
}
Сложность в любом случае: O(n*logn).
6. Сортировка Шелла
Алгоритм включает в себя сортировку вставками.
Исходный массив размером N разбивается на подмассивы с шагом N/2. Подмассивы
сортируются вставками. Затем вновь разбиваются, но уже с шагом равным N/4. Цикл
повторяется. Производим целочисленное деление шага на два каждую итерацию.
Когда шаг становится равен 1, массив просто сортируется вставками.
У массива размером с 8, первый шаг будет равен 4.
Уменьшаем шаг в два раза. Шаг равен 2.
#include <iostream>
using namespace std;
void shellSort(int list[], int listLength)
{
for(int step = listLength/2; step > 0; step /= 2)
{
for (int i = step; i < listLength; i += 1)
{
int j = i;
while(j >= step && list[j - step] > list[i])
{
swap(list[j], list[j - step]);
j-=step;
cout<<"\ndid";
}
}
}
}
int main()
{
int list[8]={3,19,8,0,48,4,5,12};
cout<<"Input array ...\n";
for (int i = 0; i < 8; i++)
{
cout<<list[i]<<"\t";
}
shellSort(list, 8);
cout<<"\n\nSorted array ... \n";
for (int i = 0; i < 8; i++)
{
cout<<list[i]<<"\t";
}
}
Сложность в лучшем и среднем случае: O(n*logn).
Сложность в худшем случае: O(n2).
7. Сортировка кучей
Исходный массив представляем в виде структуры данных кучи. Куча – это один из типов бинарного дерева.
У кучи есть следующие свойства:
- Родительский узел всегда больше дочерних;
- На i-ом слое 2i узлов, начиная с нуля. То есть на нулевом слое 1 узел, на первом – 2 узла, на втором – 4, и т. д. Правило для всех слоев, кроме последнего;
- Слои заполняются слева направо.
После формирования кучи будем извлекать самый старший узел и ставить на конец массива.
Алгоритм сортировки кучей:
- Формируем бинарное дерево из массива.
- Расставляем узлы в
дереве так, чтобы получилась куча (метод
heapify()). - Верхний элемент помещаем в конец массива.
- Возвращаемся на шаг 2, пока куча не опустеет.
Обращаться к дочерним узлам можно, зная, что дочерние элементы i-го элемента находятся на позициях 2*i + 1 (левый узел) и 2*i + 2 (правый узел).
Изначальная куча:
Индекс с нижним левым узлом определим по
формуле n/2-1, где n – длина массива. Получается 5/2 – 1 = 2 – 1 = 1. С этого
индекса и начинаем операцию heapify(). Сравним дочерние узлы 1-й позиции.
Дочерний узел оказался больше. Меняем местами с родителем.
Теперь проверяем родительский узел от позиции 1.
48 больше 3. Меняем местами.
После смены проверяем все дочерние узлы
элемента, который опустили. То есть для числа 3 проводим heapify(). Так как 3
меньше 19, меняем местами.
Наибольший элемент оказался наверху кучи. Осталось поставить его в конце массива на позицию 4.
Теперь продолжаем сортировать кучу, но последний элемент игнорируем. Для этого просто будем считать, что длина массива уменьшилась на 1.
Повторяем алгоритм сортировки, пока куча не опустеет, и получаем отсортированный массив.
void heapify(int list[], int listLength, int root)
{
int largest = root;
int l = 2*root + 1;
int r = 2*root + 2;
if (l < listLength && list[l] > list[largest])
largest = l;
if (r < listLength && list[r] > list[largest])
largest = r;
if (largest != root)
{
swap(list[root], list[largest]);
heapify(list, listLength, largest);
}
}
#include <iostream>
using namespace std;
void heapify(int list[], int listLength, int root)
{
int largest = root;
int l = 2*root + 1;
int r = 2*root + 2;
if (l < listLength && list[l] > list[largest])
largest = l;
if (r < listLength && list[r] > list[largest])
largest = r;
if (largest != root)
{
swap(list[root], list[largest]);
heapify(list, listLength, largest);
}
}
void heapSort(int list[], int listLength)
{
for(int i = listLength / 2 - 1; i >= 0; i--)
heapify(list, listLength, i);
for(int i = listLength - 1; i >= 0; i--)
{
swap(list[0], list[i]);
heapify(list, i, 0);
}
}
int main()
{
int list[5] = {3,19,8,0,48};
cout<<"Input array ..."<<endl;
for(int i = 0; i < 5; i++)
cout << list[i] << '\t';
cout << endl;
heapSort(list, 5);
cout << "Sorted array"<<endl;
for(int i = 0; i < 5; i++)
cout << list[i] << '\t';
cout << endl;
}
Сложность алгоритма в любом случае: O(n*logn).
В этой статье мы познакомились с семью видами сортировок, рассмотрели их выполнение и написание на С++. Попробуйте применить новые знания в решении задачек на LeetCode или Codeforces. Понимание подобных алгоритмов поможет в будущем пройти собеседование.
Источники:
- https://www.softwaretestinghelp.com/sorting-techniques-in-cpp/
- https://medium.com/@ssbothwell/sorting-algorithms-and-big-o-analysis-332ce7b8e3a1
- https://www.programiz.com/dsa/shell-sort
- https://www.happycoders.eu/algorithms/sorting-algorithms/
Материалы по теме
- Какая сортировка самая быстрая? Тестируем алгоритмы
- Пузырьковая сортировка на JavaScript
- Вводный курс по алгоритмам: от сортировок до машины Тьюринга
Мне сложно разобраться самостоятельно, что делать?
Алгоритмы и структуры данных действительно непростая тема для самостоятельного изучения: не у кого спросить и что-то уточнить. Поэтому мы запустили курс «Алгоритмы и структуры данных», на котором в формате еженедельных вебинаров вы:
- изучите сленг, на котором говорят все разработчики независимо от языка программирования: язык алгоритмов и структур данных;
- научитесь применять алгоритмы и структуры данных при разработке программ;
- подготовитесь к техническому собеседованию и продвинутой разработке.
Курс подходит как junior, так и middle-разработчикам.
Комментарии