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
  • Вводный курс по алгоритмам: от сортировок до машины Тьюринга

  • 0 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