Русская Википедия:Stooge sort
Материал из Онлайн справочника
Шаблон:Алгоритм) \approx O(n^{2.71})</math> | память = <math>O(n)</math> }}
Stooge sort (Сортировка по частям[1], Блуждающая сортировка[2]) — рекурсивный алгоритм сортировки с временной сложностью <math>O(n^{\log_{1{,}5}{3}}) \approx O(n^{2.71})</math>. Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки, такими, как Сортировка слиянием.
Aлгоритм сортировки
Алгоритм Stooge sort заключается в следующем:
- Если значение элемента в конце списка меньше, чем значение элемента в начале, то поменять их местами.
- Если есть 3 или более элементов в текущем подмножестве списка, то:
- Рекурсивно вызвать сортировку для первых 2/3 списка
- Рекурсивно вызвать сортировку для последних 2/3 списка
- Рекурсивно вызвать сортировку для первых 2/3 списка снова
- Иначе: конец подпрограммы.
Реализация на языках программирования
Псевдокод
algorithm 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)
{
register 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);
}
Примечания
Литература
Шаблон:Rq Шаблон:Computer-sci-stub