Сортировка пузырьком (Bubblesort)
Подробно пузырьку, больший элемент массива поднимается "вверх".
https://www.youtube.com/watch?feature=player_embedded&v=lyZQPjUT5B4
Описание алгоритма
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Реализация
void bubble(int* a, int n)
{
for (int i=n-1; i>=0; i--)
{
for (int j=0; j<i; j++)
{
if (a[j] > a[j+1])
{
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
Вывод
Метод пузырька оказывается крайне неэффективным на любом входном наборе данных. Единственный плюс алгоритма - простота его исполнения.
Сортировка выбором (Selection sort)
Упорядочиваем постепенно массив, заполняя первую позицию неупорядоченной части минимальным элементом из неупорядоченной части.
https://www.youtube.com/watch?feature=player_embedded&v=Ns4TPTC8whw
Описание алгоритма
Шаги алгоритма: находим номер минимального значения в текущем списке, производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции), теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы. Для реализации устойчивости алгоритма необходимо в пункте 2 минимальный элемент непосредственно вставлять в первую неотсортированную позицию, не меняя порядок остальных элементов.
Реализация
void select_sort(int *a, int length){
for (int i = 0; i < length - 1; i++) {
/* устанавливаем начальное значение минимального индекса */
int min_i = i;
/* находим индекс минимального элемента */
for (int j = i + 1; j < length; j++) {
if a[j] < a[min_i]) {
min_i = j;
}
}
/* меняем значения местами */
int temp = array[i];
array[i] = array[min_i];
array[min_i] = temp;
}
}
Вывод
Метод оказывается эффективным только на маленьких массивах (не более 10), на массивах больших размеров, в силу асимптотической сложности n^2, алгоритм оказывается крайне не эффективным.
Сортировка слиянием (Merge sort)
Упорядочиваем списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.
https://www.youtube.com/watch?feature=player_embedded&v=XaqR3G_NVoo
Описание алгоритма
Для решения задачи сортировки эти три этапа выглядят так:
1) Сортируемый массив разбивается на две части примерно одинакового размера;
2) Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
3) Два упорядоченных массива половинного размера соединяются в один. 1.1. - 2.1.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
3.1. Соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два подмассива. Пусть также, элементы подмассивов в каждом из этих подмассивов отсортированы по возрастанию. Тогда:
3.2. Слияние двух подмассивов в третий результирующий массив.
На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив.
Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1.3.
"Прицепление" остатка. Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.
Реализация
void merge(int *a, int low, int mid, int high)
{
// Variables declaration.
int *b = new int[high+1-low];
int h,i,j,k;
h=low;
i=0;
j=mid+1;
// Merges the two array's into b[] until the first one is finish
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
// Completes the array filling in it the missing values
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
// Prints into the original array
for(k=0;k<=high-low;k++)
{
a[k+low]=b[k];
}
delete[] b;
}
void merge_sort(int *a, int low, int high)
{// Recursive sort...
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(a, low,mid);
merge_sort(a, mid+1,high);
merge(a, low,mid,high);
}
}
Вывод
Метод оказывается крайне эффективным, однако требуется выделение дополнительной памяти.
Быстрая сортировка (Quicksort)
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью.
Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы.
Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.
https://www.youtube.com/watch?feature=player_embedded&v=ywWBy6J5gz8
Описание алгоритма
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
a) Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
b) Вычисляется индекс опорного элемента m.
c) Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
d) Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
e) Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
f) Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута обязательно и обработка гарантированно завершится.
Реализация
void quicksort(int* a, int first, int last)
{
int i = first, j = last, x = a[(first + last) / 2];
do {
while (a[i] < x) i++;
while (a[j] > x) j--;
if(i <= j) {
if (i < j) swap(a[i], a[j]);
i++;
j--;
}
} while (i <= j);
if (i < last)
quicksort(a, i, last);
if (first < j)
quicksort(a, first,j);
}
Вывод
Метод показывает высокую эффективноть, при этом он не требует расходов на дополнительную память. Однако, в худшем случае алгоритм оказывается крайне медленным (O(n2)).
Блочная сортировка
Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.
Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой.
Реализация
void bucketSort(int ar[], const int sz)
{
const int Rasryad = 10;
const int Position = 20000;
int TempArray[Rasryad][Position] = {0};
int number = 1, Ras;
for(int i = 0; i < N; i++)
{
count = 0;
for(int j = 0; j < sz; j++)
{
Ras = ar[j] / number % 10;
TempArray[Ras][j] = ar[j];
}
for(int a = 0; a < Rasryad; a++)
{
for(int b = 0; b < Position; b++)
{
if(TempArray[a][b]!= 0)
{
ar[count++] = TempArray[a][b];
TempArray[a][b] = 0;
}
}
}
number *= 10;
}
for(int i = 0; i < sz; i++)
sm += IntToStr(mas[i]) + " ";
}
Вывод
Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).
Недостатки: сильно деградирует при большом количестве мало отличных элементов, или же на неудачной функции получения номера корзины по содержимому элемента. В некоторых таких случаях для строк, возникающих в реализациях основанного на сортировке строк алгоритма сжатия BWT, оказывается, что быстрая сортировка строк в версии Седжвика значительно превосходит блочную сортировку скоростью.