Analisis Algoritma QuickSort


1. Pendahuluan

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

2. Permasalahan

Algoritma quicksort bekerja menurut prinsip bagi-dan-pecahkan (divide-and-conquer). Dengan demikian hal mendasar dalam algoritma quicksort adalah pemilihan poros (pivot) dan pembuatan partisi sedemikian rupa sehingga elemen dengan nilai kecil ada di bagian kiri poros dan elemen dengan nilai besar ada di bagian kanan poros.

Berbagai varian dari quicksort pada intinya berupaya untuk mengembangkan teknik-teknik pembuatan partisi yang efektif untuk berbagai macam masukan. Hal ini merupakan bahan yang terus dipelajari hingga kini. Ditambah pula dengan perbaikan dari segi pemrograman sehingga lebih efisien (seperti mengurangi operasi pembandingan, pertukaran maupun perulangan).

Pada tahun 1998 M.D. McIlroy membuat tulisan berjudul “A Killer Adversary for Quicksort” yang menguraikan cara untuk membuat susunan data tertentu (dalam array) hingga operasi pengurutan menggunakan quicksort mendekati kuadratik O(n2). Cara ini berlaku untuk setiap varian dari quicksort dengan syarat tertentu. Dikenal juga dengan istilah antiqsort.

Makalah ini akan membahas beberapa varian quicksort yang tersedia luas dan mengujinya terhadap berbagai susunan data tertentu, termasuk juga antiqsort, untuk memperlihatkan kompleksitas dari quicksort yang sesungguhnya.

3. Algoritma Quicksort

3.1. Divide and Conquer

Divide and conquer adalah metode pemecahan masalah yang bekerja dengan membagi (divide) masalah menjadi beberapa sub-masalah yang sama atau berhubungan, hingga masalah tersebut menjadi sederhana untuk dipecahkan (conquer) secara langsung. Pemecahan dari tiap-tiap sub-masalah kemudian digabungkan untuk memberikan solusi terhadap masalah semula[6].

Metode divide and conquer menawarkan penyederhanaan masalah dengan pendekatan tiga langkah sederhana: pembagian masalah menjadi sekecil mungkin, penyelesaian masalah-masalah yang telah dikecilkan, kemudian digabungkan kembali untuk mendapat solusi optimal secara keseluruhan. Khusus untuk quicksort, proses penggabungan (combine) tidak perlu dilakukan, karena sudah terjadi secara alami.

Dalam penerapannya metode ini dilakukan secara rekursif, yaitu memanggil dirinya sendiri. Cara pemanggilan ini memanfaatkan mekanisme stack dalam menyimpan data yang sedang diproses. Namun bisa juga dengan versi non-rekursif yaitu dengan membuat struktur data tertentu yang meniru cara kerja stack.

3.2. Algoritma

Prinsip dalam algoritma quicksort sebagai berikut (diuraikan pula oleh Sedegwick[4]):

  1. Bila elemen dalam array kurang dari jumlah tertentu (biasanya 2), proses selesai.
  2. Ambil sebuah elemen yang berfungsi sebagai poros.
  3. Pisahkan array dalam 2 bagian, sebelah kiri lebih kecil dari poros, sebelah kanan lebih besar dari poros.
  4. Ulangi proses secara rekursif pada tiap-tiap bagian.

Hal penting dari hal algoritma ini adalah: bagaimana memilih poros dengan tepat dan secara efisien mengatur tiap-tiap elemen sehingga didapat elemen kecil > poros > elemen besar dalam kondisi (mendekati) seimbang. Listing algoritma dalam bentuk program akan ditunjukkan dalam bab 5.

> Poros

Poros

< Poros

 

> Poros

P

< Poros

 

. . .

3.3. Kompleksitas

Kebutuhan waktu dari quicksort bergantung pada pembuatan partisi, seimbang atau tidak, yang bergantung juga pada elemen yang digunakan sebagai poros. Dalam menghitung kompleksitas ini, perlu dilihat pula perhitungan recurrence, karena terdapat fungsi rekursif untuk penyelesaian sub-masalah.

