Stooge sort

Stooge sort

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

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

Примечания

  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



Wikimedia Foundation. 2010.

Смотреть что такое "Stooge sort" в других словарях:

  • Stooge sort — (auch Trippelsort) ist ein rekursiver Sortieralgorithmus nach dem Prinzip Teile und herrsche (divide and conquer). Inhaltsverzeichnis 1 Prinzip 2 Komplexität 3 Pseudocode 4 Implementierung …   Deutsch Wikipedia

  • Stooge sort — Infobox Algorithm class=Sorting algorithm data=Array time = O( n log(3)/log(1.5)) space = O( n ) optimal=NoStooge sort is a recursive sorting algorithm with a time complexity of about O( n 2.7).The exponent s exact value is log(3) / log(1.5) =… …   Wikipedia

  • Stooge — A stooge is generally defined as a person that is under the control of another. Being called a stooge is not a form of praise. Stooge can also sometimes be used to mean Idiot .what is stooge......is a donkey *Stooge (missile), an early surface to …   Wikipedia

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] …   Wikipedia

  • Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) …   Wikipedia

  • Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) …   Wikipedia

  • Cycle sort — Example of cycle sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance Θ(n2) …   Wikipedia

  • Odd–even sort — Example of odd even transposition sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»