FrontProg 20 апреля 2022

➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Что такое сортировка и зачем она нужна

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

В данной статье вы научитесь разным техникам сортировок на языке С++. Мы затронем 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).

➕➕ C/C++
Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека C/C++ разработчика»
➕➕🎓 Библиотека C++ для собеса
Подтянуть свои знания по Go вы можете на нашем телеграм-канале «Библиотека C++ для собеса»
➕➕🧩 Библиотека задач по C++
Интересные задачи по Go для практики можно найти на нашем телеграм-канале «Библиотека задач по C++»

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

Ищем наименьшее значение в массиве и ставим его на позицию, откуда начали проход. Потом двигаемся на следующую позицию.

Возьмем тот же массив из пяти элементов и отсортируем его.

Проход №1

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

Зеленым отмечается наименьший элемент в подмассиве — он ставится в начало списка.

Проход №2

Число 4 — наименьшее в оставшейся части массива. Перемещаем четверку на вторую позицию после числа 0.

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

Проход №3

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

Проход №4

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

Напишем функцию поиска наименьшего элемента и используем ее в сортировке:

findSmallestPosition.cpp
        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. Быстрая сортировка

В основе быстрой сортировки лежит стратегия «разделяй и властвуй». Задача разделяется на более мелкие подзадачи. Подзадачи решаются отдельно, а потом решения объединяют. Точно так же, массив разделяется на подмассивы, которые сортируются и затем сливаются в один.

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

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

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

Опорным может быть любой элемент. Мы выбираем последний в списке.

Чтобы расположить элементы большие — справа от опорного элемента, а меньшие — слева, будем двигаться от начала списка. Если число будет больше опорного, то оно ставится на его место, а сам опорный на место перед ним.

Быстрая сортировка
Быстрая сортировка
➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

Напишем функцию разделения partition(), которая возвращает индекс опорного элемента, и используем ее в сортировке.

partition.cpp
        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. Сортировка слиянием

Сортировка слиянием также следует стратегии «разделяй и властвуй». Разделяем исходный массив на два равных подмассива. Повторяем сортировку слиянием для этих двух подмассивов и объединяем обратно.

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

Цикл деления повторяется, пока не останется по одному элементу в массиве. Затем объединяем, пока не образуем полный список.

Алгоритм сортировки состоит из четырех этапов:

  1. Найти середину массива.
  2. Сортировать массив от начала до середины.
  3. Сортировать массив от середины до конца.
  4. Объединить массив.
        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().

Алгоритм объединения массивов:

  1. Циклично проходим по двум массивам..
  2. В объединяемый ставим тот элемент, что меньше.
  3. Двигаемся дальше, пока не дойдем до конца обоих массивов.
        #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, и т. д. Правило для всех слоев, кроме последнего;
  • Слои заполняются слева направо.

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

Алгоритм сортировки кучей:

  1. Формируем бинарное дерево из массива.
  2. Расставляем узлы в дереве так, чтобы получилась куча (метод heapify()).
  3. Верхний элемент помещаем в конец массива.
  4. Возвращаемся на шаг 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.

Сортировка кучей
Сортировка кучей

Повторяем алгоритм сортировки, пока куча не опустеет, и получаем отсортированный массив.

Сортировка кучей
Сортировка кучей
heapify.cpp
        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/
***

Материалы по теме

***

Мне сложно разобраться самостоятельно, что делать?

Алгоритмы и структуры данных действительно непростая тема для самостоятельного изучения: не у кого спросить и что-то уточнить. Поэтому мы запустили курс «Алгоритмы и структуры данных», на котором в формате еженедельных вебинаров вы:

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

Курс подходит как junior, так и middle-разработчикам.

МЕРОПРИЯТИЯ

Комментарии

ВАКАНСИИ

Добавить вакансию
Разработчик C++
Москва, по итогам собеседования

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