Stooge sort

Stooge sort

Infobox Algorithm


class=Sorting algorithm
data=Array
time = O("n"log(3)/log(1.5))
space = O("n")
optimal=No

Stooge 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) = 2.709... The running time of the algorithm is thus extremely slow compared to efficient sorting algorithms, such as Merge sort.

The algorithm is defined as follows:
* If the value at the end is smaller than the value at the start, swap them.
* If there are 3 or more elements in the current list subset,
* then:
** Stooge sort the initial 2/3 of the list
** Stooge sort the final 2/3 of the list
** Stooge sort the initial 2/3 of the list again
* else: exit the procedure

The algorithm gets its name from slapstick routines of the Three Stooges, in which each stooge hits the other two.Fact|date=July 2007

Implementation

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

External links

* [http://www.everything2.com/index.pl?node=stooge%20sort Everything2.com - Stooge sort]
* [http://cg.scs.carleton.ca/~morin/misc/sortalg/ Sorting Algorithms (including StoogeSort)]

References

*Paul E. Black, "stooge sort", in Dictionary of Algorithms and Data Structures (online), Paul E. Black, ed., U.S. National Institute of Standards and Technology. Accessed 3 September 2008. Available from: [http://www.nist.gov/dads/HTML/stoogesort.html www.nist.gov/dads/HTML/stoogesort.html]


Wikimedia Foundation. 2010.

См. также в других словарях:

  • Stooge sort — (Сортировка по частям[1], Блуждающая сортировка[2])  рекурсивный алгоритм сортировки с временной сложностью . Время работы алгоритма, таким образом, крайне большое по сравнению с эффективными алгоритмами сортировки, такими, как Сортировка… …   Википедия

  • 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 — 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


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

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