Mengurutkan Data Dengan Metode Quick Sort

Quick Sort merupakan salah satu algoritma pengurutan data yang menggunakan teknik membagi  data menjadi partisi-partisi. Metode Quick Sort disebut juga dengan nama partition exchange sort. 

Untuk memulai proses pengurutan, pertama-tama sebuah data dipilih dari kelompok data sebagai data pivot. Posisi data pivot dapat dicari dengan menggunakan rumus :

    i  = (indeks awal + indeks akhir) div 2  

Kemudian elemen-elemen data akan diatur, sehingga nilai data pivot yang terletak di posisi ke I memenuhi kondisi sebagai berikut :

1. Semua data di posisi ke 1 sampai dengan ke I-1  lebih kecil atau sama dengan pivot atau data[i]<=pivot.
2. Semua data di posisi ke I+1 sampai dengan ke N  lebih besar atau sama dengan pivot atau data[i]>=pivot.

Contoh  :

Ada  12 data  sebagai berikut :  

indeks 1 2 3 4 5 6 7 8 9 10 11 12

Data        33 99 18 7 5 45 57 25 55 10 40 50

Pos = (1+12) div 2 = 6

Pivot = data[ pos]  = 45

Data 45 terpilih sebagai data pivot. Setelah diatur, maka posisi urutan data sebagai berikut :

indeks 1 2 3 4 5 6 7 8 9 10 11 12

Data        33   25 18 7 5 10   40 45 55 50 57 99

Dimana :

1. Semua elemen di posisi ke 1 sampai dengan posisi ke 8   lebih kecil atau sama dengan nilai 45.
2. Semua elemen di posisi ke 9  lebih besar atau sama dengan 45.

Dengan demikian, data tersebut akan terpecah menjadi 2 partisi, satu partisi di sisi kiri 57 dan satu partisi di sisi kanan 57 sebagai berikut :    

                                      [33   25 18 7 5 10   40  ] 45 [55 50 57 99]

Dengan cara yang sama, proses  partisi diulangi lagi untuk masing-masing partisi  baik  di sisi kanan maupun di sisi kanan. Jadi setiap partisi yang diperoleh akan dipartisi lagi hingga diperoleh hasil pengurutan data.

Dalam proses partisi dengan metode quick sort dapat selesaikan  dengan menggunakan prosedur rekursi. Karena proses partisi dengan cara sama selalu diulangi. Proses partisi dibentuk dalam sebuah prosedur atau fungsi dan akan memanggil dirinya sendiri.

Animasi dari proses Quick sort seperti pada gambar dibawah ini (sumber : www.wikipedia.com).

Kode program pascal untuk mengurutkan data dengan metode quick sort adalah sebagai berikut :

program quicksorting;
uses
crt;
type
Matrix = array[1..100] of integer;

Procedure input(var d:matrix;var n :integer);
var
code,k :integer;
i:string;
begin
  randomize;
  write(' Jumlah data  = ');readln(n);
  for k:=1 to n do
    Begin
      d[k]:=random(100);
      write(d[k], '  ');
    End; writeln;
end;

Procedure tukardata(var a,b : integer);
var t :integer;
begin
    t:=a;a:=b;b:=t;
end;

Procedure cetak(d:matrix;c:integer);
var
i:integer;
begin
   for i:=1 to c do
   write(d[i]:5);
   writeln;
end;

procedure quicksort(var d:matrix; a,b:integer);
var
a1,b1,pivot: integer;
begin
   a1:=a; b1:=b;
   pivot:=d[(a+b) div 2];
   repeat
     while(d[a1]     while(d[b1]>pivot) do dec(b1);
     if (a1<=b1) then
        begin
          tukardata(d[a1],d[b1]);
          inc(a1);
          dec(b1);
        end;
   until (a1>b1);

   cetak(d,b);
   if (a < b1) then quicksort(d, a, b1);
   if (a1 < b ) then quicksort(d,a1, b);
end;

{Program Utama}
var
data :matrix;
n:integer;
begin
clrscr;
  input(data,n);
  writeln('Proses Sorting Data');
  cetak(data,n);
  quicksort(data,1,n);
  writeln;
  writeln('Hasil Sorting Data ');
  cetak(data,n);
  readkey;
end.

Output  program :

Program di atas menghasilkan Ascending.  Anda dapat membuat program dengan hasil Descending dengan cara mengubah  operator pembanding dengan kebalikannya. Demikian algoritma pengurutan data dengan metode quick sort.Selamat mencoba. Semoga bermanfaat.

Materi yang terkait :

• Program Buble Sort
• Algoritma Pengurutan Data
• Algoritma Pencarian Data Dengan Metode Interpolasi
• Program Pencarian Data Dengan Binary Search
• Program Binary search dengan fungsi dan prosedur