Terdapat 3 jenis kompleksitas waktu dari quicksort[2]:

  1. Kasus terburuk (worst case), yaitu terjadi bila terbentuk partisi dengan komposisi sub-masalah antara n – 1 elemen dan 0 elemen. Dengan demikian pemanggilan fungsi secara rekursif dengan array berukuran 0 akan langsung kembali, T(0) = Θ(1), sehingga berlaku: T(n) = T(n – 1) + cn = O(n2).
  2. Kasus terbaik (best case), yaitu terjadi bila terbentuk partisi dengan dengan komposisi seimbang, dengan ukuran masing-masing tidak lebih dari n/2. Sehingga didapat: T(n) = 2T(n/2) + cn = na + cn log n = O(n log n).
  3. Kasus rata-rata (average case), yaitu terjadi dari perimbangan poros antara terbaik dan terburuk, yang dalam prakteknya lebih mendekati kasus terbaik ketimbang terburuk. Sehingga didapat: Tavg(n) = O(n log n).

4. Program Pendukung

Untuk membantu pengujian dibuatlah sebuah program khusus[7]. Baik program maupun penerapan algoritma quicksort menggunakan bahasa Object Pascal, khususnya menggunakan Borland Delphi. Bahasa Pascal mudah dimengerti dan cukup mewakili dalam penulisan algoritma.

4.1. Class TQuickSort

Untuk menyeragamkan penulisan tiap-tiap algoritma, dibuat sebuah common class, yaitu TQuickSort. Class ini berisi fungsi-fungsi yang ada dalam tiap-tiap algoritma quicksort dan melakukan pencatatan statistik tiap kali dipanggil. Berikut isi rutin-rutin tersebut:

  • Compare (X, Y), yaitu membandingkan X dan Y dengan hasil negatif bila lebih kecil, 0 bila sama, dan positif bila lebih besar.
  • Exchange (X, Y), yaitu menukar variabel pada posisi X dan Y.
  • CheckStack, yaitu mengecek banyaknya pemanggilan diri sendiri (rekursif) yang dilakukan. Pengecekan ini dengan melihat posisi stack (ESP), apabila berbeda dari posisi sebelumnya maka kedalaman rekursif telah bertambah.
  • Sort, yaitu fungsi publik yang melakukan operasi pengurutan. Sebelumnya array masukan disalin ke buffer internal, memanggil fungsi quicksort, dan mengecek hasil apakah telah urut. Keluaran dari fungsi ini berupa string statistik hasil.
  • AntiSort, yaitu fungsi publik untuk mengisi array dengan susunan angka sesuai algoritma antiqsort[5]. Hasil array ini akan diurutkan kembali tahap berikutnya.

Setiap implementasi algoritma quicksort diturunkan dari class TQuickSort, dengan mendefinisikan ulang (override) prosedur abstrak quicksort. Ketika dijalankan (fungsi Sort), setiap algoritma yang didaftarkan akan dipanggil dan hasilnya ditampilkan dalam TMemo.

TQuickSort = class private FExchange, FCompare, FRecursive, FStackPtr: Integer; FSolid, FCandidate, FGas: Integer; FBuffer, FVal: array of Integer; procedure Exchange(X, Y: Integer); function Compare(X, Y: Integer): Integer; procedure CheckStack; protected procedure QuickSort(Awal, Akhir: Integer); virtual; abstract; public function Sort(var Buffer: array of Integer): string; procedure AntiSort(var Buffer: array of Integer); property ProcDebug: TProcDebug read FProcDebug write FProcDebug; end; TQSStandard = class(TQuickSort) { contoh implementasi } protected procedure QuickSort(Awal, Akhir: Integer); override; end;

4.2. Tata Cara Pemanggilan Subrutin

Cara kerja subrutin perlu diketahui, sehubungan terdapatnya fungsi yang rekursif. Bila tidak ditentukan secara jelas, di Delphi suatu subrutin menggunakan cara panggil (calling convention) melalui register dan stack. Seluruh parameter merupakan kelipatan 32 bit, sehingga parameter minimal berukuran Integer 32 bit. Untuk 3 parameter pertama menggunakan register EAX, ECX dan EDX, sedangkan sisanya melalui stack.

Delphi juga melakukan optimasi pada variabel lokal, yaitu menggunakan register untuk 4 variabel 32 bit tertentu, yang disimpan pada register EDI, ESI, EBX dan EBP. Sebelumnya isi ketiga register ini disimpan dalam stack untuk nantinya diambil kembali. Telah tersimpan pula alamat kembali (EIP).

