➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями
В этой статье продемонстрируем на иллюстрациях, как работают алгоритмы сортировки: от простейшей пузырьковой до сложной древовидной кучи. Также определим сложность худших и лучших случаев, а код напишем на С++. Сортировка распределяет элементы в порядке, удобном для работы. Если отсортировать массив чисел в порядке убывания, то первый элемент всегда будет наибольшим, а последний наименьшим. Поэтому желательно хранить информацию упорядочено, чтобы было проще проводить над ней операции. В данной статье вы научитесь разным техникам сортировок на языке С++. Мы затронем 7 видов: Знание этих техник поможет получить работу. На площадке LeetCode содержится более 200 задач, связанных с сортировками. 19 из них входят в топ частых вопросов на собеседованиях по алгоритмам. В пузырьковой сортировке каждый элемент сравнивается со следующим. Если два таких элемента не стоят в нужном порядке, то они меняются между собой местами. В конце каждой итерации (далее называем их проходами) наибольший/наименьший элемент ставится в конец списка. Прежде чем писать код, разберем сортировку визуально на примере массива из пяти элементов. Отсортируем его в порядке возрастания. Пузырьковая сортировка Проход №1 Оранжевым отмечаются элементы, которые нужно поменять местами. Зеленые уже стоят в нужном порядке. Пузырьковая сортировка Наибольший элемент — число 48 — оказался в конце списка. Проход №2 Пузырьковая сортировка Наибольший элемент уже занимает место в конце массива. Чтобы поставить следующее число по убыванию, можно пройтись лишь до 4-й позиции, а не пятой. Проход №3 Пузырьковая сортировка Проход №4 Пузырьковая сортировка После четвертого прохода получаем отсортированный массив. Функция сортировки в качестве параметров будет принимать указатель на массив и его размер. Функцией Сложность в лучшем случае: O(n). Сложность в среднем случае: O(n2). Сложность в худшем случае: O(n2). Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека C/C++ разработчика» Интересно, перейти к каналу Ищем наименьшее значение в массиве и ставим его на позицию, откуда начали проход. Потом двигаемся на следующую позицию. Возьмем тот же массив из пяти элементов и отсортируем его. Проход №1 Сортировка выбором Зеленым отмечается наименьший элемент в подмассиве — он ставится в начало списка. Проход №2 Число 4 — наименьшее в оставшейся части массива. Перемещаем четверку на вторую позицию после числа 0. Сортировка выбором Проход №3 Сортировка выбором Проход №4 Сортировка выбором Напишем функцию поиска наименьшего элемента и используем ее в сортировке: findSmallestPosition.cpp Сложность в любом случае: O(n2). В сортировке вставками начинаем со второго элемента. Проверяем между собой второй элемент с первым и, если надо, меняем местами. Сравниваем следующую пару элементов и проверяем все пары до нее. Проход №1. Начинаем со второй позиции. Сортировка вставками Число 12 больше 5 — элементы меняются местами. Проход №2. Начинаем с третьей позиции. Проверяем вторую и третью позиции. Затем первую и вторую. Сортировка вставками Проход №3. Начинаем с четвертой позиции. Сортировка вставками Произошло три смены местами. Проход №4. Начинаем с последней позиции. Сортировка вставками Получаем отсортированный массив на выходе. Сложность в лучшем случае: O(n). Сложность в худшем случае: O(n2). В основе быстрой сортировки лежит стратегия «разделяй и властвуй». Задача разделяется на более мелкие подзадачи. Подзадачи решаются отдельно, а потом решения объединяют. Точно так же, массив разделяется на подмассивы, которые сортируются и затем сливаются в один. В первую очередь выбираем опорный элемент. Отметим его синим. Все значения больше опорного элемента ставятся после него, остальные — перед. Быстрая сортировка На иллюстрации массив разделяется по опорному элементу. В полученных массивах также выбираем опорный элемент и разделяем по нему. Опорным может быть любой элемент. Мы выбираем последний в списке. Чтобы расположить элементы большие — справа от опорного элемента, а меньшие — слева, будем двигаться от начала списка. Если число будет больше опорного, то оно ставится на его место, а сам опорный на место перед ним. Быстрая сортировка Напишем функцию разделения partition.cpp Сложность в лучшем случае: O(n*logn). Сложность в худшем случае: O(n2). Сортировка слиянием также следует стратегии «разделяй и властвуй». Разделяем исходный массив на два равных подмассива. Повторяем сортировку слиянием для этих двух подмассивов и объединяем обратно. Быстрая сортировка Цикл деления повторяется, пока не останется по одному элементу в массиве. Затем объединяем, пока не образуем полный список. Алгоритм сортировки состоит из четырех этапов: Для объединения напишем отдельную функцию Алгоритм объединения массивов: Сложность в любом случае: O(n*logn). Алгоритм включает в себя сортировку вставками. Исходный массив размером У массива размером с 8, первый шаг будет равен 4. Сортировка Шелла Уменьшаем шаг в два раза. Шаг равен 2. Сортировка Шелла Сложность в лучшем и среднем случае: O(n*logn). Сложность в худшем случае: O(n2). Исходный массив представляем в виде структуры данных кучи. Куча – это один из типов бинарного дерева. У кучи есть следующие свойства: После формирования кучи будем извлекать самый старший узел и ставить на конец массива. Алгоритм сортировки кучей: Обращаться к дочерним узлам можно, зная, что дочерние элементы i-го элемента находятся на позициях 2*i + 1 (левый узел) и 2*i + 2 (правый узел). Изначальная куча: Сортировка кучей Индекс с нижним левым узлом определим по формуле Сортировка кучей Дочерний узел оказался больше. Меняем местами с родителем. Сортировка кучей Теперь проверяем родительский узел от позиции 1. Сортировка кучей 48 больше 3. Меняем местами. Сортировка кучей После смены проверяем все дочерние узлы элемента, который опустили. То есть для числа 3 проводим Сортировка кучей Наибольший элемент оказался наверху кучи. Осталось поставить его в конце массива на позицию 4. Сортировка кучей Теперь продолжаем сортировать кучу, но последний элемент игнорируем. Для этого просто будем считать, что длина массива уменьшилась на 1. Сортировка кучей Повторяем алгоритм сортировки, пока куча не опустеет, и получаем отсортированный массив. Сортировка кучей heapify.cpp Сложность алгоритма в любом случае: O(n*logn). *** В этой статье мы познакомились с семью видами сортировок, рассмотрели их выполнение и написание на С++. Попробуйте применить новые знания в решении задачек на LeetCode или Codeforces. Понимание подобных алгоритмов поможет в будущем пройти собеседование. Источники: *** 
Что такое сортировка и зачем она нужна
1. Пузырьковая сортировка
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; } 2. Сортировка выбором
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; } 3. Сортировка вставками
#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; } 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<<"nnSorted array ... n"; for (int i = 0; i < 6; i++) { cout<<list[i]<<"t"; } return 0; } 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<<"nnSorted array ... n"; for (int i = 0; i < 8; i++) { cout<<list[i]<<"t"; } } 6. Сортировка Шелла
N разбивается на подмассивы с шагом N/2. Подмассивы сортируются вставками. Затем вновь разбиваются, но уже с шагом равным N/4. Цикл повторяется. Производим целочисленное деление шага на два каждую итерацию. Когда шаг становится равен 1, массив просто сортируется вставками.
#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"; } } 7. Сортировка кучей
heapify()).n/2-1, где n – длина массива. Получается 5/2 – 1 = 2 – 1 = 1. С этого индекса и начинаем операцию heapify(). Сравним дочерние узлы 1-й позиции.heapify(). Так как 3 меньше 19, меняем местами.
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; } Материалы по теме
- 3 views
- 0 Comment