Algoritma pengurutan ini disebut pengurutan seleksi (selection sort) karena gagasan pada dasarnya adalah memiliki elemen maksimum / minimum dari larik, lalu menempatkan elemen maksimum / minimum itu pada awal atau akhir larik (elemen terujung).
Ada dua variasi algoritma pengurutan seleksi ditinjau dari pemilian elemen maksimum / minimum, yaitu :
1. Algoritma pengurutan seleksi-maksimum, yaitu memilh elemen maksimum sebagai basis pengurutan.
2. Algoritma pengurutan seleksi-minimum, yaitu memilih elemen minimumsebagai basis pengurutan.
Algoritma Pengurutan Seleksi-Maksimum Ascending
Tinjau larik dengan n = 6 buah elemen dibawah ini belum terurut. Larik ini akan diurut menaik dengan metode seleksi-maksimum :
29
|
27
|
10
|
8
|
76
|
21
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 1
Cari elemen maksimum didalam larik L[1..6], maka hasilnya : maks = L[5] = 76. Pertukaran maks dengan L[n], diperoleh :
29
|
27
|
10
|
8
|
21
|
76
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 2
(Berdasarkan susunan larik hasil proses 1)
Cari elemen maksimum didalam larik L[1..5], maka hasilnya : maks = L[1] = 29. Pertukaran maks dengan L[5], diperoleh :
21
|
27
|
10
|
8
|
29
|
76
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 3
(Berdasarkan susunan larik hasil proses 2)
Cari elemen maksimum didalam larik L[1..4], maka hasilnya : maks = L[2] = 27. Pertukaran maks dengan L[4], diperoleh :
21
|
8
|
10
|
27
|
29
|
76
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 4
(Berdasarkan susunan larik hasil proses 3)
Cari elemen maksimum didalam larik L[1..3], maka hasilnya : maks = L[1] = 21. Pertukaran maks dengan L[3], diperoleh :
10
|
8
|
21
|
27
|
29
|
76
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 5
(Berdasarkan susunan larik hasil proses 4)
Cari elemen maksimum didalam larik L[1..2], maka hasilnya : maks = L[1] = 10. Pertukaran maks dengan L[2], diperoleh :
8
|
10
|
21
|
27
|
29
|
76
|
1
|
2
|
3
|
4
|
5
|
6
|
Sehingga tersisa satu elemen yaitu 8, maka pengurutan selesai. Larik L sudah terurut menaik.
Algoritma Pengurutan Seleksi-Maksimum(menaik).
Procedure SelectionSort1 (input / output L : Larikint, input n : integer )
{I.S. : Elemen larik L sudah terdefinisi harganya. }
{F.S. : Elemen larik L terurut menaik sedemikian sehingga L[1] < L[2] < _ < L[n] }
Kamus
i : integer {pencacah proses}
j : integer {pencacah untuk mencari nilai maksimum}
imaks : integer {indeks yang berisi nilai maksimum sementara}
maks : integer {elemen maksimum}
temp : integer {peubah bantu untuk pertukaran}
Algoritma
for i <-- n downto 2 do { jumlah proses sebanyak n – 1 }
{ Carielemen maksimum pada elemen L[1..i] }
imaks <-- 1 {Elemen pertama diasumsikan sebagai elemen maksimum sementara }
maks <-- L[1] { Elemen maksimum }
for j <-- 2 to i do
if L[j] > maks then
imaks <-- j
maks ß [j]
endif
endfor
{ pertukaran maks dengan L[i] }
temp <-- L[i]
L[i] <-- maks
L[imaks] <-- tempt
endfor
Apabila ingin larik yang terurut menurun, maka algoritma pengurutan seleksi-minimum sebagai sbb :
Tinjau larik dengan n = 6 buah elemen dibawah ini yang belum terurut. Larik ini akan diurut menurun ( Descending ) dengan metode pengurutan seleksi-maksimum.
29
|
27
|
10
|
8
|
76
|
21
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 1
Cari elemen maksimum didalam larik L[1..6], maka hasilnya : imaks = 5, L[imaks] = 76. Pertukaran L[imaks] dengan L[1], diperoleh :
76
|
27
|
10
|
8
|
29
|
21
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 2
(berdasarkan susunan larik hasil proses 1)
Cari elemen maksimum didalam larik L[2..6], maka hasilnya : imaks = 5, L[imaks] = 29.
Pertukaran L[imaks] dengan L[2], diperoleh :
76
|
29
|
10
|
8
|
27
|
21
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 3
(berdasarkan susunan larik hasil proses 2)
Cari elemen maksimum didalam larik L[3..6], maka hasilnya : imaks = 5, L[imaks] = 27.
Pertukaran L[imaks] dengan L[3], diperoleh :
76
|
29
|
27
|
8
|
10
|
21
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 4
(berdasarkan susunan larik hasil proses 3)
Cari elemen maksimum didalam larik L[4..6], maka hasilnya : imaks = 6, L[imaks] = 21.
Pertukaran L[imaks] dengan L[4], diperoleh :
76
|
29
|
27
|
21
|
10
|
8
|
1
|
2
|
3
|
4
|
5
|
6
|
Proses 5
(berdasarkan susunan larik hasil proses 4)
Cari elemen maksimum didalam larik L5..6], maka hasilnya : imaks = 5, L[imaks] = 10.
Pertukaran L[imaks] dengan L[5] (sebenarnya tidak perlu dilakukan sebab 10 sudah berada pada posisi yang tepat), diperoleh :
76
|
29
|
27
|
21
|
10
|
8
|
1
|
2
|
3
|
4
|
5
|
6
|
Sehingga larik L sudah terurut menurun.
Algoritma Pengurutan Seleksi-Maksimum(menurun)
Procedure SelectionSort2 (input / output L : Larikint, input n : integer )
{I.S. : Elemen larik L sudah terdefinisi harganya. }
{F.S. : Elemen larik L terurut menurun sedemikian sehingga L[1] > L[2] > _ > L[n] }
Kamus
i : integer {pencacah proses}
j : integer {pencacah untuk mencari nilai maksimum}
imaks : integer {indeks yang berisi nilai maksimum sementara}
maks : integer {elemen maksimum}
temp : integer {peubah bantu untuk pertukaran}
Algoritma
for i <-- 1 to n - 1 do
{ Cari indeks elemen maksimum pada elemen L[i..n] }
imaks <-- i {Elemen pertama diasumsikan sebagai elemen maksimum sementara }
for j <-- i + 1 to n do
if L[j] > L[imaks] then
imaks <-- j
endif
endfor
{ pertukaran maks dengan L[i] }
temp <-- L[i]
L[i] <-- maks
L[imaks] <-- tempt
endfor
Sumber : Munir, Renaldi. (2011). Algoritma & Pemrogramman Dalam Bahasa Pascal dan C. (edisi revisi). Bandung ; INFORMATIKA.
0 komentar:
Posting Komentar