Pengurutan: seleksi dan sisipan
Mengurutkan array
- Pengurutan berarti menyusun nilai-nilai dalam array secara berurutan, biasanya dari kecil ke besar.
- Pada ujian AP CSA, Anda harus mampu menulis dan melacak dua jenis pengurutan: pengurutan pemilihan (selection sort) dan pengurutan sisipan (insertion sort).
- Anda juga perlu melacak (tetapi tidak menulis) pengurutan ketiga: pengurutan penggabungan (merge sort). Kami membahas ketiganya di sini.
Pengurutan pemilihan: ide
- Jalankan melalui array dari kiri ke kanan.
- Di setiap posisi
i, temukan nilai terkecil di bagian yang masih belum terurut (dariihingga akhir). - Tukar nilai terkecil tersebut ke posisi
i. Sekarang0..isudah terurut. - Ulangi hingga seluruh array tersusun.
public class Sorter {
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i; // index of smallest so far
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j; // found a smaller value
}
}
int temp = a[min]; // swap a[i] and a[min]
a[min] = a[i];
a[i] = temp;
}
}
}
Pengurutan pemilihan: pelacakan
- Mari kita urutkan
{5, 2, 4, 1, 3}. Bagian di sebelah kiri|sudah terurut. - Setiap kali lewat, pilih nilai terkecil dari sisa elemen dan tukar ke depan.
start: [5, 2, 4, 1, 3]
i=0 smallest=1 → swap a[0],a[3]: [1 | 2, 4, 5, 3]
i=1 smallest is already 2 → no move: [1, 2 | 4, 5, 3]
i=2 smallest=3 → swap a[2],a[4]: [1, 2, 3 | 5, 4]
i=3 smallest=4 → swap a[3],a[4]: [1, 2, 3, 4 | 5]
done: [1, 2, 3, 4, 5]
Pengurutan sisipan: ide
- Bayangkan memegang kartu remi dan menambahkan satu kartu sekaligus ke tempat yang tepat.
- Mulai dari indeks
1. Sebut nilai ini sebagai kunci. - Geser nilai-nilai yang lebih besar di sebelah kiri satu langkah ke kanan, hingga kunci muat.
- Tempatkan kunci ke dalam celah. Sekarang semua di sebelah kiri sudah terurut.
public class Sorter {
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i]; // the value to place
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger values right
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key; // drop key into the gap
}
}
}
Pengurutan sisipan: pelacakan
- Urutkan lagi
{5, 2, 4, 1, 3}. Bagian di sebelah kiri|tetap terurut seiring berjalannya proses. - Nilai
keyadalah nilai yang kami sisipkan pada setiap kali lewat (pass).
start: [5, 2, 4, 1, 3]
i=1 key=2 → shift 5 right, place 2: [2, 5 | 4, 1, 3]
i=2 key=4 → shift 5 right, place 4: [2, 4, 5 | 1, 3]
i=3 key=1 → shift 5,4,2 right, place 1: [1, 2, 4, 5 | 3]
i=4 key=3 → shift 5,4 right, place 3: [1, 2, 3, 4, 5]
done: [1, 2, 3, 4, 5]
Pengurutan penggabungan: hanya pelacakan
- Pengurutan penggabungan menggunakan rekursi (pelajaran 15). Anda tidak menulisnya di ujian, tetapi Anda harus melacak-nya.
- Belah array menjadi dua lagi dan lagi, hingga setiap bagian memiliki satu nilai.
- Gabungkan pasangan-pasangan bagian kembali, selalu menjaga agar mereka tetap terurut.
Pengurutan penggabungan: pelacakan
- Satu nilai sudah "terurut". Menggabungkan dua bagian terurut menghasilkan bagian terurut yang lebih besar.
split: [5, 2, 4, 1]
[5, 2] [4, 1]
[5] [2] [4] [1]
merge: [2, 5] [1, 4]
merge: [1, 2, 4, 5]
- Pengurutan pemilihan dan sisipan lambat pada array besar (mereka melakukan sekitar n² langkah).
- Pengurutan penggabungan lebih cepat pada array besar (sekitar n·log n langkah). Itulah sebabnya hal itu penting.
Kesalahan umum
- Pengurutan pemilihan dan sisipan keduanya adalah O(n²).
- Lacak array kecil secara manual untuk memeriksa pengurutan Anda.
Sekarang Anda coba
- Setiap tugas memberikan kerangka metode dengan TODO. Urutkan array di tempat (ubah
aitu sendiri). - Sebuah Harness tersembunyi mengurutkan beberapa array dan memeriksa hasilnya.
- Gunakan Periksa jawaban untuk mengompilasi kode Anda dengan tes yang disediakan dan lihat hasilnya. Jaga antarmuka kelas dan metode yang ditampilkan pada starter.
Urut / sisipan
Pengurutan membandingkan dan menukar hingga daftar tertata.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi selectionSort(int[] a) agar mengurutkan array secara in-place dari kecil ke besar, menggunakan sorting seleksi. Pengecek menguji beberapa array.
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi insertionSort(int[] a) agar mengurutkan array secara in-place dari kecil ke besar, menggunakan sorting sisipan. Pengecek menguji beberapa array.
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi isSorted(int[] a) yang mengembalikan true jika array berada dalam urutan dari kecil ke besar (setiap item adalah <= dari yang berikutnya), atau else false. Array kosong atau item satu dianggap terurut.
Klik Jalankan untuk melihat output di sini.