Stooge sort (Сортировка по частям[1], Блуждающая сортировка[2]) — рекурсивный алгоритм сортировки с временной сложностью . Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки, такими, как Сортировка слиянием.
Aлгоритм сортировки списка элементов заключается в следующем:
algorithm stoogesort(array L, i = 0, j = length(L)-1)
if L[j] < L[i] then
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);
}
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);
}
Для улучшения этой статьи желательно: |
Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её. |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .