Algoritma Quick Sort
A. Pengertian
Quick Sort adalah algoritma pengurutan yang sangat cepat
dengan tipe penyelesaian divide and conquer untuk untuk membagi list kedalam
sublist sehingga cocok untuk mengurutkan data dalam jumlah besar. List
yang akan diurutkan (a) dipartisi dalam dua bagian, sedemikian sehingga semua
elemen dari bagian pertama (b) lebih kecil dari atau sama dengan semua elemen
dari bagian kedua (c) (divide). Kemudian dua bagian tsb diurutkan secara
terpisah dengan penerapan rekursif dari prosedur yang sama (conquer).
Rekombinasi dari dua bagian menghasilkan list yg terurut (combine).
B. Metode Pengurutan Quick Sort
Dari ilustrasi diatas dapat dilihat bahwa pivotadalah elemen yang ditandai dengan warna merah, dalam pengoperasiannya elemen yang lebihbesar dari elemen pivot akan dipindah ke sebelah kanan pivot dann yang lebih kecil akan dipindah kesebelah kiri pivot, proses ini disebut dengan proses partitioning dan akan mengasilkan dua partisiarray, yaitu partisi yang lebih besar dari pivot dan partisi yang lebih kecil dari pivot. Proses diataskemudian dilakukan lagi pada masing-masing paritisi, sehingga mengasilkan partisi-partisi yang lain,seperti pada gambar di atas.
Azon Profit Master
secara ringkas, algoritma Quick Sort adalah sebagai berikut:
- Pilih elemen pivot.
- Pindahkan elemen array yang lebih kecil dari elemen pivot ke sebelah kiri pivot, dan elemen yang lebih besar dari lemen pivot ke sebelah kanan pivot.
- Ulangi langkah 1 dan 2 untuk masing masing partisi yang terbentuk dari langkah
C. Contoh Soal Quick Sort dan Cara Menyelesaikan
Diketahui :
Bila terdapat data acak sebagai berikut :
Ditanya :
16 12 23 50 19 49 31
Data tersebut akan diselesaikan dengan metode quicksort secara descending.
Jawab:
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
D. Algoritma Quick Sort menggunakan bahasa pemrograman Pascal :
#include <stdio.h>
#define MAX 11
#define MaxStack 11
int Data[MAX];
// Prosedur menukar data
void Tukar (int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Prosedur pengurutan metode Quick Sort
void QuickSortNonRekursif()
{
struct tump {
int Kiri;
int Kanan;
}
Tumpukan[MaxStack];
int i, j, L, R, x, ujung = 1; Tumpukan[1].Kiri = 0;
Tumpukan[1].Kanan = MAX-1;
while (ujung!=0){
L = Tumpukan[ujung].Kiri;
R = Tumpukan[ujung].Kanan;
ujung--;
while(R > L){
i = L;
j = R;
x = Data[(L+R)/2];
while(i <= j){
while(Data[i] < x)
i++;
while(x < Data[j])
j--;
if(i <= j){
Tukar(&Data[i], &Data[j]);
i++;
j--;
}
}
if(L < i){
ujung++; Tumpukan[ujung].Kiri = i;
Tumpukan[ujung].Kanan = R;
}
R = j;
}
}
}
int main()
{
int i;
//Memasukkan data yang belum terurut
printf("DATA SEBELUM TERURUT : \n");
for(i=1; i<MAX; i++)
{
printf("Data ke %d : ", i);
scanf ("%d", &Data[i]);
}
QuickSortNonRekursif();
//Data setelah terurut
printf("\nDATA SETELAH TERURUT");
for(i=1; i<MAX; i++)
{
printf("\nData ke %d : %d ", i, Data[i]);
}
//scanf("%d");
return(0);
}
E. Hasil dari Pemrogaman diatas kurang lebih seperti :
Semoga bermanfaant ^^
Tidak ada komentar:
Posting Komentar