Sehingga isi stack ketika “procedure TQuickSort.QuickSort(L, R: Integer)” siap untuk dimulai adalah: <== ESP [EBP][EDI][ESI][EBX][EIP] dengan register EAX berisi pointer class TQuickSort, ECX berisi R dan EDX berisi L. Berhubung L dan R isinya perlu dipertahankan, disiapkan ruang 8 byte untuk ini. Total ruang stack yang digunakan untuk tiap prosedur dipanggil adalah 28 byte.

4.3. Susunan Input

Ada 6 jenis pengaturan array sebagai input:

  • Acak, yaitu array berisi angka-angka acak yang didapat dari fungsi Random dengan cakupan kontanta MaxInt (0 s/d 2147483647). Contoh: [942396755][2105178787][331691830][84570131][395984481].
  • Terbatas, yaitu array berisi angka-angka yang berasal dari indeks naik dan di-and-kan dengan 15 (indeks and 15). Contoh: [14][15][0][1][2].
  • Tetap, yaitu array berisi hanya 1 angka (didapat dari fungsi Random). Contoh: [381086676][381086676][381086676][381086676][381086676].
  • Urut Naik, yaitu array berisi angka-angka naik berturutan sesuai indeks array. Contoh: [0][1][2][3][4].
  • Urut Turun, yaitu array berisi angka-angka turun berturutan sesuai indeks array terbalik. Contoh: [4][3][2][1][0].
  • Anti QSort, yaitu hasil dari algoritma antiqsort, sehingga dihasilkan array dengan susunan tertentu yang diharapkan mendekati worst-case bila diurutkan.

5. Percobaan dan Analisa

Menggunakan class TQuickSort, yang diturunkan dalam bermacam-macam algoritma, dilakukan pengujian unjuk kerja. Hal-hal yang dipantau adalah:

  • Pembandingan, yaitu berapa banyak terjadi pembandingan antara 2 elemen. Setiap operasi pembandingan, baik dalam mencari elemen ataupun poros, akan dicatat.
  • Penukaran, yaitu berapa banyak terjadi pertukaran antara 2 elemen.
  • Rekursif, yaitu berapa dalam terjadi pemanggilan stack (dalam proses rekursif).
  • Waktu, yaitu berapa lama (dalam milidetik) suatu algoritma berjalan. Waktu yang dibutuhkan suatu algoritma tidak selalu berbanding lurus dengan operasi pembandingan, pertukaran, maupun rekursif.

Akibat pengembangan quicksort sudah sedemikian rupa, sehingga asal-usul dan bentuk algoritma tidak diketahui asalnya. Dalam hal ini hanya diambil beberapa contoh quicksort yang dianggap cukup mewakili sebagai percobaan.

Dalam melakukan pengambilan waktu tidak dilakukan hasil rata-rata, melainkan pada 1x hasil saja. Hal ini disebabkan pengambilan contoh (sampling) array sudah cukup mewakili, yaitu 1.000.000 angka Integer (4 byte), kecuali 10.000 angka untuk algoritma (partisi) Lomuto dan antiqsort.

Program uji coba dijalankan di sistem operasi Windows XP, prosesor AMD Sempron 1,8GHz, dan memori 512 MB.

5.1. Algoritma Lomuto

Algoritma ini terdapat dalam buku teks “Introduction to Algorithm”[2], hasil karya N. Lomuto. Merupakan penerapan quicksort yang paling sederhana dan mudah dipahami. Dari hasil pengujian diketahui hasilnya yang paling buruk.

procedure TQSLomuto.QuickSort(Awal, Akhir: Integer); function Partition(L, R: Integer): Integer; var J, P: Integer; begin P := FBuffer[R]; Result := L – 1; for J := L to R-1 do if Compare(FBuffer[J], P) <= 0 then begin Inc(Result); Exchange(Result, J); end; Inc(Result); Exchange(Result, R); end; var P: Integer; begin CheckStack; if (Awal < Akhir) then begin P := Partition(Awal, Akhir); QuickSort(Awal, P-1); QuickSort(P+1, Akhir); end; end;

Pada algoritma ini pivot diambil pada angka paling kanan di array. Secara rekursif partisi dibentuk dengan menukarkan angka-angka yang kecil di sebelah kiri dari pivot dan angka-angka yang lebih besar di kanan, hingga tidak terdapat angka yang dapat dipartisi (Awal = Akhir).

Susunan

Banyak

Pembandingan

Penukaran

Rekursif

Waktu

Kompleksitas

