BAB II TINJAUAN PUSTAKA

6

BAB II TINJAUAN PUSTAKA

2.1.

Algoritma

Algortima adalah jantung ilmu komputer atau informatika. Banyak cabang dari ilmu komputer yang diacu dalam terminologi algoritma, misalnya algoritma perutean (routing) pesan di dalam jaringan komputer, algoritma berensenham untuk menggambar garis lurus (bidang grafik kumputer), algoritma Knuth-Morris-Pratt untuk mencari suatu pola di dalam teks (bidang information retrievel), dan lain sebagainya. Algoritma dalam pengertian modern mempunyai kemiripan dengan istilah resep, proses, metode, teknik, prosedur, rutin. Algoritma adalah sekumpulan aturanaturan berhingga yang memberikan sederetan operasi-operasi untuk menyelesaikan suatu jenis masalah yang khusus (Knuth, 1973). Berdasarkan pengertian algoritma di atas, dapat disimpulkan bahwa algoritma merupakan suatu istilah yang luas, yang tidak hanya berkaitan dengan dunia komputer. Kriteria Algoritma (Knuth, 1973) adalah: 1. Input: algoritma dapat memiliki nol atau lebih masukan dari luar. 2. Output: algoritma harus memiliki minimal satu buah hasil keluaran. 3. Definiteness (pasti): algoritma memiliki instruksi-instruksi yang jelas dan tidak ambigu. 4. Finiteness (ada batas): algoritma harus memiliki titik berhenti (stopping role). 5. Effectiveness (tepat dan efisien): algoritma sebisa mungkin harus dapat dilaksanakan dan efektif.

Universita Sumatera Utara

7

2.2.

Kompleksitas Algoritma

Sebuah permasalahan dapat diselesaikan dengan berbagai algoritma. Sebagai contoh masalah pengurutan data, ada banyak algoritma pengurutan data (sortir) yang dapat digunakan untuk masalah pengurutan data tersebut. Sebuah algoritma yang baik tidak saja harus benar, tetapi juga harus efisien. Tingkat keefisienan sebuah algoritma diukur dari waktu eksekusi algoritma (time complexity/komplesitas waktu) dan kebutuhan ruang (space) memori. Algoritma yang efisien adalah algoritma yang meminimalkan kebutuhan waktu ekseskusi program dan kebutuhan ruang memori (Cormen et al, 2001). Kebutuhan waktu dan ruang suatu algoritma bergantung pada ukuran masukan (n), yang menyatakan jumlah data yang diproses. Keefisienan algoritma dapat digunakan untuk menilai algoritma yang paling baik dari sejumlah algoritma penyelesaian masalah yang ada. Dengan menggunakan besaran kompleksitas waktu/ruang algoritma, kita dapat menentukan laju peningkatan waktu/ruang yang diperlukan algoritma dengan meningkatnya ukuran masukan (n). Menghitung kebutuhan waktu algoritma dengan mengukur waktu sesungguhnya (dalam satuan detik) ketika algoritma dieksekusi oleh komputer bukan cara yang tepat, dikarenakan alasan sebagai berikut : 1. Setiap komputer dengan arsitektur berbeda mempunyai bahasa mesin yang berbeda yang berarti waktu setiap operasi antara satu komputer dengan komputer lain tidak sama. 2. Kompiler bahasa pemrograman yang berbeda menghasilkan kode mesin yang berbeda yang berarti waktu setiap operasi antara satu kompiler dengan kompiler lain tidak sama.

2.3.

Kompleksitas Waktu

Kompleksitas waktu, T(n), diukur dari jumlah tahapan komputasi yang dibutuhkan untuk menjalankan algoritma sebagai fungsi dari ukuran masukan n. Jumlah tahapan komputasi dihitung dari berapa kali suatu operasi dilaksanakan di dalam sebuah algoritma sebagai fungsi ukuran masukan (n) (Cormen et al, 2001). Di dalam sebuah algoritma terdapat bermacam jenis operasi:

Universita Sumatera Utara

8

