Kompleksitas Algoritma II

Bubble Sort

Algoritma ini merupakan algoritma pencarian, dimulai dengan memindai sebuah item pada larik satu per satu, lalu membandingkannya dengan setiap item lainnya. Proses akan berhenti atau berlanjut ke item selanjutnya jika kedua nilai item tidak sesuai urutan sehingga perlu ditukarkan nilainya.

PROSEDUR bubblesort(input a1,a2,...,an: integer)
KAMUS 
    i, j, x: integer;
ALGORITMA
    for i ← 1 to n-1 do
        for j ← n-1 downto i do
            if a[j-1] > a[j] then
                x ← a[j-1]
                a[j-1] ← a[j]
                a[j] ← x
        endfor
    endfor

Operasi Dasar	Cn
	Best Case	Worst Case
>	n2	n2

Tmin = n2
Tmax = n2
Tavg = n2

Selection Sort

Metode ini membagi larik masukan ke dalam dua bagian: sublist item sudah diurutkan, yang dibangun dari kiri ke kanan di depan (kiri) dari daftar, dan sublist dari item yang tersisa akan diurutkan yang menempati sisa daftar. Awalnya, sublist diurutkan kosong dan sublist disortir adalah seluruh daftar masukan. Prosesnya adalah dengan menemukan nilai terkecil (atau terbesar, tergantung pada pemilahan order) elemen dalam sublist disortir, bertukar (swapping) dengan elemen disortir paling kiri (memasukkannya dalam rangka urutan), dan memindahkan batas sublist satu unsur ke kanan.

PROSEDUR selectionsort(input a1,a2,...,an: integer)
KAMUS 
    i, j, k, x: integer
ALGORITMA
    for i ← 0 TO n-2 do
        k ← i
        x ← a[i]

        for j ← i+1 to n-1 do
        if a[j] < x then
            k ← j
            x ← a[k] 
        endfor

        a[k] ← a[i]
        a[i] ← x
    endfor

Operasi Dasar	Cn
	Best Case	Worst Case
<	n2	n2

Tmin = n2
Tmax = n2
Tavg = n2

Quick Sort

Quicksort didasari pemikiran bahwa pertukaran nilai sebaiknya dilakukan dengan jarak yang besar agar efektif. Asumsikan bahwa item dengan jumlah n diberikan dalam urutan terbalik dari kunci mereka. Hal ini memungkinkan untuk mengurutkan item-item dengan hanya melakukan n / 2 pertukaran, pertama mengambil paling kiri dan paling kanan dan secara bertahap maju dari dua sisi. Secara normal, hal ini hanya mungkin jika urutannya terbalik. 

PROSEDUR quicksort(input a1,a2,...,an: integer, L: integer, R: integer)
KAMUS
    i, j: integer; w, x: Item
ALGORITMA
    i ← L; 
    j ← R;
    x ← a[(L+R) / 2];

    repeat
    while a[i] < x do 
        while x < a[j]
            if i <= j then
                w ← a[i]
                a[i] ← a[j]
                a[j] ← w
                i    ← i+1
                j    ← j-1
            endif

            j ← j + 1
        endwhile

        i ← i + 1
    until i > j

    if L < j then 
        quicksort(a, L, j)
    if i < R then 
        quicksort(a, i, R)

Bedasarkan algoritma diatas, kompleksitas algortima dapat dihitung sebagai berikut.

Operasi Dasar	Cn
	Best Case	Worst Case
<=	n log n	n2

Tmin = n log n
Tmax = n2
Tavg = n log n

Binary Search

Pencarian biner (binary search atau half-interval search) adalah algoritma yang melakukan pencarian terhadap data yang telah diurutkan terlebih dahulu. Algoritma pencarian biner dimulai dengan membandingkan nilai yang dicari dengan nilai elemen tengah dari larik diurutkan. Jika nilai target sama dengan nilai elemen tengah, maka posisi diberikan dan pencarian selesai. Jika nilai target kurang dari nilai elemen tengah, maka pencarian terus di bagian bawah dari larik; atau jika nilai target lebih besar dari nilai elemen tengah, maka pencarian terus di bagian atas dari larik. Proses ini terus berlanjut, menghilangkan setengah dari elemen-elemen pada larik, dan membandingkan nilai target untuk nilai elemen tengah elemen yang tersisa - sampai nilai target baik ditemukan (dan posisi elemen yang terkait dikembalikan), atau sampai seluruh elemen yang dimiliki telah dipindai dan tidak ditemukan.

PROCEDURE BinarySearch(input a1,a2,...,an: integer, x : integer, output idx : integer)

KAMUS
   i, j, mid : integer
   ketemu : boolean

ALGORITMA
   i ← 1
   j ← n
   ketemu ← false

    while (not ketemu) and ( i <= j) do 
        mid ← (i+j) div 2   
        
        if amid = x then 
            ketemu ← true
        else
            if amid < x then
                i←mid + 1
            else
                j←mid - 1;
            endif
        endif
    endwhile 
   
    if ketemu then
        idx←mid
    else
        idx←0 
    endif

Operasi Dasar	Cn
	Best Case	Worst Case
←	1	log n

Tmin = 1
Tmax = log n
Tavg = log n  

Menampilkan Bilangan Prima

PROCEDURE tampil_prima(input min, max : integer)

ALGORITMA
    for min to n do
        if (min > 1 and (min <= 3 or (min%2 != 0 and min%3 != 0)))
            print(min)
        endif
    endfor

Operasi Dasar	Cn
	Best Case	Worst Case
print	0	n

Tmin = 0
Tmax = n
Tavg = n