Hızlı seçim

Hızlı seçim algoritmasının animasyonlu görselleştirmesi. 22. en küçük değerin seçimi.

Kaşif veya mucit	Charles Antony Richard Hoare
Keşif tarihi	1961
İlgili sorun	Seçim algoritması
Veri yapısı	Yazı tahtası
Başlangıcında	Medyan medyanı

Zaman karmaşıklığı

En kötü durumda	$O (n ^ 2)$
Ortalama	$Biz)$
En iyi senaryo	$Biz)$

Uzay karmaşıklığı

En kötü durumda	$O (1)$

Gelen algoritmalarıyla , QuickSelect bir olduğunu seçim algoritması olduğunu döndürür k inci bir sırasız listesindeki en küçük elemanı. Gibi quicksort sıralama algoritması , bu tarafından oluşturulan Tony Hoare ve dolayısıyla olarak da bilinir Hoare seçim algoritması .

Quickselect , öğeleri pivota göre bölümlemek için her seferinde bir öğe seçerek quicksort ile aynı yaklaşımı kullanır . Bununla birlikte, seti hızlı sıralamadaki gibi iki parçaya bölmek yerine, hızlı seçim algoritması yalnızca bir tarafta - aradığı öğeyi içeren tarafta - yinelenir. Bu , hızlı sıralamanın ortalama O ( n log n ) karmaşıklığını , hızlı seçimin ortalama O ( n ) karmaşıklığına düşürür .

Gibi quicksort , algoritma QuickSelect genellikle uygulandığı yerde ve seçme ek olarak k inci elemanı, bazı verileri sıralar. Bir itibariyle quicksort , bu ortalama süresi ile pratikte etkilidir . Quickselect ve türevleri, gerçek dünyada sıklıkla kullanılan algoritmalardır. $Biz)$

Algoritma

Quicksort , listeyi konumdan konuma iki parçaya yeniden düzenleyen bölüm adı verilen yardımcı bir işlev kullanır : belirli bir öğeden daha küçük öğeler ve aynı öğeye eşit veya daha büyük öğeler. İşte bu bölümü oluşturan sözde kod: gauchedroitepivot

fonction partition(list, gauche, droite, pivot) ValeurPivot := list[pivot] échanger list[pivot] et list[droite] // Déplace le pivot à la fin IndiceStockage := gauche pour i de gauche à droite-1 si list[i] < ValeurPivot échanger list[IndiceStockage] et list[i] incrémenter IndiceStockage échanger list[droite] et list[IndiceStockage] // Met le pivot à sa place définitive. retourner IndiceStockage

Quicksort , iki dalı özyinelemeli olarak sıralar ve en kötü durumda Ω ( n log n ) oluşturur. Bununla birlikte, pivot, solda daha küçük ve sağda daha büyük olanlarla birlikte, pivot son konumunda olduğundan, seçim, bölümün hangi tarafında olduğunu seçer. Dolayısıyla, hızlı seçim algoritmasını oluşturmak için tek bir özyinelemeli çağrı yeterlidir :

// Retourne le n-ième plus petit élément de la liste entre gauche et droite incluse (i.e. gauche ≤ n ≤ droite). // La taille de la liste reste la même à chaque appel récursif, donc n n'a pas besoin d'être changé. fonction select(list, gauche, droite, n) si gauche = droite // S'il n'y a qu'un élément retourner list[gauche] // Retourne cet élément pivot := ... // Choisit un pivot entre gauche et droite, par exemple // gauche + Math.floor(Math.random() * (droite - gauche + 1)) pivot := partition(list, gauche, droite, pivot) // Si le pivot est à sa position finale si n = pivot retourner list[n] sinon si n < pivot retourner select(list, gauche, pivot - 1, n) sinon retourner select(list, pivot + 1, droite, n)

Quicksort ile benzerliğine dikkat edin : minimal elemanın seçimine dayalı algoritmanın kısmi bir sıralama algoritması olması gibi, quickselect de bu O ( n ) bölümlerinin yalnızca O (log n ) ' sini oluşturan ve bölümleyen kısmi bir hızlı sıralama yöntemidir . Bu prosedür ortalama olarak doğrusal bir yürütme süresine ve pratikte iyi bir performansa sahiptir. Ayrıca, uçbirim özyinelemesi aşağıdaki gibi bir döngü ile ortadan kaldırılabildiğinden, ek sabit alan kullanan yerinde bir algoritmadır :

fonction select(list, gauche, droite, n) boucle si gauche = droite retourner list[gauche] pivot := ... // Choix du pivot entre gauche et droite pivot := partition(list, gauche, droite, pivot) si n = pivot retourner list[n] sinon si n < pivot droite := pivot - 1 sinon gauche := pivot + 1

Zaman karmaşıklığı

Quicksort gibi, hızlı seçim algoritmasının verimliliği de pivot seçimine bağlıdır. Pivot seçimi, aynı fraksiyonun her adımında dizinin boyutunu azaltmayı mümkün kılıyorsa, azalma üsteldir ve zaman karmaşıklığı , geometrik bir dizi gibi doğrusaldır . Aksine, pivot sadece boyutu 1 azaltırsa, o zaman en kötü durum ikinci dereceden bir karmaşıklığa sahiptir, O ( n 2 ). Bu, esas olarak, pivot en sağdaki öğe ise ve dizi zaten sıralanmışsa gerçekleşir.

Varyantlar

En basit çözüm, büyük olasılıkla doğrusal bir yürütme süresi veren rastgele bir pivot seçmektir. Belirleyici bir algoritma olarak, 3 değerin medyan stratejisi, hızlı sıralamada olduğu gibi, kısmen sıralanmış veriler üzerinde doğrusal bir yürütme süresi verir ve bu genellikle doğrudur. Ancak en kötü durum karmaşıklığı hala elde edilebilir, David Musser bu en kötü duruma nasıl ulaşılacağını gösterdi, buna karşı kendi seçim içi algoritması var .

En kötü durumda doğrusal bir karmaşıklık , uygulamada kullanılmaması için önemli bir pratik ek maliyetle, medyanların medyan yöntemiyle elde edilebilir . Uygulamada iyi sonuçlar ve en kötü durumda iyi bir karmaşıklık elde etmek için temel hızlı seçim ve en kötü durum için bu algoritma ile birleştirmek mümkündür, introselect bunu yapar .

Daha kesin olarak, zamandaki ortalama karmaşıklık rastgele bir pivot içindir (medyan için arama durumunda, diğer k daha hızlıdır). Zaman ortalamalı karmaşıklığı medyan hesaplama için olan Floyd - Rivest algoritması kullanılarak daha karmaşık bir pivot ile sabit 3 / 2'ye indirilebilir ve diğer ks ile daha hızlıdır . $n (2 + 2 \ log 2 + o (1)) \ leq 3.4n + o (n)$ $1,5n + O (n ^ {{1/2}})$

Notlar ve referanslar

(inç) CAR Hoare, " Algoritma 65: bul " , ACM İletişimi , cilt. 4, n o 7,1961, s. 321-322 ( DOI 10.1145 / 366622.366647 ).
Quickselect'in Blum tarzı analizi , David Eppstein , 9 Ekim 2007.