16. Rekurzív rendezések I

Merge sort:

Alapötlet:

• Az n elemű tömböt felosztjuk két (n/2 elemű) résztömbre
• A résztömböket rekurzív módon rendezzük, azaz tovább bontjuk a résztömböket, míg 1 elemű tömböt kapunk, ami önmagában rendezett.
• A rendezett résztömböket összefuttatjuk megtartva a rendezettségek.

Pszeudokód:

Eljárás Merge_sort(X, E, U)

Ha E<U akkor

K<- Egészrész((E+U)/2)

Merge_sort(X, E, K)

Merge_sort(X, K+1, U)

Merge(X, E, K, U)

Elágazás vége

Eljárás vége

Összefuttatás pszeudokódja:

Eljárás Merge(X, E, K, U)

N1<-K-E+1; N2<-U-K;

Ciklus i<-1től N1-ig

L[i]<-X[E+i-1]

Ciklus vége

Ciklus j<-1-től N2-ig

R[j]<-X[K+j]

Ciklus vége

L[N1+1]<- +∞; R[N2+1] <- +∞;

i<-1; j<-1;

Ciklus k<-E-től U-ig

Ha L[i]<=R[j] akkor

X[k]<-L[i]

i<-i+1

különben

X[k]<-R[j]

j<-j+1

Elágazás vége

Ciklus vége

Eljárás vége

• Az algoritmus futási ideje O(N*logN)-es
• A megvalósításhoz szükségünk van segédtömbökre, így nagy tömbök esetén helyfoglalás szempontjából nem hatékony.

Felhasznált Irodalom: Sergyán Szabolcs – Programozás I – 10. előadás diasor

Kommentek

comments

Powered by Facebook Comments