Русская Википедия:Stooge sort

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Алгоритм) \approx O(n^{2.71})</math> | память = <math>O(n)</math> }}

Stooge sort (Сортировка по частям, Блуждающая сортировка) — рекурсивный алгоритм сортировки с временной сложностью <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);
}

Литература

• Шаблон:Книга