Stooge sort

Stooge sort (Сортировка по частям, Блуждающая сортировка) — рекурсивный алгоритм сортировки с временной сложностью [math]\displaystyle{ O(n^{\log_{1{,}5}{3}}) \approx O(n^{2.71}) }[/math]. Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки, такими, как Сортировка слиянием.

Aлгоритм сортировки списка элементов заключается в следующем:

• Если значение элемента в конце списка меньше, чем значение элемента в начале, то поменять их местами.
• Если есть 3 или более элементов в текущем подмножестве списка, то:
  • Рекурсивно вызвать Stooge sort для первых 2/3 списка
  • Рекурсивно вызвать Stooge sort для последних 2/3 списка
  • Рекурсивно вызвать Stooge sort для первых 2/3 списка снова
• Иначе: return

Примеры реализации

 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

Пример на C

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);
}

Литература

• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. — ISBN 5-8459-0857-4.