QUICK SORT

Soal :
Bila terdapat data acak sebagai berikut :
16 12 23 50 19 49 31
Bila akan diurutkan secara descending dengan menggunakan metode quick sort maka hasil yang menjadi pivot pada tahap pertama adalah…..
Sebelum menyelesaikan soal di atas, terlebih dahulu dicari pengertian pivot. Kami telah mendapatkan 5 referensi buku untuk mendapatkan pengertian dan cara pengambilan pivot.

a. Buku Referensi 1
Algoritma dan Pemograman
Oleh : Antony Pranata
Penerbit : Graha Ilmu

Cara pengambilan pivot didapat dari L = 1 (data 1) dijumlahkan dengan R = N(jumlah data), kemudian dibagi 2. Tujuan dari pemilihan pivot adalah mengatur data di sebelah kiri agar lebih kecil daripada pivot dan data di sebelah kanan agar lebih besar daripada pivot. Misal pivot dilambangkan dengan x. Pivot 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 diantara posisi (j+1) sampai dengan N yang lebih besar daripada x dengan data diantara posisi (j+1) sampai dengan N yang lebih kecil daripada x. Dan untuk cara descending kebalikannya.
Jadi, untuk soal di atas dengan metode yang ada pada buku ini maka yang menjadi pivot pada tahap pertama yaitu :
data :
1 2 3 4 5 6 7
16 12 23 50 19 49 31

x ← data[(L + R) div 2]
x ← data[(1 + 7) div 2]
x ← data[8 div 2]
x ← data[4]
Jadi, pivot pada tahap pertama adalah data ke-4 yaitu 50.

b. Buku Referensi 2
Algoritma dan Struktur Data dengan C++
Oleh : Indra Yatini B
Erliansyah Nasution
Penerbit : Graha Ilmu

Pada buku ini dijelaskan bahwa pivot merupakan suatu elemen pembanding yang membandingkan elemen disebelah kirinya dan sebelah kanannya. Untuk memilih pivot, kita tidak harus memilih item pertama dalam daftar. Kita bisa memilih setiap item yang kita inginkan dan menukarkannya dengan item pertama sebelum memulai loop yang memisahkan daftar. Sebenarnya, item pertama dalam daftar sering merupakan pilihan buruk untuk dijadikan pivot, karena jika datar telah terurut, maka tidak ada kunci yang kurang darinya sehingga satu subdaftar akan kosong. Lebih baik memilih pivot dekat dengan tengah daftar, dengan harapan pilihan kita akan memisahkan kunci masing-masing separuh bagian.
Jadi, dalam buku ini pemilihan pivot dapat diambil didata manapun, tetapi diusahakan dekat dengan tengah.

c.Buku Referensi 3
Struktur Data dengan C++
Oleh : Andri Kristanto
Penerbit : Graha Ilmu

Pada buku ini, pemilihan pivot tidak terlalu berbeda dengan buku referensi pertama. Pengambilan pivotnya yaitu dengan menjumlahkan data 1 dengan banyaknya data kemudian dibagi 2, sehingga nilai pivotnya berada ditengah yaitu pada data ke-4, yaitu 50. Tapi hanya ada sedikit perbedaan dalam pengerjaannya yaitu dalam buku referensi 1, penyelesaian dilakukan disebelah kiri dulu kemudian data disebelah kanan dan pivot pertama menjadi j. Sedangkan dalam buku ini, nilai j ada pada data terakhir sampai (j-1).

d.Buku Referensi 4
Berpetualang dengan Struktur Data di Planet Pascal
Oleh : Dwi Sanjaya
Penerbit : J & J Learning Yogyakarta

Pivot adalah elemen yang membandingkan elemen dengan elemen lain dan menyusunnya sedemikian rupa. Cara pengambilan pivotnya pun sama dengan buku referensi 1 dan buku referensi 3, yaitu dengan rumus :
x ← data[(L + R) div 2]
Sehingga pivot pertamanya akan berada ditengah. Jika dari soal di atas, pivot pada tahap pertama adalah data ke-4 yaitu 50.

e.Buku Referensi 5
Algoritma Teknik Penyelesaian dan Permasalahan untuk Komputasi
Oleh : Edi Sutanto
Penerbit : Graha Ilmu

Pivot adalah suatu pembanding elemen data dengan elemen data lainnya yang diurutkan secara urut naik maupun urut turun. Cara pengambilan pivotnya mempunyai kesamaan dengan buku referensi 2, yaitu pengambilan pivotnya bisa diambil didata manapun tapi diusahakan mendekati tengah dan membagi array menjadi 2 bagian.


Penyelesaian :
Soal di atas akan dicoba untuk diselesaikan dengan cara descending dan dikerjakan sesuai dengan metode yang ada dibuku referensi 4 yaitu Berpetualang dengan Struktur Data di Planet Pascal.

Diketahui : Bila terdapat data acak sebagai berikut :

16 12 23 50 19 49 31
Data tersebut akan diselesaikan dengan metode quicksort secara descending.

Langkah 1 :
Tentukan pivot pada array. Misalkan pivot adalah x.
x ← data[(L+R) div 2]
x ← data[(1 + 7) div 2]
x ← data[8 div 2]
x ← data[4]
i ← L
j ← R

data 1 2 3 4 5 6 7
16 12 23 (50) 19 49 31

i → ← j
i bergerak dari sudut kiri ke kanan sampai mendapatkan nilai yang <= pivot. j bergerak dari sudut kiri ke kanan sampai mendapatkan nilai yang >= pivot.

i berhenti pada data ke-1 karena langsung menemukan nilai yang lebih kecil dari pivot.
j berhenti pada data ke-4 karena tidak menemukan nilai yang lebih besar daripada pivot.

Karena i < j maka data yang ditunjuk oleh i ditukar dengan data yang ditunjuk oleh j sehingga menjadi:

50 12 23 16 19 49 31


Langkah 2 :
data 1 2 3 4 5 6 7
50 12 23 (16) 19 49 31

i → ← j
i berhenti pada data ke-2 karena menemukan nilai yang lebih kecil dari pivot.
j berhenti pada data ke-7 karena langsung menemukan nilai yang lebih besar dari pivot.

Karena i < j maka data yang ditunjuk oleh i ditukar dengan data yang ditunjuk oleh j sehingga menjadi:

50 31 23 16 19 49 12


Langkah 3 :
Data 1 2 3 4 5 6 7
50 31 23 (16) 19 49 12

i → ← j
i berhenti pada data ke-4 karena tidak menemukan nilai yang lebih kecil dari pivot.
j berhenti pada data ke-6 karena menemukan nilai yang lebih besar dari pivot.

Karena i < j maka data yang ditunjuk oleh i ditukar dengan data yang ditunjuk oleh j sehingga menjadi:

50 31 23 49 19 16 12


Langkah 4 :
Data 1 2 3 4 5 6 7
50 31 23 (49) 19 16 12

i → ← j
i berhenti pada data ke-2 karena menemukan nilai yang lebih kecil dari pivot.
j berhenti pada data ke-4 karena tidak menemukan nilai yang lebih besar dari pivot.
Karena i < j maka data yang ditunjuk oleh i ditukar dengan data yang ditunjuk oleh j sehingga menjadi:

50 49 23 (31) 19 16 12


Langkah 5 :
Data 1 2 3 4 5 6 7
50 49 23 (31) 19 16 12

i → ← j
i berhenti pada data ke-3 karena menemukan nilai yang lebih kecil dari pivot.
j berhenti pada data ke-4 karena tidak menemukan nilai yang lebih besar dari pivot.

Karena i < j maka data yang ditunjuk oleh i ditukar dengan data yang ditunjuk oleh j sehingga menjadi:

50 49 31 23 19 16 12

Proses pengurutan berhenti karena i tidak menemukan data yang lebih kecil dari x dan j tidak menemukan data yang lebih besar dari x.


Algoritma Pengurutan
procedure quicksort_secara_descending ( i/o data : larik, input L, R : char)
{ I.S : elemen data array sudah terdefinisi }
{ F.S: menghasilkan elemen data array yang sudah terurut secara descending }
Deklarasi :
i, j, x, temp: char
Deskripsi :
x ← data[(L + R) div 2]
i ← L
j ← R

while i ≠ j do
while data[i] > x do
i = i + 1
endwhile
while data[j] < x do
j = j – 1
endwhile
if i ≠ j then
temp ← data[i]
data[i] ← data[j]
data[j] ← temp
i ← L
j ← R
endif
endwhile
endprocedure