Penjelasan lengkap selection sort
Algoritma berasal dari pemikiran atau kejadian yang akan dilakukan manusia jika menemukan permasalahan. Misalnya anda dihadapkan sepuluh bola yang memiliki angka yang berbeda. Anda diminta untuk mengurutkan bola dari angka yang terkecil sampai terbesar. Bagaimana anda melakukannya?
Untuk mengurutkan bola tersebut anda melakukan hal sebagai berikut:
Untuk mengurutkan bola tersebut anda melakukan hal sebagai berikut:
- Mencari bola yang memiliki nomor paling kecil,
- Menukar letak bola pertama dengan bola yang memiliki angka paling kecil,
- Lakukan langkah pertama sampai bola terurut tanpa melihat bola yang sudah diurutkan.
Setiap orang pasti memiliki cara yang berbeda untuk mengurutkan angka. Cara diatas disebut dengan cara selection sort. Dari algoritma deskripsi diatas dapat ditarik kembali masalah yang lebih spesifik lagi seperti bagaimana cara mencari bola dengan nomor paling kecil? Bagaimana cara menukar bola letak posisi bola?
Mencari nilai terkecil dalam array
Sebelum mempelajari selection sort perlu diketahui cara mencari bola dengan nomor paling kecil. Perhatikan potongan program dibawah ini
int bil[] = {90, 28, 17, 27, 26, 18, 28, 38, 27, 28};
int n = sizeof bil / sizeof(int);
int min = bil[0];
for(int i = 1; i < n; i++){
if(bil[i] < min)
min = bil[i];
}
Misalnya bil merupakan array dari bilangan yang akan diurutkan, n menyatakan panjang array, dan min menyatakan bilangan sementara yang diambil terlebih dahulu dengan asumsi bil ke 0 adalah bilangan terkecil.
Baca Juga : Perulangan atau Looping Bahasa C++
Baca Juga : Penggunaan Array C++
Baca Juga : Perulangan atau Looping Bahasa C++
Baca Juga : Penggunaan Array C++
Setelah mengasumsikan min adalah bilangan terkecil, kita membandingkan bilangan dalam variabel bil ke 1, 2, 3, 4 .. dst. sampai akhir dari array. Untuk memudahkan kita gunakan perulangan sehingga kita tidak perlu menulis program yang panjang.
Sebagai tambahan informasi 'sizeof' digunakan untuk menghitung bit array yang dibutuhkan. Integer menyimpan bit memori 4 bit setiap variabel. Dalam kasus diatas terdapat 10 bilangan integer, maka dibutuhkan 40 bit dalam variabel array bil. 40 bit dibagi dengan 4 bit pada memori. Dengan menggunakan cara ini kita dapat menentukan panjang array dengan penghitungan bit sepeti diatas.
Menukar nilai dua variabel
Setelah mengerti cara mencari nilai terkecil dalam array, kita harus menukar letak array. Bagaimana cara melakukannya? Perhatikan potongan program dibawah ini!
temp = bil[minIn];
bil[minIn] = bil[0];
bil[0] = temp;
Misalkan minIn adalah index dengan nilai yang paling kecil / minimum, temp adalah variabel yang digunakan untuk menyimpan sementara nilai dari bilangan paling kecil / minimum. Dengan menyimpan sementara variabel yang digunakan untuk menukar nilai kita dapat menukarkannya layaknya menukar wadah segelas kopi dengan segelas susu.
Setelah memahami cara mencari bilangan paling kecil . minimum dan cara menukar nilai dua variabel dengan kedua cara ini kita bisa membuat algoritma untuk mengurutkan bilangan. Sebelum membaca kelanjutan dari artikel ini, pembaca diharapkan mencoba membuatnya.
Selection sort
Selection sort memiliki kompleksitas O(n2). Apa itu kompleksitas? Kompleksitas adalah indikator berapa kali komputer bekerja untuk menyelesaikan suatu masalah. Kompleksitas diukur dari kejadian teburuk / worst case dari algoritma. Selection sort selalu menari satu persatu sampai akhir, oleh karena itu semua nilai selalu menjadi worst case.
Perhatikan dan pahamilah source code selection sort berikut ini!
Output atau keluarannya adalah sebagai berikut.
Selection sort menggunakan bilangan terkecil dan menaruhnya pada index pertama. Cobalah membuat selection sort dengan menggunakan bilangan terbesar.
Perhatikan dan pahamilah source code selection sort berikut ini!
#include <iostream>
using namespace std;
int main() {
int bil[] = {90, 28, 17, 27, 26, 18, 28, 38, 27, 28};
int n = sizeof bil / sizeof(int);
for(int i = 0; i < n; i++){
int min = bil[i];
int index = i;
for(int j = i; j < n; j++)
if(bil[j] < min){
min = bil[j];
index = j;
}
int temp = bil[index];
bil[index] = bil[i];
bil[i] = temp;
}
for(int i = 0; i < n; i++)
cout << bil[i] << " ";
}
Output atau keluarannya adalah sebagai berikut.
17 18 26 27 27 28 28 28 38 90
Selection sort menggunakan bilangan terkecil dan menaruhnya pada index pertama. Cobalah membuat selection sort dengan menggunakan bilangan terbesar.
Berkomentarlah secara bijak.
EmoticonEmoticon