shell Sort

shell sort

DASAR

Selection sort adalah salah satu algoritma yang digunakan untuk memecahkan masalah pengurutan(sorting) data pada suatu larik(array). Ide dasar algoritma ini adalah melakukan beberapa kali  pass untuk melakukan penyeleksian elemen array. 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, jika dilakukan sorting descending(menurun), elemen yang terbesar dari array yang belum terurut disimpan indeksnya untuk kemudian dilakukan pertukaran dengan nilai indeks yang terbesar dari elemen array.

Penggunaan algoritma selection sort sering kita jumpai ketika kita akan mengurutkan sejumlah kartu bridge. Kita susun beberapa kartu bridge dalam suatu larik kemudian kita lakukan selction sort dengan memilih kartu yang nilainya paling kecil(jika ascending) lalu kita tukar dengan kartu yang paling ujung dari kartu-kartu yang belum terurut hingga akhirnya didapatkan kartu-kartu yang telah terurut.

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

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.

Contoh simulasi algoritma selection sort sbb :
jika kita memiliki elemen array sbb :  {5, 1, 12, -5, 16, 2, 12, 14}

 

 

Algoritma di dalam Selection Sort terdiri dari kalang bersarang. Dimana kalang tingkat pertama (disebut pass).berlangsung N-1 kali. Di dalam kalang kedua, dicari elemen dengan nilai terkecil. Jika didapat, indeks yang didapat ditimpakan ke variabel min. Lalu dilakukan proses penukaran. Begitu seterusnya untuk setiap Pass. Pass sendiri makin berkurang hingga nilainya menjadi semakin kecil. Berdasarkan operasi perbandingan elemennya.

Implementasinya dalam bahasa pemrograman sbb :

public class Bledek {

public static void main(String[] args){

    int[] x = {5, 1, 12, -5, 16, 2, 12, 14};

int i, temp, j;

System.out.println("Sebelum diurutkan :");

for(i=0;i<x.length;i++)

System.out.print(x[i]+"\t");

System.out.println("\n");

for(i=0;i<x.length-1;i++){

    for(j=i+1;j<x.length;j++){

        if(x[i]>x[j]){

            temp = x[i];

x[i] = x[j];

x[j] = temp;

}

}

for(int k=0;k<x.length;k++)

System.out.print(x[k]+"\t");

System.out.println();

}

System.out.println("Setelah diurutkan :");

for(i=0;i<x.length;i++)

System.out.print(x[i]+"\t");

}

}

Visualisasi algoritmanya sebagai berikut :