Pengertian Quick Sort dan Contoh

Mengurutkan Data Dengan Metode Quick Sort


Sebelum masuk ke inti saya memperkenalkan diri saya dulu guys.
Nama saya Ferdy. Saya akan berbagi ilmu sedikit tentang Quick Sort.
Apakah ada yang belum tau, apa sih itu Quick Sort?
Dan bagaimana sih cara membuat codenya?
Sebelum ke inti alangkah baiknya saya jelaskan dulu apa itu 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 :
Semua data di posisi ke 1 sampai dengan ke I-1  lebih kecil atau sama dengan pivot atau data[i]<=pivot.
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 :
Semua elemen di posisi ke 1 sampai dengan posisi ke 8   lebih kecil atau sama dengan nilai 45.
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 :

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 :

Sekian dari saya.
Semoga bermanfaat bagi kalian😊
Jika ada yang salah tolong koreksi saya😂

Terima kasih😊👌

Referensi : dari berbagai sumber