Metode Quick Sort

Nama           : Khadijah Qurota’ Ain
Kelas            : 1IA17
NPM             : 5D414326
Mata Kulia : Algoritma dan Pemrograman 1A
Dosen           : Kunto Bayu A,ST


Quick Sort merupakan metode pengurutan data dengan cara memecah data yang belum terurut dengan baik dengan menentukan pivot untuk jadi patokan.
Pertama tama sebuah elemen dipilih dari data sehingga nilai variabel Sementara berada di suatu posisi ke I yang memenuhi kondisi sebagai berikut :
Semua elemen di posisi ke 1 sampai dengan ke I-1 adalah lebih kecil atau sama dengan Sementara.Semua elemen di posisi ke I+1 sampai dengan ke N adalah lebih besar atau sama dengan Sementara.

Sebagai contoh, data yang akan diurutkan sejumlah 12 elemen sebagai berikut :
33 45 18 7 5 99 57 25 55 10 40 50
Misalnya elemen yang dipilih adalah element yang pertama, maka variabel Sementara bernilai 33. Setelah diatur, maka nilai 33 akan menempati posisi ke I, yaitu posisi urutan ke 6 sebagai berikut :

                 Sementara
                         l
10 25 18 7 5 33 57 99 55 45 40 50
                         l
                 Urutan ke I

Tampak bahwa kondisi berikut terpenuhi, yaitu :Semua elemen di posisi ke 1 sampai dengan posisi ke 5 (10, 25, 18, 7,dan 5) akan lebih kecil atau sama dengan nilai 33 yang dipilih.Semua elemen di posisi ke 7 sampai dengan ke 12 (57,99,55,45,40 dan 50) akan lebih besar atau sama dengan nilai 33 yang dipilih.Dengan demikian, data tersebut akan terpecah menjadi 2 partisi, sebagai berikut :
(10 25 18 7 5) 33 (57 99 55 45 40 50)
Proses ini diulangi kembali untuk masing-masing partisi data, yaitu untuk data (10, 25, 18, 7, 5) dan data (57, 99, 55, 45, 40, 50). Untuk partisi yang pertama, bila nilai Sementara yang diambil adalah data pertama kembali dalam partisi bersangkutan, yaitu 10 dan diatur kembali sedemikian rupa, maka nilai data yang dipilih akan terletak di posisi sebagai berikut:
(5  7) 10 (18 25) 33 (57 99 55 45 40 50)
Untuk mengurutkan masing-masing partisi, maka proses tersebut diulangi kembali dan tiap-tiap partisi dipecah-pecah kembali lebih lanjut. Kurung yang menutupi partisi menunjukkan data yang belum urut dan perlu diurutkan kembali. Sedang data yang tidak berada diantara tanda kurung merupakan data yang sudah diurut. Iterasi selanjutya sampai didapatkan data yang telah urut semuanya adalah sebagai berikut ini.
5 (7) 10 (18 25) 33 (57 99 55 45 40 50)
5  7  10  18 (25) 33 (57 99 55 45 40 50)
5  7  10  18  25  33 (50 40 55 45) 57 (99)
5  7  10  18  25  33 (50 40 55 45) 57 99
5  7  10  18  25  33 (45 40) 50 (55) 57 99
5  7  10  18  25  33 (45 40) 50 55 57 99
5  7  10  18  25  33  40 (45) 50 55 57 99
5  7  10  18  25  33  40 45 50 55 57 99
Hingga tercapai data urut seperti diatas