Pengurutan: gelembung (*bubble*), seleksi, dan sisip
Mengurutkan array
- Pengurutan mengatur ulang array agar item-itemnya berurutan dari yang terkecil hingga terbesar.
- Kita mengurutkan di tempat: kita memindahkan item di dalam array yang sama, tanpa nilai kembalian.
- Tiga metode klasik melakukan ini: pengurutan bubble, insertion, dan selection.
Menukar dua elemen
- Setiap pengurutan perlu menukar dua item. Simpan salah satunya sementara, lalu timpa.
int t = a[i]; a[i] = a[j]; a[j] = t;menukar posisiidanj.- Melupakan variabel sementara akan kehilangan salah satu nilai — selalu simpanlah.
Bubble sort
- Lintasi array dan bandingkan setiap pasangan tetangga:
a[j]dana[j + 1]. - Jika urutannya salah, tukar keduanya. Nilai terbesar "menggelembung" ke akhir.
- Ulangi lintasan hingga seluruh array terurut.
Insertion sort
- Anggap bagian kiri array sudah terurut, dan kembangkan satu item pada saat.
- Ambil item berikutnya sebagai kunci, geser item terurut yang lebih besar ke kanan, lalu letakkan kunci di celah tersebut.
- Inilah cara banyak orang mengurutkan kartu remi di tangan mereka.
#include <stdio.h>
int main(void) {
int a[] = {3, 1, 2};
// one bubble pass: compare neighbours and swap if out of order
for (int j = 0; j < 2; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
printf("%d %d %d\n", a[0], a[1], a[2]); // 1 2 3
return 0;
}
Kesalahan umum
- Bubble, selection, dan insertion sort semuanya O(n²).
- Lacak array kecil secara manual untuk memeriksa pengurutan Anda.
Sekarang Anda coba
- Urutkan naik (terkecil pertama), di tempat, tanpa nilai kembalian.
- Penguji mencoba beberapa array, termasuk negatif dan yang sudah terurut.
- Jangan tulis
main— checker menyediakannya.
Lihat proses pengurutan berjalan
Gelembung / seleksi / sisip semuanya membandingkan dan menukar elemen hingga terurut.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi void swap(int a[], int i, int j) agar menukar item pada indeks i dan j, secara in-place (tanpa pengembalian nilai). Jangan tulis main.
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi void bubble_sort(int a[], int n) agar mengurutkan array secara ascending, secara in-place, menggunakan algoritma bubble sort. Jangan tulis main.
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi void insertion_sort(int a[], int n) agar mengurutkan array secara ascending, secara in-place, menggunakan algoritma insertion sort (ambil setiap item sebagai kunci dan geser item yang lebih besar ke kanan). Jangan tulis main.
Klik Jalankan untuk melihat output di sini.