Share This
Связаться со мной
Крути в низ
Categories
//➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

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

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 74efb46 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

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

В данной статье вы научитесь разным техникам сортировок на языке С++. Мы затронем 7 видов:

  • Пузырьковая сортировка (Bubble sort);
  • Сортировка выбором (Selection sort);
  • Сортировка вставками (Insertion sort);
  • Быстрая сортировка (Quick sort);
  • Сортировка слиянием (Merge sort);
  • Сортировка Шелла (Shell sort);
  • Сортировка кучей (Heap sort).

Знание этих техник поможет получить работу. На площадке LeetCode содержится более 200 задач, связанных с сортировками. 19 из них входят в топ частых вопросов на собеседованиях по алгоритмам.

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

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

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

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 426f2f7 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Проход №1

Оранжевым отмечаются элементы, которые нужно поменять местами. Зеленые уже стоят в нужном порядке.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami e051299 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Наибольший элемент — число 48 — оказался в конце списка.

Проход №2

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 2e61ca6 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Наибольший элемент уже занимает место в конце массива. Чтобы поставить следующее число по убыванию, можно пройтись лишь до 4-й позиции, а не пятой.

Проход №3

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 946fa2b - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Проход №4

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 6d88ef6 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

После четвертого прохода получаем отсортированный массив.

Функция сортировки в качестве параметров будет принимать указатель на массив и его размер. Функцией 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++ разработчика» Интересно, перейти к каналу

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

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

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

Проход №1

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 76d1683 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

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

Проход №2

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

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 930dfba - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Проход №3

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami fe7122b - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Проход №4

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 8c89947 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

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

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. Начинаем со второй позиции.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 1d2ccc6 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Число 12 больше 5 — элементы меняются местами.

Проход №2. Начинаем с третьей позиции.

Проверяем вторую и третью позиции. Затем первую и вторую.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 81a68ba - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Проход №3. Начинаем с четвертой позиции.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 437fbeb - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Произошло три смены местами.

Проход №4. Начинаем с последней позиции.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 4061bd4 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Получаем отсортированный массив на выходе.

         #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<<"nnSorted array ... n"; 	for (int i = 0; i < 8; i++) 	{ 	   cout<<list[i]<<"t"; 	} 	 	return 0; }     

Сложность в лучшем случае: O(n).

Сложность в худшем случае: O(n2).

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

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

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

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 5a1b0f5 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

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

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

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

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami feec780 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 8af8baf - ➕ ➕ 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<<"nnSorted array ... n"; 	for (int i = 0; i < 6; i++) 	{ 	   cout<<list[i]<<"t"; 	} 	 	return 0; }     

Сложность в лучшем случае: O(n*logn).

Сложность в худшем случае: O(n2).

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

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

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 0b3ed0d - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

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

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

  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<<"nnSorted 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.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami b5f4743 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

Сортировка Шелла

Уменьшаем шаг в два раза. Шаг равен 2.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami d4764c0 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

Сортировка Шелла

         #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<<"nnSorted 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 (правый узел).

Изначальная куча:

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami b099432 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Индекс с нижним левым узлом определим по формуле n/2-1, где n – длина массива. Получается 5/2 – 1 = 2 – 1 = 1. С этого индекса и начинаем операцию heapify(). Сравним дочерние узлы 1-й позиции.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 9b10a39 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Дочерний узел оказался больше. Меняем местами с родителем.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 0967836 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Теперь проверяем родительский узел от позиции 1.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 1d6c5ec - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

48 больше 3. Меняем местами.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 55be419 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

После смены проверяем все дочерние узлы элемента, который опустили. То есть для числа 3 проводим heapify(). Так как 3 меньше 19, меняем местами.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 93dd384 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Наибольший элемент оказался наверху кучи. Осталось поставить его в конце массива на позицию 4.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami b133bda - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

Теперь продолжаем сортировать кучу, но последний элемент игнорируем. Для этого просто будем считать, что длина массива уменьшилась на 1.

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 78e671a - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

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

➕ 7 sposobov sortirovki massivov na primere s s illjustracijami 624eb50 - ➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

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

***

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

  • Какая сортировка самая быстрая? Тестируем алгоритмы
  • Пузырьковая сортировка на JavaScript
  • Вводный курс по алгоритмам: от сортировок до машины Тьюринга

  • 2 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Свежие комментарии

    Рубрики

    About Author 01.

    blank
    Roman Spiridonov

    Моя специальность - Back-end Developer, Software Engineer Python. Мне 39 лет, я работаю в области информационных технологий более 5 лет. Опыт программирования на Python более 3 лет. На Django более 2 лет.

    Categories 05.

    © Speccy 2022 / All rights reserved

    Связаться со мной
    Close