SORTING ALGORITHM ANALYSIS

Tujuan
Tujuan dari analisa algorithma adalah untuk mengetahui efisiensi algoritma dalam hal ini yang akan dibahas adlah algorithma sorting “quick sort” terhadap algoritma “selection sort”. Analisis dilakukan dengan Tmembandingkan running time ( waktu komputasi ) antara algoritma “quick sort” terhadap algorithma “selection sort” dan jumlah proses/langkah/pembandingan data antara algoritma “quick sort” terhadap algorithma “selection sort”. Hasil analisis yang dapat adalah jumlah running time (waktu komputasi) dan jumlah proses/langkah/pembandingan data/proses untuk masing-masing algoritma.

TAHAP ANALISIS
Tahap awal analisis adalah melakukan pengecekan program untuk memastikan bahwa program telah benar secara logika maupun sintak ( tahap tracing/debugging), Tahap selanjutnya yaitu menjalankan program untuk mengetahui running time/waktu komputasi ( termasuk jumlah langkah ).
Data uji yang digunakan adalah data yang tidak terurut/random, terurut membesar/ascending, dan terurut mengecil/descending.

SELECTION SORT
PSEUDOCODE

      • If item in position J is < (or > ) item in Pos then Pos = J
    • Pos = I
      For J in I+1..N loopend loop
      If Pos /= I then swap elements in positions I and Pos

  • For I in 1..N-1 loopend loop

ANALISIS ALGORITMA DAN KOMPLEKSITAS
Pengurutan dengan pemilihan ini dilakukan dengan cara mencari suatu nilai ekstrim ( minimal /maksimal ) untuk ditukarkan dengan elemen terujung yang ada pada suatu loop proses. Kemudian elemen terujung tidak lagi diikutkan dalam proses pengurutan selanjutnya karena elemen terujung tersebut sudah merupakan data yang minimal/maksimal dalam proses pengurutan tahap 1. Proses selanjutnya dilakukan untuk data yang tersisa dalam array.
Misalnya array tersebut adalah X, maka pada setiap saat terdapat i buah data terurut pada X[0], X[1], …, X[i-1], dan data tak terurut pada X[i], X[i+1], …, X[n-1]. Algoritma melakukan pencarian X[j] terkecil dari data set yang belum terurut tersebut, misalnya didapat X[m] lalu melakukan penukaran X[i] dengan X[m] sehingga kemudian sudah terurut i+1 buat data dalam X.
Hasil pengurutan data ( mengecil/membesar ) bergantung dari nilai ektrim yang kita inginkan. Jika yang kita cari adalah nilai ektrim terkecil maka kita dapatkan array yang terurut membesar, dan begitupun sebaliknya.

ssort.PNG

Jadi total running timenya adalah:
c * n * n = cn2 = O(n^2)

QUICK SORT
PSEUDOCODE

      • //Partitioning step
        Choose a pivot and put swap it with Array[First];
        LeftPtr = First + 1;
        RightPtr = Last;
        while (RightPtr > = LeftPtr)
        while (Array[LeftPtr] < Pivot)
        increment LeftPtr;
        while (Array[RightPtr] > Pivot)
        decrement RightPtr;
        swap Array[LeftPtr] and Array[RightPtr];
        swap Array[First] and Array[RightPtr];
        //End partitioning step
        Array[First..RightPtr-1] = QuickSort(Array[First .. RightPtr-1]);
        Array[RightPtr+1..Last] = QuickSort(Array[RightPtr+1..Last]);
    • if Array contains only one element then return Array;

  • Function QuickSort (Array(First..Last))

ANALISIS ALGORITMA DAN KOMPLEKSITAS
Sesuai namanya “Quick Sort”, adalah algorithma sorting tercepat di dalam proses sorting. “Quick Sort” menggunakan “divide-and-conquer recursive algorithm”.
Algorithma dasar dalam yang dipakai untuk mengurutkan sebuah array S terdiri dari empat tahap, yaitu :

  • Jika jumlah elemen S 0 atau 1, berhenti.
  • Ambil secara acak elemen v di dalam array S. Ini yang disebut pivot.
  • Bagi menjadi 2 bagian array S, elemen selain v, menjadi 2 qroup : S1 = {x  S – {v}  x ≤ v } dan S2 = {x  S – {v}  x ≥ v }
  • Lakukan quick sort pada S1 dan diikuti S2
      Sehingga didapat persamaan :
      T(n) = 2T(n/2) + θ(n)
      Notasi 0 / Big O dapat dihitung dengan metode master :
      T(n) = 2T(n/2) + θ(n)  a = 2, b = 2 dan f(n) = θ(n) = n
      n logba = n log22 = n
      sehingga sesuai dengan kasus 2 teorema master, karena :
      n logba = n = f(n)
      jadi total running timenya adalah :
      T(n) = θ(n lg n).

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: