Home > Algorithm > Selection Sort

Selection Sort


Selection sort merupakan kombinasi dari searching dan sorting. Sebuah algoritma pengurutan yang secara berulang mencari item yang belum terurut dan mencari paling sedikit satu untuk dimasukkan ke dalam lokasi akhir. Metode ini memiliki konsep memilih data yang maksimum/minimum dari suatu kumpulan data larik L, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, diasingkan ke tempat lain, dan tidak diikutsertakan pada proses pencarian data maksimum/minimum berikutnya.

Algoritma pengurutan selection sort ini termasuk algoritma sulit dibagi/ mudah digabung (hard split/easy join).  Dari proses pengurutannya, Selection sort ini memiliki dua buah varian yaitu :

1. Maximum Sort

memilih data yang maksimum dari suatu kumpulan data larik, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data maksimum berikutnya.

2. Minimum Sort

memilih data yang minimum dari suatu kumpulan data larik , lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data minimum berikutnya.

Dalam pemecahan masalah algoritma selection sort , kita dapat memilih dua metode alternatif algoritma antara lain pemecahan dengan metode Brute Force dan pemecahan dengan metode devide and conquer.

Metode Pemecahan Brute Force

Kekuatan algoritma brute force terletak pada kemampuannya untuk menemukan semua pemecahan masalah yang mungkin, akan tetapi langkah yang dibutuhkan sangat banyak sehingga tidak baik jika digunakan untuk memecahkan masalah yang memiliki masukan yang cukup besar. Mengurutkan secara ascending dengan metode brute force

procedure SelectionSort(input/output L[1..N]: array of integer)
{Mengurutkan larik L[1..N] sehingga terurut menaik dengan metode selection sort. Asumsi : nilai N (jumlah elemen array) diketahui dan elemen larik L sudah terdefinisi nilainya }

Kamus
   i,j : integer
   temp : integer {temporary}
   Imaks : integer {indeks yang berisi nilai maks sementara}

Algoritma
   for i = n downto 2 do</p>
      Imaks ← i
      {elemen terakhir diasumsikan sebagai elemen maksimum sementara}
      for j = 1 to (i-1)
         if L[j] > L[Imaks] then
            Imaks ← j
         endif
      endfor
      {pertukaran L[i] dengan L[Imaks]</p>
      If L[i] <> L[Imaks] then
         temp ← L[i]
         L[i] ← L[Imaks]
         L[Imaks]  ← temp
      endif
   endfor

Run dari Procedure selection sort ascending :

Misalkan diberikan contoh Larik seperti berikut , perintah dari soal adalah mengurutkan larik berisi elemen-elemen acak berikut sehingga menjadi terurut menaik (ascending) menggunakan metode brute force dengan algoritma selection sort :

Cari elemen maksimum dari larik dengan perulangan. Lalu didapat hasilnya maks = 9 pada elemen ke-3 dari larik , tukarkan elemen maksimum dengan elemen terakhir pada larik yaitu ke-6 .  Selanjutnya lakukan perulangan mencari nilai maksimum, namun elemen terakhir tidak perlu di cek kembali. Cukup larik 1 – 5 saja yang dicek . akan didapat nilai maksimum 8, karena ia telah berada diposisi no 2 terakhir, jadi ia tidak perlu dipindah lagi sampai akhirnya semua elemen maksimum telah ditukar posisinya dan semuanya terurut secara ascending.

Simulasi :

Masalah

5

7

9

1

8

2

Iterasi 1

5

7

2

1

8

9

Iterasi 2

5

7

2

1

8

9

Iterasi 3

5

1

2

7

8

9

Iterasi 4

2

1

5

7

8

9

Iterasi 5

1

2

5

7

8

9

Terurut

procedure SelectionSort (input/output L[1..N]: array of integer)

{Mengurutkan larik L[1..N] sehingga terurut menaik dengan metode selection sort.

Asumsi : nilai N (jumlah elemen array) diketahui dan elemen larik L sudah terdefinisi nilainya }

Kamus

i,j : integer

temp : integer {temporary}

Imaks : integer {indeks yang berisi nilai maks sementara}

Algoritma

for i = n downto 2 do

Imaks ← i {elemen terakhir diasumsikan sebagai elemen maksimum sementara}

for j = 1 to (i-1) do

if L[j] > L[Imaks]then

Imaks ← j

endif

endfor

{pertukaran L[i] dengan L[Imaks]

If L[i] <> L[Imaks] then

temp ← L[i]

L[i] ← L[Imaks]

L[Imaks] ← temp

endif

endfor

Categories: Algorithm Tags:
  1. No comments yet.
  1. October 11, 2016 at 6:12 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: