Selection Sort Dalam C++: Contoh Program Dan Penjelasannya

Panduan Lengkap Selection Sort dalam C++: Optimalisasi Algoritma Penyortiran

Pengantar

Selection Sort merupakan algoritma penyortiran yang sederhana dan efisien yang banyak digunakan dalam berbagai aplikasi pemrograman. Algoritma ini bekerja dengan mengidentifikasi elemen terkecil (atau terbesar) dalam sebuah array dan menukarnya dengan elemen pertama (atau terakhir). Proses ini diulangi hingga seluruh array terurut.

Cara Kerja Selection Sort

Selection Sort bekerja dengan cara membagi array menjadi dua bagian: bagian yang sudah terurut dan bagian yang belum terurut. Pada setiap iterasi, algoritma menemukan elemen terkecil (atau terbesar) dalam bagian yang belum terurut dan menukarnya dengan elemen pertama (atau terakhir) dari bagian yang belum terurut.

Proses ini diulangi hingga seluruh array terurut.

Implementasi Selection Sort dalam C++

Berikut adalah implementasi Selection Sort dalam C++:

void selectionSort(int arr[], int n) {  for (int i = 0; i < n - 1; i++) {    int min_idx = i;    for (int j = i + 1; j < n; j++) {      if (arr[j] < arr[min_idx]) {        min_idx = j;      }    }    swap(arr[min_idx], arr[i]);  }}

Analisis Kompleksitas

Kompleksitas waktu Selection Sort adalah O(n^2), di mana n adalah jumlah elemen dalam array. Hal ini karena algoritma melakukan perulangan bersarang untuk menemukan elemen terkecil (atau terbesar) dalam array.

Kompleksitas ruang Selection Sort adalah O(1), karena algoritma tidak memerlukan ruang tambahan selain array yang akan diurutkan.

Kelebihan dan Kekurangan Selection Sort

Kelebihan:

• Sederhana dan mudah diimplementasikan.
• Stabil, artinya elemen dengan nilai yang sama akan mempertahankan urutan relatifnya setelah penyortiran.
• Berjalan dengan baik pada array kecil.

Kekurangan:

• Tidak efisien untuk array besar karena kompleksitas waktu O(n^2).
• Tidak cocok untuk penyortiran online, di mana elemen ditambahkan secara bertahap.

Penggunaan Selection Sort

Selection Sort paling cocok untuk penyortiran array kecil atau ketika stabilitas penting. Algoritma ini juga dapat digunakan sebagai bagian dari algoritma penyortiran yang lebih kompleks, seperti Heap Sort.

Kesimpulan

Selection Sort adalah algoritma penyortiran yang sederhana dan efisien yang cocok untuk array kecil atau ketika stabilitas penting. Meskipun memiliki kompleksitas waktu O(n^2), algoritma ini mudah diimplementasikan dan dipahami.

Lokasi:

Berbagi :