Cara Menggunakan Pengurutan Seleksi

Sortir pilihan adalah teknik pengurutan yang memilih item daftar dan kemudian menukar tempatnya dengan yang lain. Ini memilih item terbesar dan kemudian menukarnya dengan item dalam indeks tertinggi dari daftar.

Algoritme melakukan ini berulang kali hingga daftar diurutkan. Jika Anda tidak yakin bagaimana cara kerja pengurutan seleksi, Anda telah datang ke tempat yang tepat. Kami akan menjelaskannya secara lebih mendalam di bawah ini, bersama dengan menunjukkan kepada Anda sebuah contoh.

Sortir Seleksi: Pandangan Lebih Dekat

Misalkan Anda memiliki daftar: [39, 82, 2, 51, 30, 42, 7]. Untuk mengurutkan daftar menggunakan sortir pilihan, Anda harus terlebih dahulu menemukan angka tertinggi di dalamnya.

Dengan daftar yang diberikan, jumlah itu adalah 82. Tukar 82 dengan angka dalam indeks tertinggi (yaitu, 7).

Setelah pass pertama, urutan daftar baru adalah: [39, 7, 2, 51, 30, 42, 82]. Setiap kali algoritma melewati seluruh daftar, itu disebut "lulus".

Perhatikan bahwa daftar mempertahankan subdaftar yang diurutkan dan subdaftar yang tidak disortir selama proses penyortiran.

Terkait: Apa itu Notasi Big-O?

Daftar asli dimulai dengan daftar nol item yang diurutkan dan daftar semua item yang tidak disortir. Kemudian setelah lulus pertama, ia memiliki daftar yang diurutkan hanya memiliki nomor 82.

Pada pass kedua, angka tertinggi dalam sublist yang tidak disortir adalah 51. Nomor ini akan ditukar dengan 42 untuk memberikan urutan daftar baru di bawah ini:

[39, 7, 2, 42, 30, 51, 82].

Proses ini diulang sampai seluruh daftar diurutkan. Gambar di bawah ini merangkum seluruh proses:

Angka yang dicetak tebal hitam menunjukkan nilai daftar tertinggi saat itu. Yang berwarna hijau menunjukkan sublist yang diurutkan.

Analisis Algoritma

Untuk mendapatkan kompleksitas (menggunakan notasi Big-O) dari algoritma ini, ikuti di bawah ini:

Pada lintasan pertama, (n-1) perbandingan dibuat. Pada lintasan kedua, (n-2). Pada lintasan ketiga, (n-3) dan seterusnya hingga lintasan (n-1) yang hanya membuat satu perbandingan.

Menyimpulkan perbandingan seperti di bawah ini memberikan:

(n-1)+ (n-1)+ (n-1)+...+1 = ((n-1)n)/2.

Oleh karena itu sort seleksi adalah O(n²).

Implementasi Kode

Kode menunjukkan fungsi yang dapat Anda gunakan untuk melakukan pengurutan pemilihan menggunakan Python dan Java.

ular piton:

def selectionSort (daftar saya):
untuk x dalam rentang (len (daftar saya) - 1, 0, -1):
max_idx = 0
untuk posn dalam jangkauan (1, x + 1):
jika daftar saya[posn] > daftar saya[max_idx]:
max_idx = posn
suhu = daftar saya[x]
daftarku[x] = daftarku[max_idx]
daftar saya[max_idx] = suhu

Jawa:

void selectionSort (int my_array[]){ 
untuk (int x = 0; x < my_array.length - 1; x++) 
{ 
int indeks = x; 
untuk (int y = x + 1; y < my_array.length; y++){ 
if (my_array[y] < my_array[index]){ 
indeks = y; // cari indeks terendah 
} 
} 
int temp = my_array[indeks]; // temp adalah penyimpanan sementara
my_array[indeks] = my_array[x]; 
my_array[x] = suhu; 
}}

Pindah Dari Sortir Seleksi ke Sortir Gabung

Seperti yang ditunjukkan oleh analisis algoritma di atas, algoritma pengurutan seleksi adalah O(n²). Ini memiliki kompleksitas eksponensial dan karena itu tidak efisien untuk kumpulan data yang sangat besar.

Algoritma yang jauh lebih baik untuk digunakan adalah merge sort dengan kompleksitas O(nlogn). Dan sekarang Anda tahu cara kerja pengurutan seleksi, selanjutnya pada daftar studi Anda untuk algoritme pengurutan adalah pengurutan gabungan.

Tentang Penulis