Stooge sort (Сортировка по частям, Блуждающая сортировка) — рекурсивный алгоритм сортировки с временной сложностью . Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки, такими, как Сортировка слиянием.
Aлгоритм сортировки
Алгоритм Stooge sort заключается в следующем: Если значение элемента в конце списка меньше, чем значение элемента в начале, то поменять их местами. Если есть 3 или более элементов в текущем подмножестве списка, то: Рекурсивно вызвать сортировку для первых 2/3 списка Рекурсивно вызвать сортировку для последних 2/3 списка Рекурсивно вызвать сортировку для первых 2/3 списка снова Иначе: конец подпрограммы.
Реализация на языках программирования Псевдокод function stoogesort(array L, i = 0, j = length(L)-1) if L[j] < L[i] then swap(L[i], L[j]) if (j - i) > 1 then t = (j - i + 1)/3 stoogesort(L, i, j-t) stoogesort(L, i+t, j) stoogesort(L, i, j-t) return L
Си void stoogesort(int *item, int left, int right) { int tmp, k; if(item[left] > item[right])
tmp = item[left]; item[left] = item[right]; item[right] = tmp;
if((left+1) >= right) return;
k = (int)((right-left+1)/3); stoogesort(item, left, right-k); stoogesort(item, left+k, right); stoogesort(item, left, right-k); }
JavaScript function stoogesort(item, left, right) { if(left === undefined) left = 0; if(right === undefined) right = item.length-1;
var tmp, k; if(item[left] > item[right])
tmp = item[left]; item[left] = item[right]; item[right] = tmp;
if((left+1) >= right) return;
k = Math.floor((right-left+1)/3); stoogesort(item, left, right-k); stoogesort(item, left+k, right); stoogesort(item, left, right-k); }
Примечания
Литература
Категория:Алгоритмы сортировки