Algoritma Pengurutan
| English | Bahasa Indonesia |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | Pengurutan |
| selection sort/sɪˈlekʃn sɔːt/ | pengurutan seleksi |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | insertion sort |
| in place/ɪn pleɪs/ | in place |
Mengatur sesuatu menjadi tertib
- Pengurutan menyusun ulang elemen menjadi urutan (terkecil ke terbesar, misalnya).
- Kursus AP mencakup dua pengurutan sederhana: selection sort dan insertion sort.
- Keduanya menggunakan loop bersarang dan menukar atau menggeser elemen ke tempatnya.
- Mengurutkan terlebih dahulu adalah hal yang memungkinkan Anda menggunakan pencarian biner yang cepat setelahnya.
Urutan seleksi
- Temukan elemen terkecil yang tersisa dan tukar ke posisi depan.
- Kemudian cari terkecil dari sisa, tukar ke posisi berikutnya, dan seterusnya.
- Bagian depan array menjadi terurut; bagian belakang menyusut tidak terurut.
- Satu pertukaran per lintasan — namun tetap memindai sisanya setiap kali.
Insertion sort
- Ambil elemen berikutnya dan geser ke belakang ke tempat yang benar di antara bagian depan yang sudah terurut.
- Seperti mengurutkan tumpukan kartu: masukkan setiap kartu baru ke posisinya.
- Area terurut bertambah satu setiap kali lintasan.
- Cepat jika data sudah hampir terurut.
Beban kerja
- Kedua urutan menggunakan loop bersarang, sehingga melakukan sekitar
n²perbandingan dalam kasus terburuk. - Itu cukup untuk array kecil tetapi lambat untuk array yang sangat besar.
- Mereka mengurutkan di tempat — tidak perlu array kedua.
- Ujian meminta Anda untuk melacak mereka, bukan sekadar menyebut namanya.
Urutan seleksi TUKAR elemen terkecil yang tersisa ke depan; urutan sisipan MENGGERAKKAN setiap elemen baru ke belakang ke bagian yang terurut — jangan tertukar. Keduanya adalah urutan loop bersarang O(n²) dan keduanya mengurutkan di tempat. Lacak langkah demi langkah (ujian AP meminta state array setelah setiap lintasan), alih-alih menghafal nama.
Urutan seleksi pada [3, 1, 2]:
- Lintasan 1: terkecil adalah
1; tukar ke depan →[1, 3, 2]. - Lintasan 2: terkecil dari
[3, 2]adalah2; tukar →[1, 2, 3]. - Terurut — bagian depan bertambah satu elemen per lintasan.
Mengurutkan mengorderkan elemen. Urutan seleksi berulang kali menukar elemen terkecil yang tersisa ke depan; urutan sisipan menggeser setiap elemen baru ke belakang ke bagian yang terurut. Keduanya adalah loop bersarang, di tempat, urutan O(n²). Mengurutkan memungkinkan pencarian biner cepat afterwards.
Melalui proses pengurutan
Setiap lemparan menempatkan satu elemen lagi secara berurutan.
Selection sort bekerja dengan cara...
Selection sort memilih minimum dan menukarnya ke depan.
Insertion sort bekerja dengan cara...
Insertion sort menyisipkan setiap elemen ke tempat urutannya.
Dalam kasus terburuk, kedua sorting melakukan sekitar...
Perulangan bersarang menghasilkan O(n²).
Kedua selection sort dan insertion sort bekerja in-place (tanpa array kedua).
Mereka mengatur ulang array yang sama.
Urutkan lemparan selection sort pada [3, 1, 2].
Bagian depan tumbuh terurut, satu elemen per lemparan.
Mengurutkan terlebih dahulu berguna karena memungkinkan Anda kemudian menggunakan...
Pencarian biner membutuhkan data terurut.