Sıralama

Ev sahibinin türünün görselleştirilmesi (sadece değiş tokuşları gösterir).

İlgili sorun	Sıralama algoritması
Veri yapısı	Yazı tahtası

Zaman karmaşıklığı

En kötü durumda	${\ displaystyle O (n ^ {günlük {3} / günlük {1.5}})}$

Uzay karmaşıklığı

En kötü durumda	${\ displaystyle O (n)}$

Gelen bilgisayar bilimleri , ev sahibi sıralama bir olan özyinelemeli sıralama algoritması . Adı The Three Stooges'dan esinlenerek İngilizce'de yardakçı sıralama olarak adlandırılır . Cormen , Leiserson , Rivest ve Stein tarafından yazılan Algoritmaya Giriş kitabında bir alıştırma olarak sunulmuştur .

Prensip

Araziyi sınıflandırma ilkesi aşağıdaki gibidir:

Doğru sırada değillerse dizinin ilk ve son elemanlarını sıralamak için değiştiririz.
Dizi üçten fazla öğe içeriyorsa:
- dizinin ilk 2 / 3'ünü sıralarız;
- dizinin son 2 / 3'ünü sıralarız;
- Dizinin ilk 2 / 3'ünü yeniden sıralıyoruz.

Zamansal karmaşıklığı O ( n log 3 / log 1,5 ) = O ( n 2,7095 ... ) , bu nedenle bu algoritma hızlı sıralama veya balonlu sıralama ile karşılaştırıldığında özellikle verimsizdir .

Uygulama

function stoogesort(A, i, j) if A[i] > A[j] then échanger A[i] et A[j] if (j - i + 1) > 2 then t = (j - i + 1) / 3 stoogesort(A, i , j-t) stoogesort(A, i+t, j ) stoogesort(A, i , j-t) return A

Notlar ve referanslar

https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-22/18-sorting1-bogo-stooge-bubble.pdf
(in) Thomas H. Cormen , Charles E. Leiserson ve Ronald L. Rivest , Algoritmalara Giriş , Paris, Dunod ,2002, xxix + 1146 s. ( ISBN 978-2-10-003922-7 , SUDOC 068254024 ) , böl. 7 ("Hızlı sıralama")