Algoritma Pengurutan
Diperkenalkan
13:31
Koleksi Data
Ambil satu foto di ponsel Anda. Bagi komputer, itu bukanlah gambar sama sekali — itu adalah grid angka, satu untuk setiap piksel, sekitar dua belas juta darinya. Sekarang cobalah…
Narasi bahasa Inggris · takarir bahasa Inggris dan 中文 yang dapat dipilih
In this lesson
| English | Makna |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | Pengurutan |
| selection sort/sɪˈlekʃn sɔːt/ | pengurutan pilihan |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | penyisipan |
| 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.

Sortir penyisipan, menggeser setiap kunci ke posisi yang tepat satu per satu lintasan
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...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Selection sort memilih minimum dan menukarnya ke depan.
Insertion sort bekerja dengan cara...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Insertion sort menyisipkan setiap elemen ke tempat urutannya.
Dalam kasus terburuk, kedua sorting melakukan sekitar...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Perulangan bersarang menghasilkan O(n²).
Kedua selection sort dan insertion sort bekerja in-place (tanpa array kedua).
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Mereka mengatur ulang array yang sama.
Urutkan lemparan selection sort pada [3, 1, 2].
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Bagian depan tumbuh terurut, satu elemen per lemparan.
Mengurutkan terlebih dahulu berguna karena memungkinkan Anda kemudian menggunakan...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Pencarian biner membutuhkan data terurut.