Algoritma Sorting : Selection Sort

Selection sort adalah algoritma untuk sorting samaseperti halnya dengan Insertion sort yang simpel, namun tidak efisien.

Pada perulangan pertama, metode ini akan memilih elemen terkecil dari array, kemudian menukarnya dengan elemen pertama.


Selanjutnya pada perulangan kedua, akan memilih nilai terkecil kedua (atau elemen dengan nilai terkecil diantara seluruh elemen yang tersisa), dan kemudian menukarnya dengan elemen yang kedua.


selection sort

Algoritma akan terus berlanjut sampai perulangan terakhir memilih elemen dengan nilai terbesar kedua, kemudian menukarnya dengan index terakhir kedua, sehingga meninggalkan elemen terbesar di index terakhir. Setelah perulangan ke-i, maka elemen i terkecil dari array akan diurutkan dengan urutan meningkat dalam elemen pertama i dari array.

Sebagai contoh perhatikan array di bawah ini:

22 34 18 10 42 56 68 29 77 56

Maka program pertama-tama akan menetapkan elemen terkecil dari array terlebih dahulu, dalam hal ini yaitu angka10 yang berada di index 4. Kemudian akan ditukar dengan angka 22, sehingga menghasilkan:

10 34 18 22 42 56 68 29 77 56

Kemudian dari hasil pertukaran tersebut, program akan menyeleksi lagi nilai terkecil dari elemen yang tersisa yaitu kecuali angka 10. Hasil dari seleksi tersebut adalah angka 18 yang terdapat di index 2. Kemudian program akan menukar angka 18 dengan 34, sehingga menghasilkan:

10 18 34 22 42 56 68 29 77 56

Program akan terus melakukan sistem perulangan tersebut sampai dengan seluruh elemen array berurut.

Contoh:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class SelectionSort {
 
 public static void selectionSort (int [] myList){
  
  for (int i = 0; i < myList.length - 1; i++){
   int nilaiMinimum = myList[i];
   int indexNilaiMinimum = i;
   
   for(int j = i + 1; j < myList.length; j++){
    if(nilaiMinimum > myList[j]){
     nilaiMinimum = myList[j];
     indexNilaiMinimum = j;
    }
   }
   
   if(indexNilaiMinimum != i){
    myList[indexNilaiMinimum] = myList [i];
    myList[i] = nilaiMinimum;
   }
  }
  
 }
 
 public static void main(String args []){
  
  int myArray [] = {22, 34, 18, 10, 42, 56, 68, 29, 77, 56};
  SelectionSort.selectionSort(myArray);
  
  //Menampilkan array
  for (int i = 0; i < myArray.length; i++){
    System.out.print(myArray[i] + " ");
  }
    
  
 }

}

Output:
10 18 22 29 34 42 56 56 68 77

No comments

Bahasa Java. Powered by Blogger.