Selection Sort – Algoritma Pengurutan

Selection sort ini adalah salah satu algoritma pengurutan yang sering dipelajari bersama beberapa algoritma pengurutan lainnya. Bagi yang masih bingung apa itu algoritma pengurutan, jadi algoritma pengurutan adalah tahapan sistematis dalam mengatur data menurut urutan atau susunan tertentu. Pada kesempatan kali ini, kita akan membahas algoritma pengurutan yaitu Selection Sort. Diagram alur atau flowchart dari program algoritma ini telah dibahas sebelumnya disini.

Apa itu Selection Sort?

Selection Sort adalah algoritma yang mengurutkan dengan cara mencari suatu nilai ekstrim seperti nilai minimal (terkecil) atau maksimal (terbesar) dari data yang disajikan untuk ditukarkan dengan elemen terujung yang ada pada suatu proses loop (perulangan). Jadi cara kerja algoritma ini adalah misalkan mencari nilai terkecil pada data atau array yang belum terurut. Kemudian nilai terkecil akan diletakkan pada posisi yang seharusnya yaitu ditukar dengan nilai pada indeks pertama atau 0. Lalu dicari lagi nilai terkecil kedua dan ditukar dengan nilai pada indeks ke 1 dan begitu seterusnya.

Ilustrasi Penerapan Selection Sort

Kondisi awal array

Kita akan mencoba algoritma Selection Sort untuk mengurutkan data berbentuk array berisi 5 elemen yang berpola acak.

Perulangan pertama

• Ilustrasi di atas adalah proses pengurutan dengan Selection Sort pada perulangan pertama
• Kita akan mengurutkan data secara menaik (kecil ke besar), oleh karena itu kita perlu mencari nilai terkecil terlebih dahulu
• Siapkan juga variabel pos (posisi) yang akan menampung indeks dengan nilai terkecil
• Pada perulangan pertama, variabel pos dimulai dari indeks 0 dengan nilai elemen yaitu 5
• Kemudian kita cari apakah ada nilai lain yang lebih kecil dari 5
• Pada indeks ke 2 kita menemukan terdapat angka 3 yang lebih kecil dari 5, maka kita rubah variabel pos jadi sama dengan indeks 2
• Selanjutnya kita cari lagi hingga elemen terkahir pada array
• Kita menemukan angka 2 yang ternyata lebih kecil daripada 3. Angka ini berada pada indeks ke 4, maka kita rubah variabel pos menjadi 4
• Apa yang akan kita lakukan selanjutnya? Kita akan menukar elemen pada indeks pos yaitu 4, dengan elemen pada indeks pertama yaitu 0
• Mari kita lanjut ke ilustrasi selanjutnya

Ilustrasi Proses Selection Sort

• Ilustrasi di atas menggambarkan hasil proses dari setiap perulangan, sedangkan ilustrasi sebelumnya menggambarkan apa yang terjadi pada setiap perulangan
• Pada perulangan pertama kita menemukan bahwa angka 2 adalah angka terkecil sesuai dengan ilustrasi sebelumnya. Maka kita tukar dengan elemen pada indeks pertama, indeks pertama telah menemukan nilai yang cocok dan selanjutnya dapat kita abaikan
• Kita lanjut ke perulangan kedua dan ditemukan bahwa angka 3 adalah angka terkecil selanjutnya. Maka kita letakkan angka 3 berada di indeks setelah angka 2 dengan cara menukarnya
• Pada perulangan ketiga, angka terkecil yang selanjutnya ditemukan adalah 5. Maka untuk memindahkannya ke posisi yang tepat, kita lakukan pertukaran dengan nilai pada indeks ke 2
• Kemudian pada perulangan keempat, kita temukan angka 7 adalah angka yang terkecil. Lalu kita pindahkan ke

Jadi algoritma Selection Sort ini mengecek posisi mulai dari indeks ke 0, kemudian ia akan mencari angka terkecil / terbesar untuk diletakkan pada posisi yang tepat tersebut. Jika angka terkecil sudah berada pada posisi yang tepat, maka tidak ada pertukaran. Perlu teman teman ketahui, jika pada exhange sort kita menggunakan pivot dan menukar setiap elemen pada pivot untuk mencari nilai yang cocok. Pada Selection Sort ini, kita mencari angka nya dulu baru kemudian ditukar dengan posisi yang seharusnya.

Program Selection Sort dengan C++

#include <iostream>
using namespace std;

int main() {
    int pos; // untuk menampung indeks dari nilai yg dicari
    int ukuranArray = 5;
    int arr[ukuranArray] = {5, 7, 3, 9, 2};
 	
    return 0;
}

#include <iostream>
using namespace std;
void tukar(int *, int *);
void cetakArray(int arr[], int ukuranArray);

int main() {
    int pos; // untuk menampung indeks dari nilai yg dicari
    int ukuranArray = 5;
    int arr[ukuranArray] = {5, 7, 3, 9, 2};
 	
    cout << "Keadaan awal array" << endl;
    cetakArray(arr, ukuranArray);
    cout << endl;


    /*
     *
     * algoritma Selection Sort
     *
     */

    cout << "\nHasil Akhir Pengurutan: " << endl;
    cetakArray(arr, ukuranArray);
    return 0;
}

void tukar(int *a, int *b){
 	int t=*a;
 	*a=*b;
	 *b=t;
}

void cetakArray(int array[], int ukuranArray){
    for(int i = 0; i < ukuranArray; i++) {
        cout << array[i] << "  ";
	} cout << endl;
}

#include <iostream>
using namespace std;
void tukar(int *, int *);
void cetakArray(int arr[], int ukuranArray);

int main() {
    int pos; // untuk menampung indeks dari nilai yg dicari
    int ukuranArray = 5;
    int arr[ukuranArray] = {4, 7, 3, 9, 2};
 	
    cout << "Keadaan awal array" << endl;
    cetakArray(arr, ukuranArray);
    cout << endl;

    // algoritma Selection Sort
    for (int i = 0; i < ukuranArray - 1; i++) {
        pos = i;
        for (int j = i + 1; j < ukuranArray; j++) {
            // mencari nilai terkecil
            if (arr[j] < arr[pos]) {
                pos = j;
            }
        }
        if (pos != i) {
            tukar(&arr[pos], &arr[i]);
            cetakArray(arr, ukuranArray);
        }
    }

    cout << "\nHasil Akhir Pengurutan: " << endl;
    cetakArray(arr, ukuranArray);
    return 0;
}

void tukar(int *a, int *b){
 	int t=*a;
 	*a=*b;
	 *b=t;
}

void cetakArray(int array[], int ukuranArray){
    for(int i = 0; i < ukuranArray; i++) {
        cout << array[i] << "  ";
	} cout << endl;
}

Kesimpulan

Algoritma pengurutan Selection Sort ini sudah mengetahui posisi mana yang akan gunakan, selanjutnya ia hanya akan mencari angka yang cocok untuk diletakkan pada posisi tersebut. Pencarian angka terkecil atau terbesar dapat disesuaikan pada logika if yang mencari posisi.