Selection Sort adalah salah satu algoritma pengurutan sederhana yang sering digunakan dalam pemrograman. Algoritma ini bekerja dengan memilih elemen terkecil dari daftar yang belum diurutkan dan menukar posisinya dengan elemen pertama dari daftar. Proses ini diulang secara berulang hingga seluruh daftar terurut dengan benar. Meskipun tergolong sebagai algoritma yang sederhana, Selection Sort memiliki keunggulan dan kelemahan tersendiri. Pada artikel ini, kita akan membahas pengertian, langkah-langkah, serta analisis kecepatan dan kompleksitas waktu dari Selection Sort.
Langkah pertama dalam Selection Sort adalah mencari elemen terkecil dari daftar yang belum diurutkan. Proses ini dimulai dari elemen pertama hingga elemen terakhir. Jika elemen terkecil ditemukan, maka elemen tersebut akan ditukar dengan elemen pertama dari daftar. Setelah itu, proses pencarian elemen terkecil dilakukan pada daftar yang belum diurutkan, tetapi kali ini dimulai dari elemen kedua hingga elemen terakhir. Elemen terkecil yang ditemukan akan ditukar dengan elemen kedua dari daftar. Proses ini akan terus berlanjut hingga seluruh daftar terurut dengan benar.
Salah satu keunggulan Selection Sort adalah sederhananya algoritma ini. Langkah-langkahnya mudah dipahami dan diimplementasikan dalam bahasa pemrograman apapun. Selain itu, algoritma ini juga cocok digunakan pada daftar dengan jumlah elemen yang kecil atau jika daftar tersebut hampir terurut. Kelemahan dari Selection Sort adalah kecepatan eksekusinya yang relatif lambat dibandingkan dengan algoritma pengurutan lainnya. Hal ini disebabkan oleh banyaknya jumlah pertukaran yang terjadi selama proses pengurutan. Bahkan jika daftar sudah terurut sebelumnya, Selection Sort akan tetap melalui seluruh langkahnya.
Untuk memahami lebih lanjut tentang kecepatan dan kompleksitas waktu Selection Sort, kita perlu menganalisisnya secara lebih mendalam. Misalkan terdapat n elemen dalam daftar yang akan diurutkan menggunakan Selection Sort. Pada setiap iterasi, Selection Sort akan mencari elemen terkecil dari daftar yang belum diurutkan. Jumlah perbandingan yang dilakukan pada iterasi pertama adalah (n-1), pada iterasi kedua adalah (n-2), dan seterusnya. Jumlah total perbandingan yang dilakukan adalah sebagai berikut:
(n-1) + (n-2) + (n-3) + … + 1 = (n * (n-1)) / 2
Dalam notasi Big O, kompleksitas waktu Selection Sort adalah O(n^2). Artinya, waktu eksekusi Selection Sort akan meningkat secara kuadratik seiring dengan peningkatan jumlah elemen dalam daftar. Oleh karena itu, algoritma ini tidak efisien untuk digunakan pada daftar dengan jumlah elemen yang sangat besar.
Meskipun memiliki kompleksitas waktu yang tinggi, Selection Sort masih memiliki kegunaannya dalam beberapa kasus. Algoritma ini dapat digunakan ketika jumlah elemen dalam daftar relatif kecil atau jika daftar hampir terurut. Selain itu, Selection Sort juga dapat digunakan sebagai algoritma pengurutan awal sebelum menggunakan algoritma pengurutan lain yang lebih efisien. Dalam beberapa kasus, langkah-langkah sederhana dari Selection Sort dapat memberikan hasil yang lebih baik daripada algoritma pengurutan lain yang lebih kompleks.
Dalam kesimpulan, Selection Sort adalah salah satu algoritma pengurutan sederhana yang sering digunakan dalam pemrograman. Meskipun sederhana, algoritma ini memiliki keunggulan dan kelemahan tersendiri. Keunggulannya terletak pada sederhananya langkah-langkah dan kemampuan mengurutkan daftar dengan jumlah elemen yang kecil atau daftar yang hampir terurut. Namun, kelemahannya adalah kecepatan eksekusinya yang lambat dibandingkan dengan algoritma pengurutan lainnya. Oleh karena itu, pemilihan algoritma pengurutan yang tepat perlu dipertimbangkan berdasarkan kebutuhan dan karakteristik daftar yang akan diurutkan.
Pengertian Selection Sort
Apa itu Selection Sort?
Selection Sort adalah salah satu algoritma pengurutan sederhana yang digunakan untuk mengurutkan elemen-elemen dalam sebuah array. Algoritma ini bekerja dengan cara mencari elemen terkecil dari array dan menukar posisinya dengan elemen pertama. Kemudian, mencari elemen terkecil kedua dari array dan menukar posisinya dengan elemen kedua. Proses ini berlanjut hingga semua elemen dalam array terurut secara ascending.
Bagaimana Cara Kerja Selection Sort?
Cara kerja Selection Sort dapat dijelaskan dalam beberapa langkah berikut:
1. Mencari elemen terkecil dalam array.
2. Menukar posisi elemen terkecil dengan elemen pertama dalam array.
3. Mencari elemen terkecil kedua dalam array, mulai dari elemen kedua hingga elemen terakhir.
4. Menukar posisi elemen terkecil kedua dengan elemen kedua dalam array.
5. Proses ini diulang hingga semua elemen dalam array terurut.
Dengan kata lain, Selection Sort membagi array menjadi dua bagian, yaitu bagian terurut dan bagian belum terurut. Pada setiap iterasi, algoritma ini mencari elemen terkecil dari bagian belum terurut dan menukar posisinya dengan elemen terdepan dari bagian belum terurut.
Apa Kelebihan dan Kekurangan Selection Sort?
Kelebihan dari Selection Sort adalah sebagai berikut:
1. Sederhana: Algoritma ini sangat sederhana dan mudah dipahami.
2. Efisien untuk Jumlah Data Kecil: Selection Sort bekerja dengan baik pada jumlah data yang kecil.
Namun, Selection Sort juga memiliki kekurangan, yaitu:
1. Tidak Efisien untuk Jumlah Data Besar: Algoritma ini tidak efisien untuk jumlah data yang besar karena kompleksitas waktu yang tinggi.
2. Tidak Stabil: Jika terdapat dua elemen dengan nilai yang sama, posisi relatif kedua elemen tersebut dapat berubah setelah proses pengurutan.
Kapan Harus Menggunakan Selection Sort?
Selection Sort cocok digunakan dalam situasi-situasi berikut:
1. Jumlah data yang kecil.
2. Ketika stabilitas pengurutan tidak menjadi masalah.
3. Ketika kompleksitas algoritma bukan faktor yang krusial.
Dalam kasus-kasus lain, terutama ketika jumlah data besar, algoritma pengurutan lain seperti Quick Sort atau Merge Sort lebih disarankan.
Contoh Implementasi Selection Sort
Berikut adalah contoh implementasi Selection Sort dalam bahasa pemrograman C++:
“`cpp
#include
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
cout << "Array setelah diurutkan: \n";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
“`
Output:
“`
Array setelah diurutkan:
11 12 22 25 64
“`
Dalam contoh di atas, terdapat array dengan elemen {64, 25, 12, 22, 11}. Setelah proses Selection Sort, array tersebut akan terurut menjadi {11, 12, 22, 25, 64}.
Kesimpulan
Selection Sort adalah algoritma pengurutan sederhana yang bekerja dengan mencari elemen terkecil dari array dan menukar posisinya dengan elemen pertama. Proses ini diulang hingga semua elemen dalam array terurut. Algoritma ini sederhana dan efisien untuk jumlah data kecil, namun tidak efisien untuk jumlah data besar. Selection Sort cocok digunakan dalam situasi-situasi dengan jumlah data kecil dan ketika stabilitas pengurutan tidak menjadi masalah.
FAQs: Pengertian Selection Sort
1. Apa itu Selection Sort?
Selection Sort adalah algoritma pengurutan sederhana yang bekerja dengan memilih elemen terkecil dari daftar dan menukar posisinya dengan elemen pertama. Kemudian, algoritma ini memilih elemen terkecil kedua dan menukarnya dengan elemen kedua, dan seterusnya hingga seluruh daftar terurut.
2. Bagaimana cara kerja Selection Sort?
Selection Sort bekerja dengan membagi daftar menjadi dua bagian: bagian terurut dan bagian tidak terurut. Pada awalnya, bagian terurut kosong dan seluruh daftar berada dalam bagian tidak terurut. Algoritma ini secara berulang mencari elemen terkecil dari bagian tidak terurut dan menukarnya dengan elemen pertama dari bagian tidak terurut. Dengan setiap iterasi, bagian terurut bertambah satu elemen, sedangkan bagian tidak terurut berkurang satu elemen. Proses ini berlanjut hingga seluruh daftar terurut.
3. Apa kelebihan dan kekurangan Selection Sort?
Kelebihan dari Selection Sort adalah:
- Sederhana dan mudah dipahami.
- Menggunakan sedikit ruang penyimpanan tambahan.
Namun, Selection Sort juga memiliki kekurangan:
- Memiliki kompleksitas waktu yang tinggi, terutama pada daftar yang besar.
- Tidak efisien untuk daftar yang sudah hampir terurut.
4. Kapan sebaiknya menggunakan Selection Sort?
Selection Sort sebaiknya digunakan pada daftar yang relatif kecil atau ketika kompleksitas waktu bukanlah faktor yang kritis. Algoritma ini juga cocok digunakan ketika ruang penyimpanan tambahan terbatas atau terbatasnya akses ke elemen daftar.
5. Apakah Selection Sort stabil?
Selection Sort tidak stabil. Artinya, jika ada dua elemen dengan nilai yang sama, urutan relatif mereka mungkin berubah setelah proses pengurutan.
6. Apa kompleksitas waktu Selection Sort?
Kompleksitas waktu Selection Sort adalah O(n^2), di mana n adalah jumlah elemen dalam daftar. Hal ini disebabkan oleh adanya dua loop bersarang yang digunakan dalam algoritma ini.