Acak

10.000

163.856

97.640

34

0

O(n log n)

Tetap

10.000

49.995.000

50.004.999

10.000

1.187

O(1/2 n2)

Terbatas

10.000

3.204.360

3.204.984

640

78

O(n log n)

Urut Naik

10.000

49.995.000

50.004.999

10.000

1.171

O(n2)

Urut Turun

10.000

49.995.000

25.004.999

10.000

875

O(n2)

Anti Sort

10.000

49.985.002

10.000

9.999

531

O(n2)

Terlihat hanya pada susunan array yang acak kondisi rata-rata O(n log n) tercapai, sedangkan pada susunan lainnya masuk pada kasus terburuk. Pada susunan acak terbatas meskipun total pengecekan dan penukaran cukup jauh dari O(n log n) tetapi karena masih jauh dari ambang O(n2) ini tetap dianggap O(n log n). Tingkat rekursivitas menunjukkan pula bahwa pada kasus terburuk kedalamannya sebanding dengan input, sehingga waktu pengulangan (recurrence): T(n) = T(n-1) + Θ(n).

5.2. Algoritma Standar

Algoritma ini terdapat dalam buku versi PDF “The Tomes of Delphi, Algorithm and Data Structures”[1]. Pengembangan yang dilakukan algoritma ini adalah :

  • Menyatukan antara rutin partisi dan pengulangan, sehingga menghemat stack.
  • Mengambil posisi pivot di tengah array, yaitu (Awal + Akhir) div 2.
  • Menghemat proses rekursif dengan hanya melakukannya pada partisi sebelah kiri. Untuk partisi sebelah kanan cukup dengan menaikkan nilai Awal dan kembali ke awal loop.

procedure TQSStandard.QuickSort(Awal, Akhir: Integer);
var
LT, RT, Pivot: Integer;
begin
CheckStack;
while (Awal < Akhir) do begin
Pivot := FBuffer[(Awal + Akhir) div 2];
LT := Awal – 1; RT := Akhir + 1;
repeat
repeat Dec(RT); until Compare(FBuffer[RT], Pivot) <= 0;
repeat Inc(LT); until Compare(FBuffer[LT], Pivot) >= 0;
if (LT < RT) then Exchange(LT, RT);
until LT >= RT;
if (Awal < RT) then QuickSort(Awal, RT);
Awal := RT + 1;
end;
end;

Susunan

Banyak

Pembandingan

Penukaran

Rekursif

Waktu

Kompleksitas

Acak

1.000.000

27.676.697

5.741.027

29

360

O(n log n)

Tetap

1.000.000

21.769.982

9.884.992

20

312

O(n log n)

Terbatas

1.000.000

23.291.850

9.715.427

23

312

O(n log n)

Urut Naik

1.000.000

20.951.423

0

20

172

O(n log n)

Urut Turun

1.000.000

20.951.424

500.000

20

187

O(n log n)

Anti Sort

10.000

50.024.997

9.999

1

360

O(1/2 n2)

Kecuali antiqsort, keseluruhan proses masih dalam ambang kompleksitas O(n log n), yaitu 19.931.568. Pada array dengan susunan tetap, terbatas, urut naik dan urut turun, waktu yang dibutuhkan relatif sama, bahkan tidak terjadi pertukaran isi array untuk urut naik. Khusus antiqsort, lama proses adalah ½ dari kuadratik, sehingga banyak array dikurangi. Dari sisi waktu, di luar antiqsort, waktu terlama adalah untuk susunan acak. Ini sebanding dengan operasi perbandingan yang terbanyak dibanding lainnya.

Algoritma standar ini cukup efisien dalam melakukan proses rekursif. Dengan jumlah elemen pada array sebanyak 1.000.000 hanya terjadi kedalaman rata-rata berkisar 30-an, yang tertinggi didapat pada array dengan susunan acak. Bila tiap pemanggilan subrutin membutuhkan 28 byte, maka total hanya 30 * 28 = 840 byte.

5.3. Algoritma Poros Acak

Pemilihan poros yang baik menjadi kunci dalam efisiensi dalam algoritma quicksort. Pengembangan lebih lanjut dari versi standar adalah dengan mengambil elemen poros secara acak (dengan fungsi Random) antara awal dan akhir dan menukarnya dengan elemen di tengah array.

