Untuk mengurutkan sekumpulan bilangan, dapat dilakukan dengan berbagai cara (algoritma), misalnya bubble sort, selection sort, merge sort, quick sort. Di bawah ini akan dijelaskan cara mengurutkan sekumpulan bilangan menggunakan selection sort.
Dalam selection sort ini kita memilih (select) bilangan terkecil, kemudian menempatkannya di awal. Kemudian memilih bilangan terkecil selanjutnya (terkecil kedua), dan menempatkannya di posisi setelah awal (posisi kedua). Berikutnya memilih bilangan terkecil ketiga, dan menempatkannya di posisi ketiga. Begitu seterusnya.
Misalnya diberikan sekumpulan bilangan berikut:
3 8 5 7 2 3 6 8 0 4
Maka cara mengurutkannya seperti ini.
Pertama, cari bilangan yang paling kecil dari paling kiri (posisi 1):
3 8 5 7 2 3 6 8 0 4 --------------------------------|
Pindahkan bilangan tersebut ke depan (posisi 1). Bilangan yang ada di posisi 1 tersebut dipindahkan ke posisi bilangan terkecil tadi (istilahnya swap = tukar tempat):
[0] 8 5 7 2 3 6 8 [3] 4
Maka posisi 1 sudah berisi bilangan yang tepat.
Selanjutnya, cari bilangan yang paling kecil berikutnya. Kali ini, tidak dari posisi 1 (karena di posisi tersebut sudah berisi bilangan yang tepat), tetapi cari dari posisi 2:
0 8 5 7 2 3 6 8 3 4 ------------|
Swap bilangan tersebut ke posisi 2:
0 [2] 5 7 [8] 3 6 8 3 4
Maka posisi 2 sudah berisi bilangan yang tepat.
Selanjutnya, cari bilangan yang paling kecil berikutnya. Kali ini, dari posisi 3:
0 2 5 7 8 3 6 8 3 4
------------|
Swap bilangan tersebut ke posisi 3:
0 2 [3] 7 8 [5] 6 8 3 4
Maka posisi 3 sudah berisi bilangan yang tepat.
Selanjutnya cari bilangan yang paling kecil berikutnya dari posisi 4:
0 2 3 7 8 5 6 8 3 4
--------------------|
Kemudian swap:
0 2 3 [3] 8 5 6 8 [7] 4
Selanjutnya dari posisi 5:
0 2 3 3 8 5 6 8 7 4
--------------------|
Hasil swap:
0 2 3 3 [4] 5 6 8 7 [8]
Selanjutnya dari posisi 6:
0 2 3 3 4 5 6 8 9 8
|
Karena bilangan terkecil berikutnya sudah terletak di posisinya yang sesuai, maka tidak perlu dilakukan swap.
Selanjutnya dari posisi 7:
0 2 3 3 4 5 6 8 9 8
|
Ini juga tidak perlu melakukan swap.
Selanjutnya dari posisi 8:
0 2 3 3 4 5 6 8 9 8
|
Tidak perlu swap.
Selanjutnya dari posisi 9 yang merupakan posisi terakhir. Setelah mencari bilangan terkecil dari posisi ini dan melakukan swap, kita tidak perlu melanjutkan pencarian ke posisi 10. Pada posisi tersebut sudah pasti berisi bilangan terbesar yang merupakan hasil swap-swap sebelumnya.
0 2 3 3 4 5 6 8 9 8
----|
Hasil swap terakhir (hasil ini sudah terurut):
0 2 3 3 4 5 6 8 [8] [9]
Berikut adalah contoh implementasi algoritma di atas dalam bahasa C++:
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
int N;
cout << "N = ";
cin >> N;
int bilangan[N];
cout << "bilangan (pisah dgn spasi) = ";
for (int i = 0; i < N; i++) {
cin >> bilangan[i];
}
// selection sort
for (int i = 0; i < N - 1; i++) {
// cari yg paling minimum
int posisiTerkecil = i;
for (int j = i + 1; j < N; j++) {
if (bilangan[j] < bilangan[posisiTerkecil]) {
posisiTerkecil = j;
}
}
// swap ke depan (kalo memang perlu dilakukan swap)
if (posisiTerkecil != i) {
int sementara = bilangan[i];
bilangan[i] = bilangan[posisiTerkecil];
bilangan[posisiTerkecil] = sementara;
}
}
cout << "hasil = ";
for (int i = 0; i < N; i++) {
cout << bilangan[i] << " ";
}
cout << endl;
// system("pause");
}
Dan berikut merupakan contoh implementasi dalam Java:
import java.util.Scanner;
public class SelectionSort {
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.print("N = ");
int N = sc.nextInt();
System.out.print("bilangan (pisah dgn spasi) = ");
int[] bilangan = new int[N];
for (int i = 0; i < N; i++) {
bilangan[i] = sc.nextInt();
}
// selection sort
for (int i = 0; i < N - 1; i++) {
// cari bilangan terkecil
int posisiTerkecil = i;
for (int j = i + 1; j < N; j++) {
if (bilangan[j] < bilangan[posisiTerkecil]) {
posisiTerkecil = j;
}
}
// swap (jika memang harus di-swap)
if (posisiTerkecil != i) {
int sementara = bilangan[i];
bilangan[i] = bilangan[posisiTerkecil];
bilangan[posisiTerkecil] = sementara;
}
}
System.out.print("hasil = ");
for (int i = 0; i < N; i++) {
System.out.print(bilangan[i] + " ");
}
System.out.println();
}
}
). Tim kami tidak berhasil menyelesaikan soal tersebut, sementara tim satunya berhasil. Setelah kembali ke tanah air, saya berhasil menyelesaikannya. Kegagalan ini membuat saya selalu teringat dengan soal tersebut. Pelajaran berharga memang dari pengalaman, pengalaman adalah guru terbaik. Begitu kata teman saya – 
Loading tweets...
Komentar Terkini