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
