Bubble Sort dan Insertion Sort
Pengurutan sederhana.
Bubble Sort dan Insertion Sort adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.
Pengurutan Sederhana
Pengurutan gelembung dan pengurutan penyisipan adalah dua algoritma pengurutan perbandingan yang paling sederhana. Keduanya memiliki kompleksitas O(n kuadrat) dalam kasus terburuk, tetapi mudah dipahami dan berguna untuk larik kecil atau yang hampir terurut.
Cara Kerja Pengurutan Gelembung
Pengurutan gelembung berulang kali menelusuri larik dan menukar pasangan bersebelahan yang urutannya salah. Setelah setiap lintasan penuh, elemen terbesar yang tersisa menggelembung ke posisi akhirnya di bagian akhir.
Menukar Dua Bilangan Bulat
Fungsi pembantu pertukaran yang dapat digunakan kembali membuat kode pengurutan tetap rapi.
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
int main(void) {
int x = 1, y = 2;
swap(&x, &y);
printf("%d %d\n", x, y);
return 0;
}Implementasi Pengurutan Gelembung
Gunakan perulangan bersarang: perulangan luar menghitung lintasan, sedangkan perulangan dalam membandingkan pasangan bersebelahan dan menukarnya. Setelah lintasan i, i elemen terakhir sudah terurut.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
bubble_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Optimasi Berhenti Lebih Awal
Jika satu lintasan penuh tidak menghasilkan pertukaran, berarti larik sudah terurut dan Anda dapat berhenti. Dengan demikian, pengurutan gelembung memiliki kompleksitas O(n) pada masukan yang sudah terurut.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1;
}
if (!swapped) break;
}
}
int main(void) {
int a[] = {1, 2, 3, 4, 5};
bubble_sort(a, 5);
printf("sorted with early exit\n");
return 0;
}Cara Kerja Pengurutan Penyisipan
Pengurutan penyisipan membangun bagian terurut di depan. Untuk setiap elemen baru, algoritma menggeser elemen terurut yang lebih besar ke kanan dan menempatkan elemen baru pada posisinya, seperti mengurutkan kartu remi di tangan Anda.
Implementasi Pengurutan Penyisipan
Ambil elemen key = a[i], lalu geser setiap elemen yang lebih besar dalam a[0..i-1] satu slot ke kanan, dan sisipkan key ke celah tersebut.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Pengurutan Penyisipan pada Data yang Hampir Terurut
Pengurutan penyisipan sangat efektif ketika larik hampir terurut: setiap elemen hanya berpindah beberapa posisi sehingga kompleksitasnya mendekati O(n). Karena itu, algoritma ini digunakan sebagai langkah akhir dalam pengurutan hibrida.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
}
int main(void) {
int a[] = {1, 2, 4, 3, 5}; /* one out of place */
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Stabilitas
Kedua algoritma ini stabil: elemen yang sama mempertahankan urutan relatif aslinya karena algoritma hanya menukar atau menggeser saat perbandingan benar-benar menunjukkan lebih besar. Stabilitas penting ketika mengurutkan rekaman berdasarkan beberapa kunci.
Perbandingan Kompleksitas
Keduanya memiliki kompleksitas O(n kuadrat) dalam kasus rata-rata dan terburuk, tetapi berbeda dalam praktik:
- Gelembung: banyak pertukaran, jarang digunakan dalam kode nyata
- Penyisipan: lebih sedikit penulisan, sangat baik untuk larik kecil atau yang hampir terurut
Kasus terbaik untuk keduanya dengan optimasi adalah O(n).
Menghitung Operasi
Mari kita hitung perbandingan yang dilakukan pengurutan penyisipan pada larik yang diurutkan terbalik, yaitu kasus terburuk.
#include <stdio.h>
int main(void) {
int a[] = {5, 4, 3, 2, 1};
int n = 5; long cmp = 0;
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
printf("comparisons = %ld\n", cmp);
return 0;
}Pemeriksaan Singkat
Uji pemahaman Anda tentang pengurutan sederhana.
Ringkasan
Anda telah mempelajari dua algoritma pengurutan sederhana O(n kuadrat).
- Pengurutan gelembung menukar pasangan bersebelahan pada setiap lintasan
- Pengurutan penyisipan menggeser elemen dan menyisipkannya ke bagian depan yang terurut
- Keduanya stabil; dengan optimasi, keduanya mencapai O(n) pada masukan terurut
- Pengurutan penyisipan merupakan pilihan praktis yang lebih baik untuk data kecil
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Bubble Sort dan Insertion Sort” gratis?
Ya — teks lengkap “Bubble Sort dan Insertion Sort” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Bubble Sort dan Insertion Sort”?
Pengurutan sederhana. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai C Academy?
Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Bubble Sort dan Insertion Sort” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?
Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Bubble Sort dan Insertion Sort
- Quicksort
- Mergesort
- Menggunakan qsort