(a) Operasi baca/tulis (b) Operasi aritmetika (+, -, *, /) (c) Operasi pengisian nilai (assignment) (d) Operasi pengakasesan elemen larik (e) Operasi pemanggilan fungsi/prosedur (f) Dan lain-lain. Dalam hal kompleksitas waktu yang dihitung adalah jumlah operasi khas (tipikal) yang mendasari suatu algoritma. Untuk algoritma pengurutan, operasi khas yang dimaksud adalah perbandingan elemen dan pertukaran elemen. Kompleksitas waktu dibedakan atas tiga jenis, yakni : 1. Tmax(n) : kompleksitas waktu untuk kasus terburuk (worst case), kebutuhan waktu maksimum. 2. Tmin(n) : kompleksitas waktu untuk kasus terbaik (best case),kebutuhan waktu minimum. 3. Tavg(n): kompleksitas waktu untuk kasus rata-rata (average case), kebutuhan waktu secara rata-rata.

2.4.

Kompleksitas Waktu Asimptotik

Notasi “O” disebut notasi “O-Besar” (Big-O) adalah merupakan notasi kompleksitas waktu asimptotik. Dalam praktek, nilai T(n) yang eksak tidak terlalu penting, yang lebih penting adalah laju peningkatan T(n) ketika n membesar, pada tabel 2.1 berikut akan menunjukkan contoh perbandingan pertumbuhan untuk T (n)  2n 2  6n  1 , Tabel 2.1. Perbandingan Pertumbuhan T (n) dengan n 2

n

T ( n)  2 n 2  6n  1

n2

10

261

100

100

2.061

10.000

1000

2.006.001

1.000.000

10.000

2.000.060.001

100.000.000

Universita Sumatera Utara

9

Untuk n yang besar, pertumbuhan T(n) sebanding dengan n, T(n) tumbuh seperti n tumbuh. T(n) tumbuh seperti n tumbuh saat n bertambah ditulis T(n) = O(n2). Notasi “O” berguna untuk membandingkan beberapa algoritma dari dan untuk masalah yang sama dalam hal menentukan yang terbaik. Semakin kecil nilai O dari suatu algoritma, maka berarti semakin baik kompleksitas waktu algoritma tersebut (Cormen et al, 2001).

2.5. Kompleksitas Ruang Memori Kompleksitas ruang memori S(n), diekspresikan sebagai jumlah memori yang digunakan oleh struktur data yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n, dan kompleksitas ruang memori S(n) diukur berdasarkan memori yang digunakan oleh struktur data tersebut (Cormen et al, 2001).

2.6. Algotima Pengurutan Dalam ilmu komputer, algoritma pengurutan (sorting) adalah algoritma yang meletakkan elemen-elemen suatu kumpulan data dalam urutan tertentu atau proses pengurutan data yg sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan, yang pada kenyataannya urutan tertentu yang umum digunakan adalah terurut secara numerikal ataupun secara leksikografi (urutan secara abjad sesuai kamus). Ada 2 (dua) jenis pengurutan, yakni secara ascending (naik) dan descending (turun).

2.7. Klasifikasi Algoritma Pengurutan Algoritma pengurutan diklasifikasikan menjadi beberapa jenis, yakni : 1. Exchange Sort Algoritma yang dikategorikan dalam Exchange Sort jika cara kerja algoritma tersebut melakukan pembandingan antar data dan melakukan pertukaran apabila urutan yang didapat belum sesuai. Contohnya : Bubble sort, Cocktail sort, Comb sort, Gnome sort, Quicksort.

Universita Sumatera Utara

10

2. Selection Sort Algoritma yang dikategorikan dalam Selection Sort jika cara kerja algoritma tersebut mencari elemen yang tepat untuk diletakkan pada posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan. Contohnya Selection sort, Heap sort, Smooth sort, Strand sort. 3. Insertion Sort Algoritma yang dikategorikan dalam Insertion Sort jika cara kerja algoritma tersebut mencari tempat yang tepat untuk suatu elemen data yang telah diketahui ke dalam subkumpulan data yang telah terurut, kemudian melakukan penyisipan (insertion) data di tempat yang tepat tersebut. Contohnya adalah Insertion sort, Shell sort, Tree sort, Library sort, Patience sort. 4. Merge Sort Algoritma yang dikategorikan dalam Merge Sort jika cara kerja algoritma tersebut membagi data menjadi subkumpulan-subkumpulan yang kemudian subkumpulan tersebut diurutkan secara terpisah, dan kemudian digabungkan kembali dengan metode merging. algoritma ini melakukan metode pengurutan merge sort juga untuk mengurutkan subkumpulandata tersebut, atau dengan kata lain, pengurutan dilakukan secara rekursif. Contohnya adalah Merge sort. 5. Non Comparison Sort Algoritma yang dikategorikan dalam Non Comparison Sort jika proses pengurutan data yang dilakukan algoritma tersebut tidak terdapat pembandingan antardata, data diurutkan sesuai dengan pigeon hole principle. Contohnya adalah Radix sort, Bucket sort, Counting sort, Pigeonhole sort, Tally sort.

