Sorting Algorithm

Posted: July 28, 2008 in Algorithm, Programming
Tags: ,

Lets talk about something hard….its about algorithm…yep of source..its a logic
wkwkwkw…
udahan bahasa inggrisnya
langsung aja ke pembahasan:

==========Bubble Sort==========
Bubble Sort sering disebut juga metode penukaran. Tekniknya adalah dengan melakukan perbandingan data yang satu dengan data setelahnya dan melakukan pertukaran jika kedua data tersebut salah satunya lebih besar atau lebih kecil.
Example :
Terdapat data seperti di bawah ini

8 3 9 5
Yang pertama diasumsikan diurutkan dari kecil ke besar (ascending). Maka 8 dibandingkan dengan 3, karena 8 > 3 maka

3 8 9 5
8 dibandingkan dengan 9, karena 9 > 8, maka pertukaran tidak dilakukan

3 8 9 5
5 dibandingkan dengan 9, karena 9 > 5 maka

3 8 5 9
Dan dibandingkan 5 dengan 8, karena 8 > 5 maka

3 5 8 9
(data telah terurut)

==========Selection Sort==========
Konsep dari metode ini adalah mencari (memilih) nilai terkecil dan menukarnya dengan eleman paling awal pada setiap tahap.
Example :
Terdapat data seperti ini

7 9 2 8 6
Langkah awal, ditemukan nilai terkecil adalah 2

2 9 7 8 6
Nilai terkecil adalah 6 maka

2 6 7 8 9
(data telah terurut)

==========Insertion Sort==========
Pengurutan dilakukan dengan cara membandingkan data ke- i (dimana i dimulai dari data kedua sampai dengan data yang terakhir) dengan data sebelumnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuia dengan posisi seharusnya. Setiap langkah insertion sort seolah – olah mengambil sebuah elemen dari tempat tertentu, kemudian menyisipkannya ke suatu tempat sehingga elemen – elemen lainya bergeser ke belakang
Example:

9 4 6 2 7 5
dimulai data ke dua, yaitu 4 kemudian dibandingkan ke kiri

4 9 6 2 7 5
selanjutnya ada di data ketiga yaitu 6 kemudian dibandingkan lagi

4 6 9 2 7 5
selanjutnya ada di data keempat yaitu 2 kemudian dibandingkan lagi

2 4 6 9 7 5
selanjutnya ada di data kelima yaitu 7 kemudian dibandingkan lagi

2 4 6 7 9 5
selanjutnya ada di data keenam yaitu 5 kemudian dibandingkan

2 4 5 6 7 9
(data sudah terurut)

==========Quick Sort==========
Metode Quick Sort sering disebut juga dengan metode partition exchange sort. Metode ini diperkenalkan oleh C.A.R. Hoare. Metodenya adalah yang pertama memilih salah satu elemen dari data yang ingin diurutkan sebagai pivot (acuan). Pivot tersebut akan dibandingkan dengan data yang lain. Proses membandingkan mulai dari data paling kanan ke kiri. Pembanding akan terus dilakukan sampai ada data yang lebih kecil dari data pivot. Jika ditemukan data yang lebih kecil, maka tukar posisi elemen pivot dengan data tersebut. Langkah selanjutnya adalah membandingkan elemen paling kiri setelah data yang telah ditukar tadi. Jika menemukan data yang lebih besar maka tukar posisi dengan elemen pivot. Begitu seterusnya sampai elemen – elemen data di sebela kiri data pivot lebih kecil dari pivot dan elemen – elemen data di sebelah kanan pivot lebih besar.
Example :
Terdapat data seperti di bawah ini

7 5 9 4 8
7 sebagai pivot. Dibandingkan dan ditemukan data yang terkecil adalah 4 maka

4 5 9 7 8
Langkah berikut membandingkan pivot dengan kirinya (9). Karena ditemukan lebih besar maka tukar posisi dengan pivot

4 5 7 9 8
Selanjutnya 4 sebagai pivot.

4 5 7 9 8
Karena 4 sudah yang terkecil, maka langkah selanjutnya 5 sebagai pivot.

4 5 7 9 8
Karena 5 sudah terurut maka pivot selanjutnya 7

4 5 7 9 8
Karena 7 juga sudah terurut maka pivot selanjutnya 9

4 5 7 9 8
Ditemukan di sebelah kanan pivot angka terkecil maka ditukar

4 5 7 8 9
(data sudah terurut)

==========Merge Sort==========
Algoritma dari merge sort adalah dengan cara memecah data menjadi beberapa bagian, kemudian dari tiap bagian dilakukan pengurutan. Kemudian tiap bagian yang sudah terurut digabung dengan bagian lain da dilakukan pengurutan lagi
Example :

7 5 9 4 8

Maka data akan dipecah kemudian diurutkan

7 5 — 9 — 4 8

5 7 — 9 — 4 8

Digabung, kemudian diurutkan

7 5 9 — 4 8

4 5 7 8 9
(data sudah terurut)

oke..itu aja doeloe..sebenarnya masi banyak lagi algoritma sorting lainnya seperti shell sort, heap sort dan lain-lain…selanjutnya saya serahkan kepada anda…..he he he

O iya, kebetulan saya juga punya applet animasi tentang sorting:
Download Animasi 1
Download Animasi 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s