Algoritma Quick Sort

Algoritma quicksort diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960, dan dimuat sebagai artikel di Computer Journal 5 pada April 1962. Bentuknya yang sederhana, efisien dan efektif dengan cepat membuatnya menjadi algoritma pengurutan (sorting) yang paling banyak digunakan, terutama dalam bahasa pemrograman. Berbagai penelitian dan pengembangan telah banyak dilakukan hingga saat ini. Tercatat peneliti seperti Sedgewick, Bentley, McIlroy, Clement, Flajolet, Vallee, hingga Martinez, membuat analisis dan implementasi dari quicksort.

Beberapa hal yang membuat quicksort unggul:

• Secara umum memiliki kompleksitas O(n log n).
• 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 mergesort dan heapsort.
• Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.
• Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).

Namun terdapat pula kelemahan quicksort:

• 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(n²).
• 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.

Pada bahasa pemrograman, quicksort ada dalam pustaka stdlib.h untuk bahasa C, dan class TList dan TStringList dalam Delphi (Object Pascal) maupun FreePascal.

Nah, sekarang yuk kita coba programnya...

1. Buat tampilan interface seperti gambar di bawah ini

2. Klik pada proses button
dan ketikkan syntaxnya...

unit quicksorta;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TFQuickSort = class(TForm)
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Edit1: TEdit;
    ListBox1: TListBox;
    ListBox2: TListBox;
    Button1: TButton;
    Button2: TButton;
    Button3: TButton;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
  private
    { Private declarations }
    Data:array of integer;
  public
    { Public declarations }
  end;

var
  FQuickSort: TFQuickSort;

implementation

{$R *.dfm}

procedure QuickSort(var A:array of integer;iLo,iHi:integer);
var
  Lo,Hi,Pivot,T:integer;
begin
  Lo:=iLo;
  Hi:=iHi;
  Pivot:=A[(Lo+Hi) div 2];
  repeat
    while A[Lo]<Pivot do Inc(Lo);
    while A[Hi]>Pivot do Dec(Hi);
    if Lo<=Hi then
    begin
      T:=A[Lo];
      A[Lo]:=A[Hi];
      A[Hi]:=T;
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo>Hi;
  if Hi>iLo then QuickSort(A,iLo,Hi);
  if Lo<iHi then QuickSort(A,Lo,iHi);
end;

procedure TFQuickSort.Button1Click(Sender: TObject);
var
  nilai:integer;
begin
  //menambahkan nilai ke listbox
  if TryStrToInt(Edit1.Text,Nilai) then
  ListBox1.Items.Add(IntToStr(nilai));
  //membersihkan komponen inputan nilai
  Edit1.Clear;
  //focus kursor ke inputan nilai
  Edit1.SetFocus;
end;

procedure TFQuickSort.Button2Click(Sender: TObject);
var
  indek:Word;
begin
  //menentukan panjang array
  SetLength(Data,ListBox1.Items.Count);

  //pemasukan nilai ke array
  for indek:=0 to ListBox1.Items.Count-1 do
  Data[indek]:=StrToInt(ListBox1.Items[indek]);
  //proses pengurutan/sorting
  QuickSort(data,Low(Data),High(Data));
  //kosongkan hasil
  ListBox2.Items.Clear;
  //memasukkan nilai hasil
  for indek:=0 to ListBox1.Items.Count-1 do
  ListBox2.Items.Add(IntToStr(data[indek]));
end;

procedure TFQuickSort.Button3Click(Sender: TObject);
begin
  close;
end;

end.
3. Setelah selesai, Cek hasil program tersebut...