BUBBLE SORT

A.      Pengertian Bubble SortBubble Sort adalah salah satu algoritma untuk sorting data, atau kata lainnya mengurutkan data dari yang terbesar ke yang terkecil atau sebaliknya (Ascending atau Descending).Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.                Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.Algoritma bubble sort adalah salah satu algoritma pengurutan yang paling simple, baik dalam hal pengertian maupun penerapannya. Ide dari algoritma ini adalah mengulang proses pembandingan antara tiap-tiap elemenarray dan menukarnya apabila urutannya salah. Pembandingan elemen-elemen ini akan terus diulang hingga tidak perlu dilakukan penukaran lagi. Algoritmaini termasuk dalam golongan algoritma comparison sort, karena menggunakan perbandingan dalam operasi antar elemennya. Berikut ini adalah gambaran dari algoritma bubble sort. Misalkan kita mempunyai sebuah array dengan.  Elemen-elemen “4 2 5 3 9”. Proses yang akan terjadi apabila digunakan algoritma bubblesort adalah sebagai berikut.

Pass pertama(4 2 5 3 9) menjadi (2 4 5 3 9)(2 4 5 3 9) menjadi (2 4 5 3 9)(2 4 5 3 9) menjadi (2 4 3 5 9)(2 4 3 5 9) menjadi (2 4 3 5 9)Pass kedua(2 4 3 5 9) menjadi (2 4 3 5 9)(2 4 3 5 9) menjadi (2 3 4 5 9)(2 3 4 5 9) menjadi (2 3 4 5 9)(2 3 4 5 9) menjadi (2 3 4 5 9)Pass ketiga(2 3 4 5 9) menjadi (2 3 4 5 9)(2 3 4 5 9) menjadi (2 3 4 5 9)(2 3 4 5 9) menjadi (2 3 4 5 9)(2 3 4 5 9) menjadi (2 3 4 5 9)

Dapat dilihat pada proses di atas, sebenarnya pada pass kedua, langkah kedua, array telah terurut. Namun algoritma tetap dilanjutkan hingga pass kedua berakhir. Pass ketiga dilakukan karena definisi terurut dalam algoritma bubblesort adalah tidak ada satupun penukaran pada suatu pass, sehingga pass ketiga dibutuhkan untuk memverifikasi keurutan array tersebut.

B.      Algoritma Bubble Sort

1.    Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).2.    Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.3.    Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dst.

4.    Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.

Contoh Kasus Bubble Sort :

Misalkan kita punya data seperti ini: 6, 4, 3, 2 dan kita ingin mengurutkan data ini (ascending) dengan menggunakan bubble sort. Berikut ini adalah proses yang terjadi:

Iterasi ke-1: 4, 6, 3, 2 :: 4, 3, 6, 2 :: 4, 3, 2, 6 (ada 3 pertukaran)Iterasi ke-2: 3, 4, 2, 6 :: 3, 2, 4, 6 :: 3, 2, 4, 6 (ada 2 pertukaran)Iterasi ke-3: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 1 pertukaran)Iterasi ke-4: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 0 pertukaran) -> proses selesai

C.      Kompleksitas Algoritma Bubble Sort

Kompleksitas Algoritma Bubble Sort dapat dilihat dari beberapa jenis kasus, yaitu worst-case, average-case, dan best-case.

Ø  Kondisi Best-Case

Dalam kasus ini, data yang akan disorting telah terurut sebelumnya, sehingga proses perbandingan hanya dilakukan sebanyak (n-1) kali, dengan satu kali pass.Proses perbandingan dilakukan hanya untuk memverifikasi keurutan data. Contoh Best-Case dapatdilihat pada pengurutan data “1 2 3 4” di bawah ini.

Pass Pertama(1 2 3 4) menjadi (1 2 3 4)(1 2 3 4) menjadi (1 2 3 4)(1 2 3 4) menjadi (1 2 3 4)

Dari proses di atas, dapat dilihat bahwa tidak terjadi penukaran posisi satu kalipun, sehingga tidak dilakukan pass selanjutnya. Perbandingan elemen dilakukan sebanyak tiga kali. Proses perbandingan pada kondisi ini hanya dilakukan sebanyak (n-1) kali. Persamaan Big-O yang diperoleh dari proses ini adalah O(n). Dengan kata lain, pada kondisi Best-Case algoritma Bubble Sort termasuk pada algoritmalanjar.

Ø  Kondisi Worst-Case