procedure TQSStandardRandom.QuickSort(Awal, Akhir: Integer); while (Awal < Akhir) do begin RT := Awal + Random(Akhir – Awal + 1); { RT = posisi acak } LT := (Awal + Akhir) div 2; { LT = posisi tengah } Exchange(RT, LT); { tukarkan tengah dan acak } end; end;

Susunan

Banyak

Pembandingan

Penukaran

Rekursif

Waktu

Kompleksitas

Acak

1.000.000

28.872.089

5.695.245

34

391

O(n log n)

Tetap

1.000.000

21.769.982

10.884.991

20

328

O(n log n)

Terbatas

1.000.000

22.615.269

9.757.808

23

329

O(n log n)

Urut Naik

1.000.000

28.395.563

1.704.095

33

265

O(n log n)

Urut Turun

1.000.000

20.951.424

500.000

20

172

O(n log n)

Anti Sort

10.000

193.642

41.438

21

0

O(n log n)

Dari hasil uji coba tidak terlihat adanya peningkatan efisiensi dibanding versi standar. Kecenderungan yang terjadi kedalaman rekursif justru meningkat, terutama untuk array dengan susunan urut naik dan urut turun. Pada kondisi data sudah terurut, karena penukaran poros dengan elemen secara acak, mengakibatkan terjadi operasi pengurutan ulang yang tidak perlu. Dengan melihat tambahan biaya untuk fungsi Random dan penukaran tersebut maka teknik poros acak ini kurang bermanfaat.

Namun hal menarik dari versi ini adalah tidak terpengaruh dengan susunan array hasil antiqsort, yaitu kompleksitasnya tetap minimal, atau sebanding dengan susunan acak. Berhubung rekayasa dari antiqsort relatif jarang terjadi, secara keseluruhan versi poros acak ini cenderung tidak efisien.

5.4. Algoritma Poros Tengah dari Tiga (Median of Three)

Cara lain untuk mengambil elemen poros adalah dengan melakukan penyusunan awal, tengah dan akhir dari array pada setiap proses partisi menjadi terurut. Berikut langkah-langkahnya:

1.

333

222

111

Banding dan tukarkan awal dan tengah

2.

222

333

111

Banding dan tukarkan tengah dan akhir

3.

222

111

333

Banding dan tukarkan awal dan tengah

4.

111

222

333

Posisi terurut awal, tengah, dan akhir

procedure TQSStandardMedianOfThree.QuickSort(Awal, Akhir: Integer); var LT, RT, Pivot: Integer; begin while (Awal < Akhir) do begin RT := (Awal + Akhir) div 2; { RT = tengah } if (Compare(FBuffer[Awal], FBuffer[RT]) > 0) then Exchange(Awal, RT); { awal dan tengah } if (Compare(FBuffer[RT], FBuffer[Akhir]) > 0) then Exchange(RT, Akhir); { tengah dan akhir } if (Compare(FBuffer[Awal], FBuffer[Tengah]) > 0) then Exchange(Awal, Tengah); { awal dan tengah } end; end;

Susunan

Banyak

Pembandingan

Penukaran

Rekursif

Waktu

Kompleksitas

Acak

1.000.000

27.331.126

5.014.477

27

360

O(n log n)

Tetap

1.000.000

24.769.979

9.884.992

20

328

O(n log n)

Terbatas

1.000.000

26.095.024

8.716.097

23

344

O(n log n)

Urut Naik

1.000.000

23.951.420

0

20

187

O(n log n)

Urut Turun

1.000.000

23.951.421

500.002

20

203

O(n log n)

Anti Sort

10.000

25.059.992

4.998

2

219

O(1/4 n2)

Hasil dari pemilihan poros melalui ‘median of three’ ini tidak membawa banyak pengaruh. Hanya terlihat kedalaman rekursif cenderung minimal, dibanding versi standar maupun poros random, dengan tambahan biaya untuk operasi pembandingan dan penukaran. Namun hal yang lebih baik adalah dalam menghadapi susunan antiqsort, yaitu hanya ¼ dari kuadratik.

5.5. Algoritma Poros Dinamis

Berkembang pula cara untuk menentukan poros secara dinamis, yaitu:

  • Bila array di bagian kiri kosong (Kiri = Poros), maka geser Poros ke Kanan.
  • Bila array di bagian kanan kosong (Kanan = Poros), maka geser Poros ke Kiri.

