Sorting: bubble, selection, and insertion · Pengurutan: gelembung (*bubble*), seleksi, dan sisip
Putting an array in order
- Sorting rearranges an array so the items go from smallest to largest.
- We sort in place: we move items around inside the same array, with no return value.
- Three classic methods do this: bubble, insertion, and selection sort.
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.
Swapping two elements
- Every sort needs to swap two items. Save one in a temporary, then overwrite.
int t = a[i]; a[i] = a[j]; a[j] = t;exchanges positionsiandj.- Forgetting the temporary loses one of the values — always keep it.
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
- Go through the array and compare each pair of neighbours:
a[j]anda[j + 1]. - If they are in the wrong order, swap them. The biggest value "bubbles" to the end.
- Repeat the passes until the whole array is in order.
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
- Treat the left part of the array as already sorted, and grow it one item at a time.
- Take the next item as a key, shift bigger sorted items to the right, then drop the key into the gap.
- This is how many people sort playing cards in their hand.
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;
}
Common mistakes
- Bubble, selection and insertion sort are all O(n²).
- Trace a small array by hand to check your sort.
Kesalahan umum
- Bubble, selection, dan insertion sort semuanya O(n²).
- Lacak array kecil secara manual untuk memeriksa pengurutan Anda.
Now you try
- Sort ascending (smallest first), in place, with no return value.
- The checker tries several arrays, including negatives and an already-sorted one.
- Do not write a
main— the checker provides one.
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.
Watch a sort run · Lihat proses pengurutan berjalan
Bubble / selection / insertion all compare and swap into order. · Gelembung / seleksi / sisip semuanya membandingkan dan menukar elemen hingga terurut.
Complete void swap(int a[], int i, int j) so it exchanges the items at index i and j, in place (no return). Do not write a main. · 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.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Complete void bubble_sort(int a[], int n) so it sorts the array ascending, in place, using bubble sort. Do not write a main. · Lengkapi void bubble_sort(int a[], int n) agar mengurutkan array secara ascending, secara in-place, menggunakan algoritma bubble sort. Jangan tulis main.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Complete void insertion_sort(int a[], int n) so it sorts the array ascending, in place, using insertion sort (take each item as a key and shift bigger items right). Do not write a main. · 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.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.