Dalam kasus ini, data terkecil berada pada ujung array. Contoh Worst-Case dapat dilihat pada pengurutan data “4 3 2 1” di bawah ini.

Pass Pertama(4 3 2 1) menjadi (3 4 2 1)(3 4 2 1) menjadi (3 2 4 1)(3 2 4 1) menjadi (3 2 1 4)Pass Kedua(3 2 1 4) menjadi (2 3 1 4)(2 3 1 4) menjadi (2 1 3 4)(2 1 3 4) menjadi (2 1 3 4)Pass Ketiga(2 1 3 4) menjadi (1 2 3 4)(1 2 3 4) menjadi (1 2 3 4)(1 2 3 4) menjadi (1 2 3 4)Pass Keempat(1 2 3 4) menjadi (1 2 3 4)(1 2 3 4) menjadi (1 2 3 4)(1 2 3 4) menjadi (1 2 3 4)

Dari langkah pengurutan di atas, terlihat bahwa setiap kali melakukan satu pass, data terkecil akan bergeser ke arah awal

sebanyak satu step. Dengan kata lain, untuk menggeser data terkecil dari urutan keempat menuju urutan pertama, dibutuhkan pass sebanyak tiga kali, ditambah satu kali pass untuk memverifikasi. Sehingga jumlah proses pada kondisi best case dapat dirumuskan sebagai berikut. Jumlah proses = n2+n (3)Dalam persamaan (3) di atas, n adalah jumlah elemen yang akan diurutkan. Sehingga notasi Big-O yang didapat adalah O(n2). Dengan kata lain, pada kondisi worst-case, algoritma Bubble Sort termasuk dalam kategori algoritma kuadratik.

Ø  Kondisi Average-Case

Pada kondisi average-case, jumlah pass ditentukan dari elemen mana yang mengalami penggeseran ke kiri paling banyak. Hal ini dapat ditunjukkan oleh proses pengurutan suatu array, misalkan saja (1 8 6 2). Dari (1 8 6 2), dapat dilihat bahwa yang akan mengalami proses penggeseranpaling banyak adalah elemen 2, yaitu sebanyak dua kali.

Pass Pertama(1 8 6 2) menjadi (1 8 6 2)(1 8 6 2) menjadi (1 6 8 2)(1 6 8 2) menjadi (1 6 2 8)Pass Kedua(1 6 2 8) menjadi (1 6 2 8)(1 6 2 8) menjadi (1 2 6 8)(1 2 6 8) menjadi (1 2 6 8)Pass Ketiga(1 2 6 8) menjadi (1 2 6 8)(1 2 6 8) menjadi (1 2 6 8)(1 2 6 8) menjadi (1 2 6 8)

Dari proses pengurutan di atas, dapat dilihat bahwa untuk mengurutkan diperlukan dua buah passing,ditambah satu buah passing untuk memverifikasi. Dengan kata lain, jumlah proses perbandingan dapat dihitung sebagai berikut. Jumlah proses = x2+x (4) Dalam persamaan (4) di atas, x adalah jumlahpenggeseran terbanyak. Dalam hal ini, x tidak pernah lebih besar dari n, sehingga x dapat dirumuskan sebagaiDari persamaan (4) dan (5) di atas, dapat disimpulkan bahwa notasibig-O nya adalah O(n2). Dengan kata lain, pada kondisi average case algoritma Bubble Sort termasuk dalam algoritma kuadratik.

D.      Implementasi dalam Pseudo-Code

Setiap algoritma akan memiliki implementasi yang berbeda, tergantung dari bahasa program yang dipakai. Oleh karena itu berikut ini adalah pseudo-code dari algoritma bubblesort, untuk memudahkan implementasi bubblesort pada bahasa apapun.

procedure bubbleSort( A : list ofsortable items ) defined as:doswapped := falsefor each i in 0 to length(A) - 2inclusive do:if A[i] > A[i+1] thenswap( A[i], A[i+1] )swapped := trueend ifend forwhile swappedend procedure

E.       Kelebihan dan Kelemahan Bubble Sort

Kelebihan :·      Metode Buble Sort merupakan metode yang paling simpel·      Metode Buble Sort mudah dipahami algoritmanya

Kelemahan:Meskipun simpel metode Bubble sort  merupakan metode pengurutan yang paling tidak efisien.  Kelemahan buble sort adalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika  data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya

