Insertion Sort ~ Dodi Pratama

METODE SORTING

Seringkali perancang program perlu mengurutkan sekumpulan data yang dimiliki untuk memudahkan pemrosesan selanjutnya terhadap data tersebut. Pengurutan adalah sebuah algoritma dasar yang sering diperlukan dalam pembuatan program. Berbagai algoritma pengurutan telah diciptakan dan dapat digunakan. Pemahaman tentang beberapa algoritma pengurutan dasar perlu diketahui, termasuk cara penggunaannya dalam program.

PENGERTIAN SORT

Sorting atau pengurutan data adalah proses yang sering harus dilakukan dalam pengolahan data. Sortdalam hal ini diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urut menaik (ascending) dari nilai terkecil sampai dengan nilai terbesar, atau urut menurun (descending) dari nilai terbesar sampai dengan nilai terkecil. Sorting adalah proses pengurutan.

Terdapat dua macam pengurutan:

Ø Pengurutan internal (internal sort), yaitu pengurutan terhadap sekumpulan data yang disimpan dalam media internal komputer yang dapat diakses setiap elemennya secara langsung. Dapat dikatakan sebagai pengurutan tabel

Ø Pengurutan eksternal (external sort), yaitu pengurutan data yang disimpan dalam memori sekunder, biasanya data bervolume besar sehingga tidak mampu untuk dimuat semuanya dalam memori.

INSERTION SORT

Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan.

CARA KERJA INSERTION SORT

Insertion Sort bekerja seperti orang yang sedang mengurutkan kartu di tangan. Dimulai dengan tangan kiri yang kosong dan kartunya tertumpuk di meja. Selanjutnya kita ambil satu persatu kartu di meja dan diletakkan di tangan kiri dengan posisi yang benar (terurut). Untuk menemukan posisi yang banar, maka kita harus membandingkan satu persatu kartu yang ada (di tangan kiri) secara berurutan.

CONTOH INSERTION SORT

Bagian abu-abu (dua bilangan pertama) sekarang dalam keadaan terurut.

Berikutnya, kita perlu menyisipkan bilangan ketiga (4) ke dalam bagian abu-abu sehingga setelah penyisipan tersebut, bagian abu-abu tetap dalam keadaan terurut ;

CARANYA :

pertama : Ambil bilangan ketiga (4).

Kedua : Geser bilangan kedua (10) sehingga ada ruang untuk disisipi.

Ketiga : Sisipkan bilangan 4 ke posisi yang tepat.

Sekarang, tiga bilangan pertama sudah terurut dan kita sisipkan bilangan keempat kepada tiga bilangan pertama tersebut. Setelah penyisipan, empat bilangan pertama haruslah dalam keadaan terurut.