Алгоритмы сортировки
Сортировка - это процесс упорядочивания элементов в списке. Вот как это работает:
У нас есть список, и мы выбираем одно поле в каждом элементе списка, которое будет служить “ключом”. Этот ключ должен быть чем-то, что мы можем сравнить, например, числом или словом.
Наша цель - переставить элементы списка так, чтобы ключи были в порядке возрастания или убывания.
Есть два основных типа сортировки:
- Внутренняя сортировка: Здесь мы предполагаем, что все данные находятся в оперативной памяти компьютера. Наша цель - сделать как можно меньше шагов, чтобы отсортировать список.
- Внешняя сортировка: Здесь данные хранятся где-то вне оперативной памяти, например, на жестком диске. Наша цель - сделать как можно меньше обращений к этому хранилищу данных, потому что это обычно занимает много времени.
Существуют разные методы сортировки, которые подходят для разных ситуаций. Например, есть простые методы, такие как обмен, вставки и выбор. Есть и более сложные методы, такие как сортировка Шелла, пирамидальная сортировка и быстрая сортировка. Есть даже специальные методы, такие как подсчет, которые работают только в определенных ситуациях.
Этот метод подразумевает, что все данные, которые мы хотим отсортировать, являются целыми числами в диапазоне от 0 до k. Основная идея состоит в том, чтобы для каждого числа x определить, сколько чисел меньше x. Зная это, мы можем поместить число x на правильное место в отсортированном списке.
void countSort(int* arr, int n) { int min = arr[0], max = arr[0]; for(int i = 1; i < n; i++) { if(arr[i] < min) min = arr[i]; if(arr[i] > max) max = arr[i]; } int range = max - min + 1; int* countArr = new int[n]; for(int i = 0; i < n; i++) { countArr[arr[i] - min]++; } for(int i = 1; i < range; i++) { countArr[i] += countArr[i - 1]; } int* sortedArr = new int[n]; for(int i = n - 1; i >= 0; i--) { int pos = countArr[arr[i] - min] - 1; sortedArr[pos] = arr[i]; countArr[arr[i] - min]--; } for(int i = 0; i < n; i++) arr[i] = sortedArr[i]; }
Метод прямого включения (вставки)
При этом методе мы делим список на две части: отсортированную и неотсортированную. В начале отсортированной частью считается только первый элемент. Затем мы берем следующий элемент из неотсортированной части и вставляем его на правильное место в отсортированной части.
void insertionSort(int* arr, int n) { for(int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while(j >= 0 && arr[i] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }
Максимальное количество сравнений ключей с i при i-ом проходе равно i - 1. Если предположить, что все перестановки из n элементов равновероятны, то среднее число сравнений равно i/2. Число перестановок M(i) = C(i) + 2. Этот алгоритм работает лучше всего, когда исходный список уже отсортирован, и хуже всего, когда элементы расположены в обратном порядке.
Этот метод сортировки работает так: мы делим массив на две части - отсортированную и неотсортированную. В начале считаем, что отсортированная часть пуста, а все элементы массива находятся в неотсортированной части. Затем мы ищем наименьший элемент в неотсортированной части и перемещаем его в конец отсортированной части. Этот процесс повторяется, пока весь массив не будет отсортирован.
void selectionSort(int* arr, int n) { for(int i = 0; i < n – 1; i++) { int minIndex = i; for(int j = i + 1; j < n ; i++) { if(arr[j] < arr[minIndex]) minIndex = j; } swap(arr[i], arr[minIndex]); } }
Пузырьковая сортировка - это еще один простой метод сортировки. Он работает так: на каждом шаге мы сравниваем два соседних элемента и меняем их местами, если они расположены в неправильном порядке. Этот процесс повторяется, пока весь массив не будет отсортирован.
void bubbleSort(int* arr, int n) { for(int i = 0; i < n - 1; i++) { for(int j = 0; j < n - i - 1; j++) { if(arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } }
Оба этих метода имеют свои преимущества и недостатки. Метод прямого выбора обычно работает быстрее, если элементы в начале массива уже почти отсортированы. Пузырьковая сортировка, с другой стороны, может быть более эффективной для больших массивов, но она может быть медленной, если массив изначально почти отсортирован. Если на каком-то проходе не произошло ни одного обмена, это означает, что список уже отсортирован, и алгоритм может быть завершен раньше времени. Это свойство делает пузырьковую сортировку идеальной для списков, которые уже почти отсортированы.
Шейкерная сортировка(сортировка перемещиванием) – Алгоритм сортировки, которая улучшает сортировку пузырьком, проходя по массиву в обоих направлениях. Это позволяет уменьшить количество проходов, необходимых для полной сортировки массива. На каждом проходе справа налево минимальный элемент всплывает на первую позицию, а на проходе слева направо максимальный элемент тонет на последнюю позицию. Процесс повторяется, пока границы рабочей части массива не сойдутся. Число сравнений пузырька = (n^2 – n) / 2 . Шейкерная сортировка лучше пузырьковой за счет того, что шейкерная сортировка проходит с двух сторон, а пузырьковая только с одной стороны
void shakerSort(int* arr, int size) { int left = 0, right = size - 1; bool swapped = false; while(left < right) { for(int i = left; i < right; i++) { if(arr[i] > arr[i + 1]) { swap(arr[i], arr[i + 1]); swapped = true; } } right--; for(int i = right; i > left; i--) { if(arr[i] < arr[i - 1]) { swap(arr[i], arr[i - 1]); swapped = true; } } left++; if(!swapped) break; swapped = false; } }