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 membandingkan 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

For I in 1..N-1 loop
Pos = I
For J in I+1..N loop
If item in position J is < (or > ) item in Pos then Pos = J

end loop
If Pos /= I then swap elements in positions I and Pos

end 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.

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

QUICK SORT
PSEUDOCODE

Function QuickSort (Array(First..Last))
if Array contains only one element then return Array;
//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]);

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).

Lebih detail tantang uji unjuk kerja silahkan akses disini.

Inlinks:

• Data Security
• MD5 and SHA-1 ( Hash Function Chryptography )
• Apa itu Algorithms?
• SORTING ALGORITHM #1
• SORTING ALGORITHM ANALYSIS
• Sejarah Kriptografi
• Keamanan Informasi dan Kriptografi
• Quick-sort Source-Code
• Merge-sort Source-Code
• Insertion-sort Source-Code
• Selection-sort Source-Code
• Heap-sort Source-Code
• Bubble-sort Source-Code
• Enkripsi RC4 part 2
• Matrix-Chain-Multiply Source-Code
• Matrix-Chain-Order
• LINEAR DISCRIMINANT ANALYSIS (LDA)