The Stooges
- 1 year ago
- 0
- 0
Stooge sort (Сортировка по частям , Блуждающая сортировка ) — рекурсивный алгоритм сортировки с временной сложностью . Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки, такими, как Сортировка слиянием .
Алгоритм Stooge sort заключается в следующем:
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);
}
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);
}
|
Это
заготовка статьи
по
информатике
. Помогите Википедии, дополнив её.
|