selection sort

Pengertian Selection Sort

Selection Sort adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan, Selection Sort membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar.

Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun) Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.

CONTOH :

Data Acak    : 5 6 8 1 3 25 10

Ascending    : 1 3 5 6 8 10 25

Descending    : 25 10 8 6 5 3 1

Konsep Selection Sort Algoritma pengurutan sederhana salah satunya adalah Selection Sort. 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.

Contoh Selection Sort :

Ascending

• Cek seluruh elemen array, temukan nilai terkecil (1) dan tukarkan posisinya dengan posisi nilai yang tersimpan pada posisi pertama dari array (3)

• Temukan nilai terkecil kedua (2), dan tukarkan posisinya dengan nilai yang berada pada posisi kedua (10).

• Dua elemen biru pertama tidak akan berubah lagi sebab mereka sudah merupakan nilai terkecil pertama dan kedua dalam array tsb.

• Sekarang, ulangi dengan cara/proses “pilih dan tukar”

• Pengurutan Selesai.

CONTOH PROGRAM

#include <iostream>

using namespace std;

void tampilkanLarik(int data[], int n)

{

    int i;

    for (i=0; i<n; i++)

        cout<< data[i]<<" ";

        cout<<endl;

}

void selection_sort(int data[], int n)

{

    int posMin, posAwal, j, temp;

    for (posAwal=0; posAwal < n-1; posAwal++)

    {

        posMin = posAwal;

        for ( j=posAwal+1; j<n; j++)

            if (data[posMin] > data[j])

                posMin=j;

            temp=data[posAwal];

            data[posAwal]=data[posMin];

            data[posMin]=temp;

            cout<< "\nHasil posAwal= "<< posAwal <<": ";

            tampilkanLarik(data,n);

        }

    }

int main()

{

   const int JUM_DATA =10;

   int i;

   int data[] = {9,13,17,89,23,90,45,87,56,32};

   selection_sort(data, JUM_DATA);

   cout<<"\nHasil Pengurutan : ";

   tampilkanLarik(data,JUM_DATA);

    return 0;

}