Dengan bergerak lebih dinamis, diharapkan distribusi elemen sebagai poros lebih bervariasi, dan mengurangi terjadinya kasus terburuk.

procedure TQSStringListDelphi.QuickSort(Awal, Akhir: Integer); var LT, RT, Pv: Integer; begin CheckStack; while Awal < Akhir do begin LT := Awal; RT := Akhir; Pv := (Awal + Akhir) shr 1; while LT <= RT do begin while Compare(FBuffer[LT], FBuffer[Pv]) < 0 do Inc(LT); while Compare(FBuffer[RT], FBuffer[Pv]) > 0 do Dec(RT); if LT > RT then Break; if (LT <> RT) then Exchange(LT, RT); if Pv = LT then Pv := RT else if Pv = RT then Pv := LT; Inc(LT); Dec(RT); end; if Awal < RT then QuickSort(Awal, RT); Awal := LT; end; end;

Susunan

Banyak

Pembandingan

Penukaran

Rekursif

Waktu

Kompleksitas

Acak

1.000.000

27.218.424

4.623.697

31

391

O(n log n)

Tetap

1.000.000

19.142.656

9.095.616

19

297

O(n log n)

Terbatas

1.000.000

20.995.476

8.295.499

22

313

O(n log n)

Urut Naik

1.000.000

19.000.019

0

19

157

O(n log n)

Urut Turun

1.000.000

19.000.036

500.000

19

172

O(n log n)

Anti Sort

10.000

25.029.991

5.001

2

203

O(1/4 n2)

Terlihat secara umum terjadi penurunan banyaknya pembandingan dan penukaran dibanding versi standar, acak, maupun tengah-dari-tiga. Meski begitu, untuk kondisi array susunan acak, waktu yang dibutuhkan menjadi lebih lama. Ini akibat nilai poros yang direferensikan langsung, Compare(FBuffer[RT], FBuffer[Pv]), dibanding versi standar, Compare(FBuffer[RT], Pivot). Versi ini juga bermasalah dalam hal antiqsort, sebanding dengan tengah-dari-tiga, yaitu ¼ kuadratik.

5.6. Algoritma Rekursif Minimal

Pengembangan akhir dari versi standar adalah mengurangi banyaknya fungsi rekursif yang dilakukan. Bila sebelumnya fungsi rekursif selalu dikerjakan untuk bagian kiri (bila Awal < Kanan), hal ini bisa dioptimalkan untuk bekerja pula pada bagian kanan, dengan tujuan mengolah array yang lebih besar. Contoh prosedur berikut disertakan banyak komentar agar lebih jelas.

procedure TQSMinRekursifDelphi.QuickSort(Awal, Akhir: Integer); var LT, RT, Pv: Integer; begin CheckStack; { selagi awal < akhir } while Awal < Akhir do begin LT := Awal; RT := Akhir; Pv := (LT + RT) div 2; while LT < RT do begin { cari angka di kiri lebih kecil dari pivot } while Compare(FBuffer[LT], FBuffer[Pv]) < 0 do Inc(LT); { cari angka di kanan lebih besar dari pivot } while Compare(FBuffer[RT], FBuffer[Pv]) > 0 do Dec(RT); { bila LT > RT maka berhenti } if LT > RT then Break; { tukarkan bila posisi berbeda } if (LT <> RT) then Exchange(LT, RT); { bila pivot tepat di kiri, ganti pivot ke kanan } if Pv = LT then Pv := RT { jika tidak, bila pivot tepat di kanan, ganti pivot ke kiri } else if Pv = RT then Pv := LT; { naikkan kiri dan kanan } Inc(LT); Dec(RT); end; { bila awal .. kanan > kiri .. akhir } if RT-Awal > Akhir-LT then begin { bila ada kiri .. akhir, ulangi } if LT < Akhir then QuickSort(LT, Akhir); { akhir pindah ke kanan } Akhir := RT; end else begin { bila ada awal .. kanan, ulangi } if Awal < RT then QuickSort(Awal, RT); { awal pindah ke kiri } Awal := LT; end; end; end;

Susunan

Banyak

Pembandingan

Penukaran

Rekursif

Waktu

Kompleksitas

Acak

1.000.000

27.483.556

4.648.282

14

375

O(n log n)

Tetap

1.000.000

20.191.104

10.095.552

20

328

O(n log n)

Terbatas

1.000.000

22.460.455

9.279.990

18

360

O(n log n)

Urut Naik

