Algoritma Quick Sort

Metode Quick atau yang sering disebut juga metode partisi diperkenalkan pertama kali oleh C. A. R. Hoare pada tahun 1962. Pada metode quick, jarak dari kedua elemen yang ditukarkan dibuat cukup besar dengan tujuan untuk mempertinggi efektivitasnya. Hal ini mengingat metode gelembung yang menggunakan jarak cukup dekat ternyata kurang efektif.

Proses pengurutan dengan metode quick dapat dijelaskan sebagai berikut : mula-mula dipilih data tertentu yang dinamakan pivot, misalnya x. Pivot ini harus diletakkan pada posisi ke-j sedemikian hingga data antara 1 sampai dengan (j – 1) lebih kecil daripada x; sedangkan data pada posisi ke-(j+1) sampai dengan N lebih besar daripada x. Cara pengaturannya adalah menukarkan data di antara posisi 1 sampai dengan (j – 1) yang lebih besar daripada x dengan data di antara posisi (j + 1) sampai dengan N yang lebih kecil daripada x.

Algoritma penyisipan langsung sendiri dapat dituliskan sebagai berikut:

1. x ← Data [( L + R) / 2)].

2. i ← L

3. j ← R

4. Selama ( i < = j ) kerjakan baris 5 sampai dengan 12.

5. Selama ( Data [ i ] < style="mso-spacerun:yes"> ← i + 1

6. Selama ( Data [ j ] > x ) kerjakan i ← j - 1

7. Jika (i < = j ) maka kerjakan baris 8 sampai dengan 10; jika tidak kerjakan baris 11.

8. Tukar Data [ i ] dengan Data [ j ].

9. i ← i + 1

10. j ← j - 1

11. Jika ( L < r =" j.

12. Jika ( i < l =" i.

Jika suatu barisan yang terdiri dari n elemen yang ditempatkan dalam suatu array dan urutan yang diinginkan adalah urutan yang tidak turun (non decreasing) maka dapat digunakan metode Quick Sort yang dengan teknik Divide and Conquer.

Adapun algoritma Quick Sort tersebut terdiri dari dua prosedur yaitu prosedur PARTITION dan prosedur QUICKSORT. Berikut ini disajikan algoritma Quick Sort yang dimaksud, yaitu :

PROCEDURE QUICKSORT(p,q)

IF p ← j← q + 1

CALL PARTITION(p,j)

CALL QUICKSORT(p,j-1)

CALL QUICKSORT(j+1,q)

END IF

END QUICKSORT

PROCEDURE PARTITION(m,p)

INTEGER m,p,i ; GLOBAL A(m-1,p)

V ← A(m) ; i← m

LOOP

LOOP i← i + 1 UNTIL A( i ) > = V REPEAT

LOOP p ← p - 1 UNTIL A( p ) < = V REPEAT

IF i

THEN CALL INTERCHANGE (A(i),A(p))

ELSE EXIT

END IF

REPEAT

A(m) ← A(p)

A(p) ← V

END PARTITION

http://www.informatika.org/~rinaldi/Matdis/2009-2010/Makalah0910/MakalahStrukdis0910-023.pdf

http://books.google.co.id/books?id=Rfa5DcATAEQC&pg=PA342&dq=Algoritma+Quick+Sort&hl=id&ei=zuNsTcWrHYvxrQeu-oX7Bg&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCoQ6AEwAA#v=onepage&q&f=false