Pengurutan Sederhana · Pelajaran 5 dari 10
Selection sort
8 menit baca · BelajarCode
Selection sort bekerja seperti memilih pemain untuk berbaris dari yang terpendek: cari yang terpendek di antara yang belum berbaris, taruh di depan, lalu ulangi untuk sisanya.
| Langkah | Terkecil dari bagian belum urut | Urutan setelah ditukar |
|---|---|---|
| Awal | 29 10 14 37 13 | |
| 1 | 10 | 10 29 14 37 13 |
| 2 | 13 | 10 13 14 37 29 |
| 3 | 14 | 10 13 14 37 29 |
| 4 | 29 | 10 13 14 29 37 |
Bagian yang dicetak tebal adalah bagian yang sudah urut dan tidak akan berubah lagi.
1def selection_sort(data):2 data = data.copy()3 n = len(data)4 for i in range(n - 1):5 terkecil = i6 for j in range(i + 1, n):7 if data[j] < data[terkecil]:8 terkecil = j9 data[i], data[terkecil] = data[terkecil], data[i]10 return data1112print(selection_sort([29, 10, 14, 37, 13]))[10, 13, 14, 29, 37]
Analisis
- Perbandingan selalu sekitar n²/2, berapa pun keadaan awal datanya, jadi O(n²) untuk semua kasus.
- Penukaran paling banyak n - 1 kali. Ini kelebihannya dibanding bubble sort jika menukar data itu mahal.
- Tidak stabil: penukaran jarak jauh bisa membalik urutan dua data yang nilainya sama.
1siswa = [("Andi", 80), ("Bela", 70), ("Citra", 80), ("Dimas", 60)]23def selection_sort_nilai(data):4 data = data.copy()5 for i in range(len(data) - 1):6 terkecil = i7 for j in range(i + 1, len(data)):8 if data[j][1] < data[terkecil][1]:9 terkecil = j10 data[i], data[terkecil] = data[terkecil], data[i]11 return data1213print(selection_sort_nilai(siswa))[('Dimas', 60), ('Bela', 70), ('Citra', 80), ('Andi', 80)]Andi semula di depan Citra, tetapi setelah diurutkan Citra justru di depan Andi. Itulah yang dimaksud tidak stabil.
Cek pemahaman
Berapa banyak penukaran maksimal yang dilakukan selection sort pada 100 data?
Latihan
Urutkan dari besar ke kecil
Ubah selection_sort supaya mengurutkan dari yang terbesar ke yang terkecil. Uji dengan [29, 10, 14, 37, 13].
Pembahasan
1def selection_sort_turun(data):2 data = data.copy()3 n = len(data)4 for i in range(n - 1):5 terbesar = i6 for j in range(i + 1, n):7 if data[j] > data[terbesar]:8 terbesar = j9 data[i], data[terbesar] = data[terbesar], data[i]10 return data1112print(selection_sort_turun([29, 10, 14, 37, 13]))[37, 29, 14, 13, 10]
Cukup membalik tanda pembanding menjadi > dan mencari yang terbesar.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.