Stooge sıralama - Stooge sort - Wikipedia

Stooge sıralama
Stoogesort anim.gif sıralama
Stooge sıralamanın görselleştirilmesi (yalnızca swapları gösterir).
SınıfSıralama algoritması
Veri yapısıDizi
En kötü durumda verimÖ(ngünlük 3 / günlük 1.5)
En kötü durumda uzay karmaşıklığıÖ(n)

Stooge sıralama bir yinelemeli sıralama algoritması. Son derece kötü olmasıyla dikkate değer zaman karmaşıklığı nın-nin Ö (ngünlük 3 / günlük 1.5 ) = O (n2.7095...)Bu nedenle algoritmanın çalışma süresi, makul sıralama algoritmalarına kıyasla daha yavaştır ve Kabarcık sıralaması, oldukça verimsiz bir türün kanonik bir örneği. Ancak daha etkilidir Slowsort. İsim nereden geliyor Üç yardakçıları.[1]

Algoritma şu şekilde tanımlanır:

  • Başlangıçtaki değer sondaki değerden büyükse, bunları değiştirin.
  • Listede 3 veya daha fazla öğe varsa, o zaman:
    • Stooge, listenin ilk 2 / 3'ünü sıralar
    • Stooge, listenin son 2 / 3'ünü sıralar
    • Stooge, listenin ilk 2 / 3'ünü tekrar sıralar

Özyinelemeli çağrılarda kullanılan tamsayı sıralama boyutunu 2 / 3'ü yuvarlayarak elde etmek önemlidir. yukarı, Örneğin. 5'in 2 / 3'ünün yuvarlanması 3 yerine 4 vermelidir, aksi takdirde sıralama belirli verilerde başarısız olabilir.

Uygulama

 işlevi Stoogesort(dizi L, ben = 0, j = uzunluk(L)-1){     Eğer L[ben] > L[j] sonra       // En soldaki öğe, en sağdaki öğeden büyükse         L[ben]  L[j]           // En soldaki ve en sağdaki öğeyi değiştirin     Eğer (j - ben + 1) > 2 sonra       // Dizide en az 3 öğe varsa         t = zemin((j - ben + 1) / 3)         Stoogesort(L, ben  , j-t)  // Dizinin ilk 2 / 3'ünü sıralayın         Stoogesort(L, ben+t, j)    // Dizinin son 2 / 3'ünü sırala         Stoogesort(L, ben  , j-t)  // Dizinin ilk 2 / 3'ünü yeniden sıralayın     dönüş L }

Referanslar

  1. ^ "CSE 373" (PDF). course.cs.washington.edu. Alındı 14 Eylül 2020.

Kaynaklar

Dış bağlantılar