Eşit Elemanlar ile Hızlı Sıralama Algoritması İlerleme

Hızlı sıralama algoritmasının ilerleyişini bir dizi eşit öğe (1 (a), 1 (b), 1 (c) ile göstermemi gerektiren bir algoritma ataması üzerinde çalışıyorum vb.) dizideki son öğe olan pivot ile. Algoritmanın yinelemeli kısmı beni kafa karıştırıcı olan şey. Bence 1 (d) olacaktıEşit Elemanlar ile Hızlı Sıralama Algoritması İlerleme

1(a) 1(b) 1(c) 1(d) [1(e)] 
1(a) | 1(b) 1(c) 1(d) 1(e) 
1(a) 1(b) | 1(c) 1(d) 1(e) 
1(a) 1(b) 1(c) | 1(d) 1(e) 
1(a) 1(b) 1(c) 1(d) | 1(e)

Bu pivot sonra ve ilerlemesi bir eksik alışverişi hariç yukarıdaki ile aynı olacaktır: Şimdiye kadar ilerlemesini var. Sola ve sağa tekrarlanan çağrıların nasıl çalıştığına dair kafam karıştı. Dizinin "sağ" tarafındaki unsurlar kendileriyle değiştirilecek miydi? Bu algoritma hangi noktada durur? Burada

yalancı kod olan:

QS(A, p, r): 
if p < r 
    q = PARTITION(A, p, r) 
    QS(A, p, q - 1) 
    QS(A, q + 1, r) 

PARTITION(A, p, r): 
x = A[r] 
i = p - 1 
for j = p to r - 1 
    if A[j] <= x 
     i = i + 1 
     exchange A[i] with A[j] 
exchange A[i + 1] with A[r] 
return i + 1

s birinci eleman dizisi ve r son elemanıdır.

Yardımlarınız için teşekkürler. q hep r eşit olacaktır çünkü çağrı if p < r görevlisi tarafından bir no-op (p < r hep olacak hale QS(A, r+1, r), haline gelmesi

kaynak

2016-03-25 tfreiner

sorunuz açık değil. herhangi bir sahte kod göstermiyorsunuz. –

Benim hatam. Sadece ekledim! – tfreiner

İşte size yardımcı olabilecek bazı açıklamalar: [yinelenen öğelerle hızlı sıralama] (http://stackoverflow.com/questions/13339227/quick-sort-algorithm-improvement-if-more-duplicate-keys). – Crocode

sizin durumunuzda ikinci çağrı, QS(A, q + 1, r), her zaman, no-op olacak yanlış).

Diziniz 1, 2, ..., 5; q'un ilk değeri 5'tir, böylece ilk özyinelemeli çağrı QS(A,1,4) ve ikinci - QS(A,6,5) (no-op) olur. onun q 4 olacak ve iki aramalar - -

Aynı şey QS(A,1,4) için olacak QS(A,1,3) ve QS(A,5,4). partition kodlamak için

QA(A,1,5) 
    PARTITION(A,1,5) -> 5 
    QS(A,1,4) 
     PARTITION(A,1,4) -> 4 
     QS(A,1,3) 
      PARTITION(A,1,3) -> 3 
      QS(A,1,2) 
       PARTITION(A,1,2) -> 2 
        QS(A,1,1) 
        QS(A,3,2) 
      QS(A,4,3) 
     QS(A,5,4) 
    QS(A,6,5)

İlginç şekilde, bu şekilde yapılır görmedin. Orada, <= yerine < kullanın, hiç olmazsa öğelerini değiştirmemeliyim. (Tabii ki, tüm takaslar da, iki eşit endeks arasında değil, genel durumda olmasa da, no-ops'tur).

kaynak

2016-03-26 00:28:27

Teşekkürler. Harika bir açıklama! – tfreiner

@tfreiner en çok hoş geldiniz. :) –

Eşit Elemanlar ile Hızlı Sıralama Algoritması İlerleme

cevap

İlgili konular