1.000.000

19.000.019

0

19

156

O(n log n)

Urut Turun

1.000.000

19.000.036

500.000

19

172

O(n log n)

Anti Sort

10.000

25.029.989

5.001

2

204

O(1/4 n2)

Perubahan cukup besar terjadi pada turunnya kedalaman rekursif untuk arary susunan acak, sedangkan susunan lainnya tidak banyak berbeda dibanding versi standar, poros acak, tengah-dari-tiga, dan dinamis. Meskipun secara waktu tidak banyak mengalami perubahan.

5.7. Algoritma Lain

Beberapa pengembangan lain dari algoritma quicksort seperti berikut:

  • Tidak menggunakan pemanggilan rekursif, yaitu dengan menyusun struktur data tertentu dan meniru cara kerja stack. Meskipun cara ini diklaim lebih cepat, tetapi operasi stack dalam arsitektur komputer dan sistem operasi sudah dioptimalkan sedemikian rupa sehingga berjalan sangat efisien.
  • Menggabungkan quicksort dengan algoritma pengurutan yang lain, seperti insertion-sort yang efisien untuk array yang kecil. Ditentukan titik potong tertentu, misalnya 16 elemen (bila normalnya 2), sehingga quicksort berhenti mempartisi, dan hasil akhir diserahkan kepada insertion-sort untuk mengurutkan potongan-potongan array.

Algoritma di atas tidak dibahas dalam makalah ini.

6. Kesimpulan

Hasil uji coba untuk keseluruhan algoritma, dengan besar array 10.000.000 angka, susunan acak, dihitung pada total pembandingan ditambah + penukaran (CmpXchg), pemanggilan rekursif, dan waktu (dalam satuan milidetik), adalah sebagai berikut:

Kateg.

Lomuto

Standar

Poros Acak

P Med-of-3

Pr Dinamis

Min Rek

CmpXchg

431.654.749

384.110.834

393.574.481

370.556.389

373.445.492

375.778.251

Rekursif

62

35

35

29

34

15

Waktu

6.125

4.218

4.390

4.079

4.516

4.454

clip_image002

Dari berbagai uji coba didapatkan kesimpulan sebagai berikut:

  • Algoritma quicksort, di luar partisi Lomuto yang sebatas contoh di buku teks, pada umumnya mencukupi untuk kebutuhan sorting.
  • Kompleksitas dengan kasus terburuk, yaitu O(n2), sejauh ini sulit untuk dibuktikan. Algoritma standar perlu dihindari, berdasarkan susunan array dari algoritma antiqsort, untuk memenuhi kasus terburuk O(1/4 n2).
  • Meskipun menggunakan pemanggilan rekursif, kebutuhan stack cukup minimal, yaitu dengan kedalaman 35 untuk 10.000.000 angka.

7. Referensi

  1. Julian Backnall. The Tomes of Delphi™ Algorithms and Data Structures. 5:161-175, 2001.
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 7: Quicksort, pp.145–164.
  3. Bentley and McIlroy, Engineering a sort function, Software Practice and Experience, Jan. 1993.
  4. R. Sedgewick. Implementing quicksort programs. Comm. ACM, 21:847–856, 1978.
  5. M.D. McIlroy, A Killer Adversary for Quicksort. Software Practice and Experience, Vol. 29(0), 1–4 (0 1999).
  6. Wikipedia.org, http://en.wikipedia.org/wiki/Quicksort, Tanggal: 25-11-2007.
  7. Pengujian Sorting Dengan QuickSort, Program Delphi. Tanggal: 28-11-2007. http://wawan.web.id/delphi/sort_mhk.zip.

File PDF: sorting_mhk_4.pdf

6 Komentar »

  1. Wanted to say hello
    Thanks!
    Interlock Roofing
    Interlock Industries

  2. Yogjay said

    Analisisnya sip… terima kasih

  3. Raditya said

    terima kasih atas penjelasannya..
    sukses selalu

  4. […] Clement, Flajolet, Vallee, hingga Martinez, membuat analisis dan implementasi dari quicksort. Baca selengkapnya…   Contoh Program […]

  5. […] https://oguds.wordpress.com/2007/11/28/analisis-algoritma-quicksort/ […]

  6. […] https://oguds.wordpress.com/2007/11/28/analisis-algoritma-quicksort/ […]

RSS feed for comments on this post · TrackBack URI

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: