Quick Sort
Quick Sort atau Partition Exchange Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data, kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa, 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 :
Misalnya element 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 :
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.
Maka Proses dari rekursi tampak pada pengurutan data dari bawah sampai dengan I-1 dan pengurutan I+1 sampai dengan atas.
(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
Maka Proses dari rekursi tampak pada pengurutan data dari bawah sampai dengan I-1 dan pengurutan I+1 sampai dengan atas.
Implementasi Algoritma Quick Sort
Berikut adalah implementasi dari quick sort dalam bahasa C. Implementasinya terbagi menjadi dua prosedur, yaitu prosedur partisi dan prosedur quicksort.
void quicksort(int x[], int first, int last) {
int pivIndex = 0;
if(first < last) {
pivIndex = partition(x,first, last);
quicksort(x,first,(pivIndex-1));
quicksort(x,(pivIndex+1),last);
}
}
int partition(int y[], int f, int l) {
int up,down,temp;
int piv = y[f];
up = f;
down = l;
goto partLS;
do {
temp = y[up];
y[up] = y[down];
y[down] = temp;
partLS:
while (y[up] <= piv && up < l) {
up++;
}
while (y[down] > piv && down > f ) {
down–;
}
} while (down > up);
y[f] = y[down];
y[down] = piv;
return down;
}
Berikut adalah implementasi dari quick sort dalam bahasa C. Implementasinya terbagi menjadi dua prosedur, yaitu prosedur partisi dan prosedur quicksort.
void quicksort(int x[], int first, int last) {
int pivIndex = 0;
if(first < last) {
pivIndex = partition(x,first, last);
quicksort(x,first,(pivIndex-1));
quicksort(x,(pivIndex+1),last);
}
}
int partition(int y[], int f, int l) {
int up,down,temp;
int piv = y[f];
up = f;
down = l;
goto partLS;
do {
temp = y[up];
y[up] = y[down];
y[down] = temp;
partLS:
while (y[up] <= piv && up < l) {
up++;
}
while (y[down] > piv && down > f ) {
down–;
}
} while (down > up);
y[f] = y[down];
y[down] = piv;
return down;
}
Kelebihan dan Kelemahan Algoritma Quick Sort
Beberapa hal yang membuat quick sort unggul:
Beberapa hal yang membuat quick sort unggul:
- Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.
- Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti merge sort dan heap sort.
- Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.
- Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).
- Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).
- Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n2).
- Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).
- Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program.
Sumber :
