Comments 35
P.S. Selection — www.youtube.com/watch?v=YLfjP-Cals0 и Merge — www.youtube.com/watch?v=YvtDD0YMScU
Удивительно, что по сравнениям этот алгоритм на 20% быстрее сортировки Шелла, от которой он отличается только тем, что там пузырёк проходит по каждой разности до конца. По обменам они почти одинаковы.
В пирамидальной сортировке этот поиск производится с помощью построения кучи из элементов массива.
Что касается пузырьковой сортировки, то там максимальный элемент на текущем отрезке целенаправленно не ищется. В результате многочисленных обменов максимумы «всплывают» на свои места, но это не есть поиск.
Результаты следующие.
«Глупая» сортировка зависает на неопределенное время на размере массива около 3000 элементов. На 2000 показывает время примерно 1600 мс.
«Пузырьковая» ведет себя лучше — около 25 мс на размере 2000 элементов. На 30 000 элементов — 2700 мс, почти три секунды.
«Шейкерная» сортировка — на размере 2000 элементов такие же, даже немного хуже (спишем на статистику) результаты. А вот на 30000 элементов разница в два раза — 1200 мс.
«Гребешковая» сортировка меня удивила. Я ожидал, что будет быстрее, но не на столько же! 2000 элементов — 11 мс. 30 000 элементов — 26 мс. 30 000 000 — 5500 мс.
Для сравнения — Arrays.sort(): 3000 элементов — 14-15 мс, 30000 — 30-40 мс, 30 000 000 — 3400 мс.
Вы заметили, что «гребешковая» сортировка получилась быстрее стандартной джавы? Меня это заинтересовало, и я начал увеличивать размер массива, и сравнивать результаты «гребешка» и Arrays.sort(). Получилось, что до 1 500 000 элементов «гребешок» быстрее, а вот дальше уже стандартная сортировка начинает работать быстрее.
Вот такие вот результаты :) Приятно, что реализация «гребешковой» сортировки тривиальна — можно реально использовать на небольших массивах с реальной пользой.
Кому интересно, привожу «тестовую лабораторию»:
package com.webprestige.winter.wallpaper;
import java.util.Random;
public class DesktopStarter {
public static void main(String[] args) {
int size = 30000000;
Random r = new Random();
int[] v = new int[size];
for (int i = 0; i < size; v[i++] = r.nextInt(10000));
long time = System.currentTimeMillis();
coolSort(v);
long endTime = System.currentTimeMillis();
System.out.println("Time is " + (endTime - time));
// for(int i = 0; i < size; i++) {
// System.out.print(v[i] + " ");
// }
}
private static void stupidSort(int[] v) {
boolean end = false;
while (!end) {
end = true;
for (int i = 0; i < v.length - 1; i++) {
if (v[i] > v[i + 1]) {
int t = v[i];
v[i] = v[i + 1];
v[i + 1] = t;
end = false;
break;
}
}
}
}
private static void bulbSort(int[] v) {
boolean end = false;
while (!end) {
end = true;
for (int i = 0; i < v.length - 1; i++) {
if (v[i] > v[i + 1]) {
int t = v[i];
v[i] = v[i + 1];
v[i + 1] = t;
end = false;
}
}
}
}
private static void shakeSort(int[] v) {
boolean end = false;
while (!end) {
end = true;
for (int i = 0; i < v.length - 1; i++) {
if (v[i] > v[i + 1]) {
int t = v[i];
v[i] = v[i + 1];
v[i + 1] = t;
end = false;
}
}
for (int i = v.length - 1; i > 0; i--) {
if (v[i] < v[i - 1]) {
int t = v[i];
v[i] = v[i - 1];
v[i - 1] = t;
end = false;
}
}
}
}
public static void coolSort(int[] v) {
float loadFactor = 1.247f;
int step = v.length;
boolean end = false;
int t;
while (!end) {
end = true;
step /= loadFactor;
if (step < 1) {
step = 1;
}
for (int i = 0; i < v.length - 1; i++) {
if ((i + step) < v.length) {
if (v[i] > v[i + step]) {
t = v[i];
v[i] = v[i + step];
v[i + step] = t;
end = false;
}
} else {
end = false;
}
}
}
}
}
Вы, кстати, не упомянули про «чет-нечет».
private static void oddNotOddSort(int[] v) {
boolean end = false;
while (!end) {
end = true;
for (int i = 0; i < v.length - 1; i += 1) {
if (v[i] > v[i + 1]) {
int t = v[i];
v[i] = v[i + 1];
v[i + 1] = t;
end = false;
}
}
for (int i = 1; i < v.length - 1; i += 1) {
if (v[i] > v[i + 1]) {
int t = v[i];
v[i] = v[i + 1];
v[i + 1] = t;
end = false;
}
}
}
}
Результаты: для 3000 элементов — порядка 40 мс, для 3000 — 2600. По сути, также, как и пузырьковая
Вот исходник:
private static void bogosort(IntArray a) {
boolean end = false;
while(!end) {
a.shuffle();
end = true;
for(int i = 0; i < a.size-1; i++) {
if (a.get(i) > a.get(i+1)) {
end = false;
break;
}
}
}
}
Для справки — IntArray — тонкая обертка над массивом, используется в движке LibGdx. В данном случае то, что массив обернут и это влияет на производительность, думаю, не очень важно — посколько основные операции — перемешивание, а оно реализовано внутри этого класса без всяких оберток (фух, аж сам запутался :) ). Собственно, поэтому и использовал этот класс — лень было писать свою функцию перемешивания.
А вот и результаты:
1-6 элементов — 4 мс
7 — 20-30 мс
8 — 20-50 мс
9 — 150-600 мс
10 — 1000 и больше
11 — 2500 — 5000
На двенадцати элементах мой ноутбук начал гудеть вентилятором, но результат не выдавал никакой. Вывод — более полусотни лет прогресса, а больше десяти элементов отсортировать не можем :))
Огромное спасибо!
Никропостер врывается в чат. А как вычислили сложность глупой сортировки? Здесь указывается n^3, но даже на анимации циклов значительно меньше 7^3. Как тут посчитать циклы c n? В другом источнике говорили даже про (n*n!)
Некропостер 2.
Пусть мы пишем сортировку вот таким псевдокодом:
void stupid_sort(int *arr, size_t length)
{
size_t idx = 0;
while (idx < length-1)
{
if (arr[idx] > arr[idx+1])
{
swap(arr[idx], arr[idx+1]);
idx = 0;
continue;
}
++idx;
}
}Тогда, если массив имеет ввид [a_0, ..., a_(n-1)] и отсортирован в обратном порядке, то:
для a_0 мы сравним с a_1, поменяем их, начнем заново. Получим
[a_1, a_0, ..., a_(n-1)].
Затем пройдем два раза, получая
[a_1, a_2, a_0, ..., a_(n-1)].
и получим
[a_2, a_1, a_0, ..., a_(n-1)]
А дальше интересно. После того как мы поменяем a_3 с a_0, то получим
[a_2, a_1, a_3, a_0, ...]
и надо будет еще два цикла (два раза сбросить idx в ноль, чтобы поставить a_3 на положенный ему индекс.
Сейчас немного формализую. Пусть a[i], 0 <= i < n, -- наш массив. Пусть i*(1) - адрес первого элемента, такого что a[i*(1)] > a[i*(1)+1]. Тогда
Цикл while потребует i*(1) сравнений перед тем как это обнаружить, поменять элементы и затем сбросить счетчик. То есть потребуется i*(1) операций для того, чтобы получить массив вида:
[..., a[i*(1)+1], a[i*(1)], ...]
Дальше две ветки: либо cлайс a[0]...a[i*(1)] отсортирован и мы идем дальше, либо a[i*(1)-1] > a[i*(1)+1] и тогда потребуется i*(1)-1 операций, чтобы и эту пару поменять. А если каждый предыдущий, то потребуется
операций, чтобы получить [..., a[i*(1)]...] как отсортированный подмассив (мы все еще не знаем отсортировано ли то, что дальше a[i*(1)]. Эта сумма -- квадратичного порядка. Дальше, такая ситуация теоретически может повториться вплоть n-1 раз, откуда и получаем порядок третьей степени. Я, может, даже набросаю подсчет.
https://pastebin.com/8gqxhtqB
Вот примерная реализация. Вот некоторые исполнения:
n: 10; n^3: 1000; ops: 174; log_n(ops): 2.24055
n: 100; n^3: 1000000; ops: 166749; log_n(ops): 2.61103
n: 1000; n^3: 1000000000; ops: 166667499; log_n(ops): 2.74062
n: 2000; n^3: -589934592; ops: 1333334999; log_n(ops): 2.76427
Дальше не исполнял (после 4000 там уже из-за оверфлоу проблемы), но можно увидеть, что логарифм от числа операций по базе n приближается к трем.
Пузырьковая сортировка и все-все-все