2.8. Algoritma SMS (Scan, Move and Sort) Algoritma SMS diperkenalkan oleh Rami Mansi pada 2 April 2010, yang merupakan peningkatan dari algoritma Quicksort. Karena algoritma SMS merupakan peningkatan dari algoritma Qiucksort, berarti algoritma SMS dikategorikan dalam algoritma Exchange Sort. Dalam kasus terbaik, algoritma SMS membutuhkan kompleksitas waktu O(n). Dalam kasus rata-rata algoritma SMS membutuhkan kompleksitas waktu O(n + f * (nilai maksimum + |nilai minimum|)), di mana f adalah jumlah elemen yang

Universita Sumatera Utara

11

sering muncul. Peningkatan pada kasus rata-rata terjadi ketika n adalah jauh lebih besar dari pada nilai maksimum dan |nilai minimum|, di mana kompleksitas waktu mendekati O(n). Ketika berurusan dengan berbagai elemen yang berbeda, algoritma SMS lebih efisien dari pada algoritma quicksort. Dalam kasus terburuk, algoritma SMS membutuhkan kompleksitas waktu O(n + f * (nilai maksimum + |nilai minimum|)) (Mansi, 2010).

2.9. Konsep Algoritma SMS Konsep utama dari algoritma SMS mendistribusikan elemen dari array masukan pada tiga array tambahan sementara. Ukuran dari array ditentukan dan tergantung pada nilai maksimum dan nilai minimum dari array masukan. Array tambahan pertama disebut PosArray yang menampung elemen-elemen yang bernilai positif dari array masukan dan menggunakan nilai dari elemen itu sendiri sebagai indeks dalam array. Array kedua adalah NegArray yang menampung elemen-elemen yang bernilai negatif dari array masukan dan menggunakan nilai absolut dari elemen itu sendiri sebagai indeks dalam array. Array ketiga adalah FreqArray dan digunakan untuk menyimpan elemen yang muncul lebih dari 1 (satu) kali (sering muncul) dari array masukan (Mansi, 2010).

2.10. Langkah-Langkah Algoritma SMS.

Algoritma SMS terdiri dari tiga prosedur, yakni Scan, Move, dan Sort. Prosedur pertama adalah Scan (kenal), yang mengenali array dan berguna untuk mendapatkan nilai minimum, nilai maksimum, jumlah elemen positif, dan jumlah elemen negatif dari array masukan. Selain itu, prosedur ini memeriksa apakah nilai minimum sama dengan nilai maksimum, jika sama berarti array input sudah adalah array yang sudah terurut, jika tidak sama maka dilanjutkan ke prosedur move. Prosedur kedua adalah prosedur Move (pindah) yang menciptakan tiga array sementara, FreqArray berukuran n, PosArray berukuran nilai maksimal tambah 1 (satu), dan NegArray berukuran absolut dari nilai minimum ditambah 1 (satu), dan kemudian menginisialisasi PosArray, NegArray, dan FreqArray dengan nilai

Universita Sumatera Utara

12

minimum dikurang 1 (satu) untuk yang menunjukkan indeks yang akan dilewati di fase berikutnya. Kemudian, prosedur ini mendistribusikan elemen pada tiga array, elemen positif disimpan dalam PosArray menggunakan elemen itu sendiri sebagai indeks, elemen-elemen negatif disimpan dalam NegArray menggunakan nilai absolut dari elemen itu sendiri sebagai indeks, dan elemen yang sering muncul disimpan dalam FreqArray menggunakan variabel i sebagai indeks dimulai dari nol dan seterusnya bertambah satu. Prosedur ketiga adalah prosedur Sort (pengurutan) yang menyalin elemen-elemen dari NegArray mulai dari indeks terakhir dan mengabaikan elemen NegArray yang berisi nilai minimum kurang 1 (satu). Kemudian menyalin elemen-elemen dari PosArray mulai dari indeks pertama dan juga mengabaikan elemen PosArray yang berisi nilai nilai minimum dikurang 1 (satu). Penyalinan dilakukan pada array input asli dengan menimpa nilai-nilai asli dengan nilai-nilai yang telah diurutkan. Setelah menyalin setiap elemen dari NegArray dan PosArray ke array yang asli, kemudian dilanjutkan prosedur pencarian FreqArray dan menyalin semua elemen yang sama dengan elemen yang disalin dalam operasi penyalinan terakhir (elemen saat ini) (Mansi, 2010).

