Mengurutkan Data Dengan Metode Quick Sort

Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. 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 :
  1.  Semua elemen di posisi ke 1 sampai dengan ke I-1 adalah lebih kecil atau sama dengan Sementara.
  2. 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 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 :










 
Tampak bahwa kondisi berikut terpenuhi, yaitu :
  1. 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.
  2. Semua elemen di posisi ke 7 sampai dengan ke 12 (57,99,55,45,40 dan 50) aka 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

Bila diamati lebih lanjut, maka quick sort dapat didefinisikan dengan lebih mudah menggunakan prosedur rekursi. Misalnya untuk partisi sebagai berikut



Maka Proses dari rekursi tampak pada pengurutan data dari bawah sampai dengan I-1 dan pengurutan I+1 sampai dengan atas.



Program rekursi untuk mengurutkan data dengan metode Quick Sort ini dapat berupa :
(* Program Quick Sort
Mengurutkan Data Dengan Metode Quick Sort secara rekursi
Stefanus Eko Prasetyo, Junaini Krisnawati, Deli, Lintang Agung, Hendry, Nico Arsanto
*)

Type
 TipeArray = string[20];
 ArrayUrut = array[1..1000] of TipeArray;

 Procedure QuickSort(var x      : ArrayUrut;
                         Bawah, Atas : word);

 var
   I, J   : word;
   Sementara : TipeArray;
 Begin
   While Atas > bawah Do
   begin
   I := Bawah;
   J := Atas;
   Sementara := X[Bawah];


   {Memecah Array menjadi 2 bagian}
   While I < J Do Begin
     While X[J] > Sementara Do J := J - 1;
     X[I] := X[J];
     While (I<J) And (X[I] <= Sementara) Do I := I + 1;
     X[J] := x[I];
   end;

   X[I] := Sementara;

   {Urutkan rekursi}
   QuickSort(X, Bawah, I-1);
   Bawah := I + 1;
 end;
end;

Var
  Nama : ArrayUrut;
  N, I : word;
Begin
  Write('Jumlah data yang akan diurutkan ?'); ReadLn(N);
  WriteLn;
  WriteLn('Masukkan data :');
  For I:=1 to N Do Begin
     Write('Data ke ',I,' ? '); ReadLn(Nama[I]);
 end;

 {urutkan dengan prosedur QuickSort}
 QuickSort(Nama,1,N);

 {Tampilkan Data yang telah diurut}
 WriteLn;

 WriteLn('Data yang telah di urut :');
 WriteLn('-------------------------');

 For I := 1 To N Do
    WriteLn(Nama[I]);

 end.


Bila Program ini dijalankan :
Jumlah data yang diurutkan ? 8
Masukkan Data :
Data ke 1 ? Dewa
Data ke 2 ? Arsanto
Data ke 3 ? Lintang
Data ke 4 ? Stefanus
Data ke 5 ? Nico
Data ke 6 ? Akbar
Data ke 7 Rudy
Data ke 8 ? Meidi




Data yang telah terurut :
--------------------------------
Akbar
Arsanto
Dewa
Lintang
Meidi
Nico
Rudy
Stefanus


                            
~~Selesai~~

Source Code dapat di Download disini

First


EmoticonEmoticon