Stooge sort

Stooge sort
Визуализация работы алгоритма
Визуализация работы алгоритма
Предназначение Алгоритм сортировки
Структура данных Массив
Худшее время O ( n log 1 , 5 ⁡ 3 ) ≈ O ( n 2.71 ) {\displaystyle O(n^{\log _{1{,}5}{3}})\approx O(n^{2.71})}
Затраты памяти O ( n ) {\displaystyle O(n)}

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

Aлгоритм сортировки

Алгоритм Stooge sort заключается в следующем:

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

Реализация на языках программирования

Псевдокод 

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

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

Примечания

  1. ↑ Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2000. — 960 с. — ISBN 5-900916-37-5.
  2. ↑ Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.

Литература

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