Pemrograman · Algoritme
Penjelasan selection sort: cara kerja, kode, dan kompleksitas
Jawaban singkat
Selection sort membagi list menjadi bagian terurut di kiri dan bagian belum terurut di kanan. Pada setiap langkah, algoritma mencari elemen terkecil di bagian belum terurut lalu menukarnya ke posisi belum terurut yang pertama. Algoritma ini selalu melakukan sekitar n²/2 perbandingan, sehingga O(n²) pada semua kasus, tetapi melakukan paling banyak n − 1 pertukaran dan memakai ruang tambahan O(1). Versi array yang umum tidak stabil.
Buka Urut barisIde dasar dengan kata-kata sederhana
Pindai seluruh list dan temukan elemen terkecil. Tukar dengan elemen di indeks 0; sekarang indeks 0 sudah final. Pindai sisa list mulai dari indeks 1, temukan yang terkecil, lalu tukar ke indeks 1. Lanjutkan sampai tersisa satu elemen, yang pasti merupakan yang terbesar.
Tidak seperti bubble sort dan insertion sort, selection sort tidak diuntungkan oleh input yang sudah terurut: algoritma ini tetap harus memindai setiap elemen yang tersisa untuk memastikan sudah menemukan nilai minimum.
Contoh langkah demi langkah
Urutkan [64, 25, 12, 22, 11]. Bagian sebelum garis sudah terurut dan final.
| Langkah | Bagian belum terurut | Minimum yang ditemukan | Pertukaran | List setelah langkah |
|---|---|---|---|---|
| 1 | 64, 25, 12, 22, 11 | 11 di indeks 4 | indeks 0 ↔ 4 | [11 | 25, 12, 22, 64] |
| 2 | 25, 12, 22, 64 | 12 di indeks 2 | indeks 1 ↔ 2 | [11, 12 | 25, 22, 64] |
| 3 | 25, 22, 64 | 22 di indeks 3 | indeks 2 ↔ 3 | [11, 12, 22 | 25, 64] |
| 4 | 25, 64 | 25 di indeks 3 | tidak perlu | [11, 12, 22, 25 | 64] |
Empat langkah untuk lima elemen, dengan 4 + 3 + 2 + 1 = 10 perbandingan dan tiga pertukaran sungguhan.
Implementasi Python
def selection_sort(items):
"""Sort a list in place, ascending. Returns the same list."""
n = len(items)
for i in range(n - 1):
smallest = i
for j in range(i + 1, n):
if items[j] < items[smallest]:
smallest = j
if smallest != i:
items[i], items[smallest] = items[smallest], items[i]
return items
print(selection_sort([64, 25, 12, 22, 11])) # [11, 12, 22, 25, 64]
print(selection_sort([2, 1])) # [1, 2]Perulangan luar berjalan n − 1 kali karena elemen terakhir yang tersisa otomatis sudah di tempatnya. Perulangan dalam hanya mencatat sebuah indeks; pertukaran terjadi sekali per langkah luar.
Kompleksitas waktu dan ruang
| Ukuran | Nilai | Alasan |
|---|---|---|
| Perbandingan, semua kasus | n(n − 1)/2 | setiap langkah memindai seluruh bagian belum terurut |
| Waktu, terbaik / rata-rata / terburuk | O(n²) | pemindaian tidak bergantung pada urutan |
| Pertukaran, terburuk | n − 1 | paling banyak satu pertukaran per langkah |
| Ruang tambahan | O(1) | di tempat, satu variabel indeks |
Jumlah penulisan yang sedikit adalah satu-satunya kekuatan nyata selection sort. Jika menulis ke memori jauh lebih mahal daripada membaca, seperti pada sebagian memori flash atau saat memindahkan record besar, penulisan yang lebih sedikit bisa berarti. Cycle sort melangkah lebih jauh dengan menulis setiap elemen paling banyak satu kali.
Stabilitas: mengapa selection sort tidak stabil
Sort yang stabil mempertahankan urutan relatif elemen yang sama. Pertukaran jarak jauh pada selection sort dapat melompatkan sebuah elemen melewati elemen lain yang bernilai sama.
def selection_sort_by_key(items, key):
n = len(items)
for i in range(n - 1):
m = min(range(i, n), key=lambda j: key(items[j]))
items[i], items[m] = items[m], items[i]
return items
cards = [("4", "hearts"), ("4", "spades"), ("2", "clubs")]
print(selection_sort_by_key(cards, key=lambda c: c[0]))
# [('2', 'clubs'), ('4', 'spades'), ('4', 'hearts')] order of the 4s changedAngka 2 ditukar dengan 4 hati, yang memindahkan 4 hati ke belakang 4 sekop. Versi stabil ada: alih-alih menukar, keluarkan nilai minimum dan sisipkan di posisi i, sambil menggeser yang lain ke kanan. Cara ini menjaga urutan tetapi memakan O(n) penulisan per langkah.
Perbandingan selection sort dengan sort lain
| Algoritma | Terbaik | Rata-rata | Terburuk | Ruang tambahan | Stabil |
|---|---|---|---|---|---|
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | Tidak |
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Ya |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Ya |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Tidak |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ya |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Tidak |
Heapsort adalah selection sort dengan struktur data yang lebih baik: ia juga berulang kali memilih elemen terbesar yang tersisa, tetapi menemukannya dalam O(log n) memakai binary heap alih-alih pemindaian O(n), sehingga totalnya menjadi O(n log n).
Kapan memakai selection sort
Pakai sorted() atau list.sort() bawaan di kode Python sungguhan. Selection sort layak diketahui sebagai contoh pembelajaran, untuk array berukuran tetap yang sangat kecil di lingkungan terbatas, dan ketika jumlah penulisan harus minimal. Ini pertanyaan ujian dan wawancara yang sering muncul, biasanya berupa: telusuri langkahnya, hitung perbandingan dan pertukaran, lalu jelaskan mengapa tidak stabil.
FAQ
Apakah selection sort stabil?
Versi array standar yang bekerja di tempat tidak stabil, karena pertukaran jarak jauh bisa memindahkan elemen melewati elemen yang sama. Versi yang menyisipkan alih-alih menukar bersifat stabil tetapi melakukan lebih banyak penulisan.
Berapa kompleksitas waktu selection sort?
O(n²) pada kasus terbaik, rata-rata, dan terburuk. Algoritma ini selalu melakukan n(n − 1)/2 perbandingan, apa pun urutan inputnya.
Berapa banyak pertukaran yang dilakukan selection sort?
Paling banyak n − 1, satu per langkah luar. Ini lebih sedikit daripada bubble sort atau insertion sort, yang bisa melakukan O(n²) pertukaran atau pergeseran.
Apa perbedaan selection sort dan insertion sort?
Selection sort memilih nilai minimum dari bagian belum terurut dan menambahkannya ke bagian terurut. Insertion sort mengambil elemen berikutnya dan menyisipkannya ke tempat yang tepat di bagian terurut. Insertion sort stabil dan punya kasus terbaik O(n); selection sort tidak keduanya.