SORTINGPengertian SortingPengurutan (Sorting) merupakan proses pengurutan sekumpulan data dalam suatu    urutan tertentu.Sortingdipakai untuk:1.Membantu proses pencarian (searching)2.Menyelesaikan masalah-masalah kompleks seperti penjadwalan (scheduling), pengolahan basis data, riset operasi, dsb.

Jenis-Jenis Pengurutan

         1.BUBBLE SORT·         Pengertian Bubble Sort

Bubble Sort (metode gelembung) adalah metode pengurutan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

·         Kelebihan dan Kekurangan Bubble Sort-          Kelebihan :

1. Metode Bubble  Sort merupakan yang paling simple2. Metode Bubble Sort muda di pahami algoritmanya

-          Kelemahan :Meskipun simpel metode Bubble Sort  merupakan metode

pengurutan yang paling tidak efisien.  Kelemahan BubbleSort adalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika  data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.

·      Algoritma dari Bubble Sort•      Membandingkan data ke-i dengan data ke-(i+1) (tepat

bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).

•      Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn   3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.

•      Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dan seterusnya.

•      Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi

                                          2.            SELECTION SORT·         Pengertian Selection Sort

Selection sort merupakan perbaikan dari metode bubble sort dengan mengurangi jumlah perbandingan. Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dan nilai data terbesar dimulai dari data diposisi 0 hingga diposisi N-1.

·         Metode Selection SortJika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan metode selection sort adalah sebagai berikut :

                         1          Cari data terkecil dalam interval j = 0 sampai dengan j = N-1                         2          Jika pada posisi pos ditemukan data yang terkecil, tukarkan

data diposisi pos dengan data di posisi i jika k.                         3          Ulangi langkah 1 dan 2 dengan j = j + i sampai dengan j = N-

1, dan seterusnya sampai j = N - 1.                         4          Bila diketahui data awal berupa: 44 55 12 42 94 18 6 67,

maka langkah per langkah pengurutan dengan metode selection sort adalah sebagai berikut:44 55 12 42 94 18 06 67 Data Awal

06 55 12 42 94 18 44 67 Tukarkan data ke 1 dengan data ke 7

06 12 55 42 94 18 44 67 Tukarkan data ke 2 dengan data ke 3

06 12 18 42 94 55 44 67 Tukarkan data ke 3 dengan data ke 6

06 12 18 42 94 55 44 67 Data ke 4 tidak ditukarkan

06 12 18 42 44 55 94 67 Data ke 5 ditukarkan dengan data ke 7

06 12 18 42 44 55 94 67 Data ke 6 tidak ditukarkan

06 12 18 42 44 55 67 94 Data ke 7 ditukarkan dengan data ke 8

06  12 18 42 44 55 67 94 Data setelah terurut

Tabel 2. Langkah demi langkah pengurutan dengan metode selection sort.

·         Kelebihan dan Kekurangan Selection Sort-          Kelebihan

                                1            Algoritma ini sangat rapat dan mudah untuk diimplementasikan.

                                2            Operasi pertukarannya hanya dilakukan sekali saja.                                3            Waktu pengurutan dapat lebih ditekan.                                4            Mudah menggabungkannya kembali.                                5            Kompleksitas selection sort relatif lebih kecil.

-          Kekurangan                                1            Sulit untuk membagi masalah.

                                    3.            INSERTION SORT·         Pengertian Insertion Sort

Insertion sort adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat.

·         Macam- macam metode insertion sort                                  1            Langsung (straight insertion sort)

Ilustrasi dari langkah-langkah pengurutan dengan algoritma penyisipan langsung (straight insertion sort) tabel berikut :

         2            Metode penyisipan biner (binary insertion sort)Metode pengurutan dengan algoritma penyisipan biner

(binary insertion sort) memperbaiki metode pengurutan dengan algoritma penyisipan langsung dengan melakukan proses perbandingan yang lebih sedikit sehingga proses pengurutan lebih cepat.

Metode penyisipan biner melakukan proses perbandingan dengan membagi dua bagian data dari posisi 0 sampai dengan i-1 yang disebut dengan bagian kiri dan kanan. Apabila data pada posisi ke i berada pada jangkauan kiri maka proses perbandingan dilakukan hanya pada bagian kiri dan menggeser posisi sampai i.

·         Kelebihan dan kekurangan insertion sort-          Kelebihan Sederhana dalam penerapannya. Mangkus dalam data yang kecil. Jika list sudah terurut atau sebagian terurut maka Insertion

Sort akan lebih cepat dibandingkan dengan Quicksort. Mangkus dalam data yang sebagian sudah terurut. Lebih mangkus dibanding Bubble Sort dan Selection Sort. Loop dalam pada Inserion Sort sangat cepat, sehingga

membuatnya salah satu algoritma pengurutan tercepat pada jumlah elemen yang sedikit.

Stabil.

-          Kekurangana.       Banyaknya operasi yang diperlukan dalam mencari posisi

yang tepat untuk elemen larik.b.      Untuk larik yang jumlahnya besar ini tidak praktis.c.       Jika list terurut terbalik sehingga setiap eksekusi dari

perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.

d.      Membutuhkan waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan elemen dalam

jumlah besar.

2.ExchangeaSort

Pembahasan yang kedua mengenai Metode Exchange Sort. Metode ini merupakan metode pengurutan data yang hampir mirip dengan Bubble Sort ( Mirorr-Nya buble sort), bahkan mungkin juga metode Bubble Sort sama dengan Exchange Sort. Namun setiap metode pasti memiliki perbedaan, perbedaan antara Exchange Sort dan Bubble Sort terletak dalam hal bagaimana membandingkan antaraelemen-elemennya.Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot). Sedangkan Bubble sort akan membandingkan

Iterasi

Data[0]

Data[1]

Data[2]

Data[3]

Data[4]

Data[5]

Data[6]

Data[7]

Data[8]

Data[9]

Awal

12 35 9 11 3 17 23 15 31 20

i=1 12 35 9 11 3 17 23 15 31 20i=2 12 35 9 11 3 17 23 15 31 20i=3 9 12 35 11 3 17 23 15 31 20i=4 9 11 12 35 3 17 23 15 31 20i=5 3 9 11 12 35 17 23 15 31 20i=6 3 9 11 12 17 35 23 15 31 20i=7 3 9 11 12 17 23 35 15 31 20   i=8 3 9 11 12 15 17 23 35 31 20

   i=9 3 9 11 12 15 17 23 31 35 20

 Akhir

3 9 11 12 15 17 20 23 31 35

elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi,dan begitu seterusnya.

Quick sort disebut juga dengan partition exchange sortKelebihan dan Kelemahan Algoritma Quick Sort

Beberapa hal yang membuat quick sort unggul: Secara umum memiliki kompleksitas O(n log n).

Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.

Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti merge sort dan heap sort.

Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.

Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).

Namun terdapat pula kelemahan quick sort:

Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).

Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n2).

Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).

Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program

METODE SEARCHING

Searching merupakan kegiatan untuk menemukan atau mencari suatu data yang ditentukan disuatu tempat, apakah sudah sesuai atau belum.Sedangakan Searching sendiri ada beberapa metode yaitu :

1. Sequential Search: metode pencarian yang dimulai dari data

elemen pertama.teknik pencarian data dimana data dicari secara

urut dari depan ke belakang atau dari awal sampai akhir.

Kelebihan dari proses pencarian secara sequential ini jika data

yang dicari terletak didepan, maka data akan ditemukan dengan

cepat. Tetapi dibalik kelebihannya ini, teknik ini juga memiliki

kekurangan1. Jika data yang dicari terletak dibelakang atau paling akhir, maka akan membutuhkan waktu yang lama dalam proses pencariannya.2. Beban komputer akan semakin bertambah jika jumlah data dalam array sangat banyak.

2.. Binary Seacrh (Pencarian Biner)

Metode ini digunakan jika sejumlah data telah diurutkan. Jika

dibandingkan

dengan metode awal tadi metode ini jauh lebih cepat. Secara garis

besar metode ini bisa dijelaskan sebagai berikut. Urutkan

dahulusejumlah data. Lalu bagi dua data-data tadi dengan jumlah

data yang sama pada masing-masingnya.

Kemudian datadibandingkan dengan data terakhir dari

subdata yang pertama. Jika data yang

dicari lebih keci, pencarian dilanjutkan pada sub data pertama

dengan terlebih dahulumembagi dua lagi data-data tersebut dengan

jumlah yang sama. Tetapi jika  data yang dicari lebih besar dari

data terakhir sub data pertama, berarti data yang  dicari

kemungkinan terletak pada subdata yang kedua Proses diatas

dilakukan  berulang sampai data ditemukan atau tidak ditemukan