2.11. Pseudocode Algoritma SMS Prosedur Scan(array, size) if size > 1 then

(1)

var a, max, min, NOP, NON

(2)

max:=array(0)

(3)

min:=array(0)

(4)

NOP:=0

(5)

NON:=0

(6)

for a:= 0 to size-1 do

(7)

if array(a) > max then max := array(a) else

(8) (9) (10)

min:=array(a) end if

(11) (12)

Universita Sumatera Utara

13

if array(a) >= 0 then

(13)

NOP:= NOP+1

(14)

else

(15) NON:= NON+1

(16)

end if

(17)

end for

(18)

if min ≠ max then

(19)

Move(array, size, NOP, NON, max, min)

(20)

end if

(21)

end if

(22)

Akhir prosedur Scan Prosedur Move(array, size, NOP, NON, max, min) var b,c,d,i

(1)

i:=0

(2)

create a new array: FreqArray[size] and initialize by the value (min-1)

(3)

if NOP > 0 then

(4)

create a new array:PosArray[max+1]

(5)

for b:=0 to max do

(6)

PosArray(b):= min-1 end for

(7) (8)

end if

(9)

if NON>0 then

(10)

create a new array: NegArray[|min|+1]

(11)

for c:= 0 to |min|+1 do

(12)

NegArray(c):= min-1 end for

(13) (14)

end if

(15)

for d:= 0 to size-1 do

(16)

if array(d) >= 0 then

(17)

if PosArray(array(d))==min-1 then

(18)

PosArray(array(d)):=array(d)

(19)

else

(20)

Universita Sumatera Utara

14

FreqArray(i):=array(d)

(21)

i:=i+1

(22)

end if

(23)

else

(24)

if NegArray(|array(d)|)==min-1 then

(25)

NegArray(|array(d)|):= array(d)

(26)

else

(27) FreqArray(i):= array(d)

(28)

i:= i+1

(29)

end if

(30)

end if

(31)

end for

(32)

Sort(array, NegArray, PosArray, FreqArray,

NON, NOP, max, min, i)

(33)

Akhir prosedur Move Prosedur Sort(array, NegArray, PosArray, FreqArray, NON, NOP, max, min, i) var index,x,y

(1)

index:=0

(2)

if NON > 0 then

(3)

for x:= |min| downto 0 do if NegArray(x) ≠ min-1 then

(4) (5)

array(index):= NegArray(x)

(6)

index:= index+1

(7)

for y:= 0 to i do

(8)

if FreqArray(y)==array(index-1) then array(index):= FreqArray(y)

(10)

index:= index+1

(11)

end if end for end if end for

(9)

(12) (13) (14) (15)

end if

(16)

if NOP > 0 then

(17)

Universita Sumatera Utara

15

for x:= 0 to max do if PosArray(x) ≠ min-1 then

(18) (19)

array(index):= PosArray(x)

(20)

index:= index+1

(21)

for y:= 0 to i do

(22)

if FreqArray(y)== array(index-1) then

(23)

array(index):=FreqArray(y)

(24)

index:= index+1

(25)

end if end for end if end for end if

(26) (27) (28) (29) (30)

Akhir prosedur Sort

2.12. Kompleksitas Waktu Algortima SMS Algoritma SMS terdiri dari tiga prosedur, yakni Scan, Move, dan Sort, berikut akan terlihat kompleksitas waktu dari ketiga prosedur tersebut yang akan menghasilkan kompleksitas waktu keseluruhan dari algoritma SMS

2.12.1. Kompleksitas waktu prosedur scan Tujuan dari prosedur scan adalah untuk mendapatkan nilai maksimum, nilai minimum, jumlah elemen positif, dan jumlah elemen negatif dari array masukan. Hal ini memerlukan pengenalan array dimana setiap elemen harus dikunjungi 1 (satu) kali. Untuk perulangan (baris 7-18 prosedur scan) memerlukan kompleksitas waktu O(n) (Mansi, 2010).

Universita Sumatera Utara

16

