Penerapan Cara menghitung Big-O pada Algoritma Sorting (Source Code Java)

 Assalmualaikum wr.wb

Alhamdulillah pada kali ini saya akan membahas tentang cara menghitung big-O / worst case dari Algoritma Sorting :

• Bubble Sort
• Merge Sort
• Quick Sort 

pada kali ini saya hanya akan membahas penerapan perhitungan big-O menggunakan aturan-aturan yang ada:

Contoh source code kali ini adalah bahasa pemrograman java. langsung cuss saja ke permasalahannya :

Perhhitungan Big-O dari masing-masing metode sorting :

1.      Bubble Sort

ALGORITMA BUBBLESORT	COST	JML LANGKAH
for(int i=0; i<list.length; i++){             for(int j=i + 1; j<list.length; j++){                 if(list[i] > list[j]){                     int temp = list[i];                     list[i] = list[j];                     list[j] = temp;                 }             }         }	C1 C2 C3 C4 C5 C6	n n-1 1 1 1 1

 

Notasi Big-O :

Aturan yang dipakai pada penghitungan Big-O di atas :

a.       Apabila terdapat perkalian, maka nilai Big-O juga perkalian dari bilangan tersebut.

b.      Apabila terdapat penjumlahan, maka yang diambil hanya bilangan yang terbesar.

 

2.      Merge Sort

ALGORITMA	COST	JML LANGKAH
int low = lo;         int high = n;             if (low >= high){         return ;         }             int middle = (low + high) / 2;         mergeSort_srt(array, low, middle);         mergeSort_srt(array, middle + 1, high);         int end_low = middle;         int start_high = middle + 1;         while ((lo <= end_low) && (start_high <= high)) {         if (array[low] < array[start_high]) {         low++;             }         else {         int Temp = array[start_high];         for (int k = start_high- 1; k >= low; k--) {           array[k+1] = array[k];         }                 array[low] = Temp;                 low++;                 end_low++;                 start_high++;             }         }	C1 C2 C3     C4 C5 C6 C7 C8 C9   C10       C11 C12 C13   C14	1 1 1     1 n log(n) n log(n) 1 1 2n   1       1 n-1 1   1

 

Notasi Big-O :

 

3.      Quick Sort

ALGORITMA	COST	JML LANGKAH
int i = low, j = high;         int temp;         int pivot = arr[(low + high) / 2];         while (i <= j) {             while (arr[i] < pivot)                 i++;             while (arr[j] > pivot)                 j--;             if (i <= j) {                 temp = arr[i];                 arr[i] = arr[j];                 arr[j] = temp;                 i++;                 j--;             }         }         if (low < j)             quickSort(arr, low, j);         if (i < high)             quickSort(arr, i, high);	C1 C2 C3 C4 C5   C6   C7 C8 C9 C10         C11 C12 C13 C14	2 1 1 n n   n   1 1 1 1         1 n log(n) 1 n log(n)

 

Notasi Big-O :

                 

      Aturan yang terdapat dalam perhitungan di atas =

a.       Konstanta otomatis dihilangkan

b.      Apabila terdapat perkalian, maka nilai Big-O juga perkalian dari bilangan tersebut.

c.       Apabila terdapat penjumlahan, maka yang diambil hanya bilangan yang terbesar.