Сортировка – важный аспект программирования. Отсортированные данные позволяют быстрее и эффективнее работать с данными.
Для описания эффективности алгоритма мы использовали два основных критерия: расход памяти и асимптотическую временную сложность (О-нотация).
С асимптотической сложностью можете ознакомиться в другой нашей статье.
Bubble Sort
Сортировка пузырьком считается учебной и самой легкой в понимании. В её основе лежит поочередное сравнение соседних элементов. Если они стоят в неверном порядке, их меняют местами. Так, наибольший элемент "всплывает" наверх с каждым проходом.
Это самый медленный из алгоритмов с квадратичной скоростью O(n2). Однако он самый легкий в реализации и не использует много памяти.
//функцию Swap мы будем в нескольких алгоритмах. Её реализация везде идентична.
private static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void BubbleSort (int[] data)
{
int i, j;
for (j = data.Length - 1; j > 0; j--) {
for (i=0; i<j; i++) {
if (data [i] > data [i + 1])
swap (data, i, i + 1);
}
}
}
Insertion Sort
Сортировка вставками – алгоритм квадратичной сложности и тоже не злоупотребляет дополнительной памятью. Тем не менее, его средняя скорость выполнения примерно вдвое выше, чем у пузырьков.
Принцип прост. Все элементы просматриваются по очереди. Просмотренные элементы считаются отсортированными и каждый новый ставится на нужное место в ранее упорядоченной последовательности.
public static void InsertionSort (int[] data)
{
int i, j;
for (j = 1; j < data.Length; j++) {
for (i = j; i > 0 && data[i] < data[i-1]; i--)
Swap(data, i, i - 1);
}
}
Shell Sort
Сортировка Шелла – это та же сортировка вставками, но с предварительными грубыми проходами. Принцип похожий, но сравнение идет не соседних элементов, а нескольких в определенном интервале. Это позволяет оптимизировать перебор.
private static void ShellSort(int[] data)
{
int step = data.Length / 2;
int temp;
while (step > 0)
{
for (int i = 0; i + step < data.Length; i++)
{
int j = i + step;
temp = data[j];
while (j - step >= 0 && temp < data[j - step])
{
data[j] = data[j - step];
j = j - step;
}
data[j] = temp;
}
step = step / 2;
}
}
Quick Sort
Быстрая сортировка или сортировка Хоара является одной из самых эффективных: на случайных данных достигает производительности O(n log(n)). Однако алгоритм является рекурсивным, поэтому использует много дополнительной памяти.
Принцип интересней прошлых примеров. Сначала мы определяем опорную точку в последовательности. Теоретически это может быть любой элемент, на практике выбирают либо медианный, либо средний. Потом перераспределяем так, чтобы все элементы меньше опорного были слева, а больше – справа. Применяем алгоритм рекурсивно к обеим половинам, пока в них больше одного элемента.
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[left];
while (true)
{
while (arr[left] < pivot)
left++;
while (arr[right] > pivot)
right--;
if (left < right)
{
if (arr[left] == arr[right]) return right;
Swap(arr, left, right);
}
else
{
return right;
}
}
}
private static void QuickSort(int[] arr, int left, int right)
{
if (left < right)
{
int pivot = Partition(arr, left, right);
if (pivot > 1)
QuickSort(arr, left, pivot - 1);
if (pivot + 1 < right)
QuickSort(arr, pivot + 1, right);
}
}
Merge Sort
Сортировка слиянием похожа по принципу на быструю и тоже является рекурсивной. Скорость алгоритма O(n log(n)) и требует дополнительной памяти в размере исходной последовательности.
На мой взгляд, слияние проще для понимания, чем сортировка Хоара. Сначала мы разбиваем исходную последовательность пополам, и сортируем каждую половину рекурсивно до тех пор, пока в каждой половине не останется по одному элементу. Затем осуществляем их слияние.
private static int[] MergeSort(int[] array)
{
if (array.Length == 1)
return array;
int middle = array.Length / 2;
//для лаконичности используем linq
return Merge(MergeSort(array.Take(middle).ToArray()), MergeSort(array.Skip(middle).ToArray()));
}
private static int[] Merge(int[] arr1, int[] arr2)
{
int ptr1 = 0, ptr2 = 0;
int[] merged = new int[arr1.Length + arr2.Length];
for (int i = 0; i < merged.Length; ++i)
{
if (ptr1 < arr1.Length && ptr2 < arr2.Length)
merged[i] = arr1[ptr1] > arr2[ptr2] ? arr2[ptr2++] : arr1[ptr1++];
else
merged[i] = ptr2 < arr2.Length ? arr2[ptr2++] : arr1[ptr1++];
}
return merged;
}
HeapSort
Пирамидальная сортировка или сортировка кучей тоже имеет асимптотическую сложность O(n log(n)), но на практике оказывается медленнее предыдущих двух и применяется достаточно редко, хоть и не требует дополнительного выделения памяти.
Алгоритм интересен своим подходом. Принцип похож на сортировку вставками. Только мы не ищем место элемента в массиве, а просеиваем его в двоичную кучу (Heap).
Чтобы понять, почему это ускоряет процесс с n до log(n), давайте разберем, что это за структура данных. По сути, куча – бинарное дерево, которое удовлетворяет дополнительным условиям:
- Дерево сбалансировано. Т. е. все листья имеют глубину h или h-1, где h – это глубина дерева.
- Уровень h заполнен слева направо.
- Каждый элемент должен быть меньше или равен своего родителя, в корне – максимальный элемент.
Готовая пирамида выглядит так:
static void HeapSort(int[] data)
{
var length = data.Length;
for (int i = length / 2 - 1; i >= 0; i--)
{
Heapify(data, length, i);
}
for (int i = length - 1; i >= 0; i--)
{
int temp = data[0];
data[0] = data[i];
data[i] = temp;
Heapify(data, i, 0);
}
}
/* Пирамиду можно строить по разному, самый оптимальный вариант - в виде массива,
где потомки элемента data[i] хранятся в ячейках a[2i+1] и a[2i+2].
*/
static void Heapify(int[] data, int length, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < length && data[left] > data[largest])
{
largest = left;
}
if (right < length && data[right] > data[largest])
{
largest = right;
}
if (largest != i)
{
Swap(data, i, largest);
Heapify(data, length, largest);
}
}
Комментарии