2.12.2. Kompleksitas waktu prosedur move Kasus terbaik prosedur move adalah ketika semua elemen dari array masukan adalah bilangan positif dan nilai maksimumnya kecil, atau ketika semua elemen dari array masukan adalah bilangan negatif dan nilai minimumnya kecil. Jika semua elemen array adalah bilangan positif dan tidak ada yang negatif, maka untuk perulangan (baris 6-8 dari prosedur move) membutuhkan kompleksitas waktu O(max) untuk menginisialisasi PosArray, dan untuk perulangan (baris 16-32 dari prosedur move) membutuhkan kompleksitas waktu O(n). Berdasarkan penjelasan diatas, jika seluruh elemen array masukan merupakan bilangan positif, kompleksitas waktu keseluruhan prosedur move adalah O(n + max). Di sisi lain, jika semua elemen dari array masukan adalah bilangan negatif, maka untuk perulangan (baris 12 -14 prosedur move) membutuhkan kompleksitas waktu O(|min|) menginisialisasi NegArray, dan untuk perulangan (baris 16 -32 prosedur move) membutuhkan kompleksitas waktu O(n). Dalam hal ini berarti, kompleksitas waktu keseluruhan prosedur move jika seluruh elemen array masukan merupakan bilangan negatif adalah O(n + |min|). Dapat dikatakan bahwa dalam kasus rata-rata dan terburuk, jika terdapat elemen positif dan negatif dalam array masukan, maka kompleksitas waktu keseluruhan prosedur move adalah O(n + max + |min|)) (Mansi, 2010).

2.12.3. Kompleksitas waktu prosedur sort

Kasus terbaik prosedur sort adalah ketika semua elemen array masukan merupakan bilangan positif dan semua elemen berbeda serta bilangan maksimum bernilai kecil, atau ketika semua elemen array masukan adalah bilangan negatif dan semua elemen berbeda serta bilangan minimum bernilai kecil. Jika semua elemen array masukan adalah bilangan positif dan berbeda, maka perulangan (baris 18-29 dari prosedur sort) membutuhkan kompleksitas waktu O(max), karena perulangan (baris 22-27 dari prosedur sort) membutuhkan kompleksitas waktu O(1) dalam kasus ini. Jika semua elemen array masukan adalah bilangan negatif dan setiap elemen berbeda, maka untuk perulangan (baris 4-15 dari prosedur sort) membutuhkan kompleksitas waktu O(|min|), karena perulangan (baris 8-13 dari prosedur sort) membutuhkan

Universita Sumatera Utara

17

kompleksitas waktu O(1) dalam kasus ini. Dapat dikatakan, pada kasus rata-rata, dan terburuk prosedur sort, prosedur Sort membutuhkan kompleksitas waktu O(max * f) + O(|min| * f), di mana f adalah jumlah elemen yang sama. Dengan kata lain, kompleksitas waktu prosedur sort adalah O(f * (max + |min|)). Kompleksitas waktu kasus terbaik dari algoritma SMS adalah O(n), ketika array masukan sudah terurut. Ini berarti, ketika nilai max sama dengan min (baris 19-21 prosedur scan) maka array input sudah diurutkan. Dalam kasus rata-rata dan terburuk, prosedur scan memerlukan kompleksitas waktu O(n), prosedur move membutuhkan kompleksitas waktu O(n + max + |min|), dan prosedur sort memerlukan kompleksitas waktu O(f * (max + |min|)). Jika dianggap distribusi data adalah normal, frekuensi elemen harus sedikit, dan karena sebagian besar aplikasi nyata memiliki n jauh lebih besar dari nilai max dan |min|, dapat dipertimbangkan max dan min sebagai konstanta dan menghilangkannya. Kompleksitas waktu keseluruhan dari algoritma SMS dalam kasus rata-rata dan terburuk adalah O(n + f * (max + | min |)), di mana f adalah jumlah elemen yang sama (Mansi, 2010).

2.13. Kompleksitas Ruang Memori Algortima SMS Pada kasus terbaik, jika array masukan berisikan data yang sudah terurut, algoritma SMS berhenti/selesai pada prosedur Scan dan algoritma SMS tidak memerlukan ruang memori tambahan untuk mengurutkan array masukan. Jika semua elemen dari array masukan adalah positif, algoritma SMS hanya membuat 2 array baru, yakni PosArray berukuran (max + 1) dan FreqArray berukuran (n), atau jika semua elemen dari array masukan adalah negatif, algoritma SMS juga hanya membuat 2 array baru, yakni NegArray berukuran (|min| + 1) dan FreqArray berukuran (n). Dapat dikatakan dalam kasus rata-rata dan terburuk, algoritma SMS membutuhkan ruang memori tambahan sebesar O(n + max + | min | +2) (Masni, 2010).

Universita Sumatera Utara