Pengertian Sorting (Selection Sort dan Insertion Sort) dengan Contoh Program C++

Pengertian Selection Sort
Selection Sort merupakan salah satu algoritma pengurutan yang sederhana. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data. Untuk sorting ascending (menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar yang disimpan indeksnya kemudian ditukar.

Selection Sort diakui karena kesederhanaan algoritmanya dan performanya lebih bagus daripada algoritma lain yang lebih rumit dalam situasi tertentu. Algoritma ini bekerja sebagai berikut:

1. Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list
2. Menukarkan nilai ini dengan elemen pertama list
3. Mengulangi langkah di atas untuk sisa list dengan dimulai pada posisi kedua
4. Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan. 

Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan.

Berikut adalah simulasi Algoritma Selection Sort
Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut

Algoritma pengurutan selection sort ini termasuk algoritma sulit dibagi/ mudah digabung (hard split/easy join).  Dari proses pengurutannya, Selection sort ini memiliki dua buah varian yaitu :

1. Maximum Sort
Memilih data yang maksimum dari suatu kumpulan data larik, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data maksimum berikutnya.

2. Minimum Sort
Memilih data yang minimum dari suatu kumpulan data larik , lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data minimum berikutnya.
Dalam pemecahan masalah algoritma selection sort , kita dapat memilih dua metode alternatif algoritma antara lain pemecahan dengan metode Brute Force dan pemecahan dengan metode devide and conquer.

Metode Pemecahan Brute Force
Kekuatan algoritma brute force terletak pada kemampuannya untuk menemukan semua pemecahan masalah yang mungkin, akan tetapi langkah yang dibutuhkan sangat banyak sehingga tidak baik jika digunakan untuk memecahkan masalah yang memiliki masukan yang cukup besar.

Contoh Program Selection Sort
*source code dibawah di build/compile menggunakan Micrososft Visual C++ 2013

Hasilnya

Pengertian Insertion Sort
[post_ad]Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada. Inde algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu, dimana jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut. Dalam pengurutan data, metode ini dipakai bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array diurutkan.

Penganalogian Insertion Sort dengan pengurutan kartu
Berikut menjelaskan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu, Anggaplah kita ingi mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.

1. Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. dan anggaplah kita akan menyusun kartu ke tangan kiri kita.
2. Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.
3. Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.
4. Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang).

Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya, demikian juga halnya dalam pengurutan data. Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakan di depan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.

[post_ad]Catatan : Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data-data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.

 
Berikut adalah simulasi Algoritma Insertion Sort
Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.

Dari gambaran proses pengurutan/sorting data di atas dapat diketahui bagaimana data-data tersebut berpindah posisi dari satu index ke index lain dalam satu array.

Contoh Program Insertion Sort
*source code dibawah di build/compile menggunakan Micrososft Visual C++ 2013

Hasilnya

Cukup segitu penjelasan mengenai Selection Sort dan Insertion Sort, semoga anda memahami isi artikel diatas, jika ada yang belum dipahami anda bisa bertanya melalui form komentar dibawah, segera mungkin akan saya jawab. Jangan lupa juga membanca penjelasan materi tentang pemprograman C++ lainnya :

1. Pengenalan Mengenai Variabel
2. Array Satu Dimensi, dan Dua Dimensi
3. Stack
4. Queue
5. Searching (Sequential Search dan Binarry Search)

Sumber :

Buku Pemprograman C# Abdul Kadir

Power Point :  Struktur Data oleh Taufik Fuadi Abidin (scribd)