Boble- og innsettingssortering
Enkle sorteringer
Boble- og innsettingssortering er en gratis leksjon i C Academy på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i C Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i C Academy inneholder totalt 4 leksjoner.
Enkle sorteringsalgoritmer
Boblesortering og innsettingssortering er de to enkleste sammenligningsbaserte sorteringsalgoritmene. Begge har O(n i andre) i verste fall, men er enkle å forstå og nyttige for små eller nesten sorterte tabeller.
Slik fungerer boblesortering
Boblesortering går gjentatte ganger gjennom tabellen og bytter om på tilstøtende par som står i feil rekkefølge. Etter hver full gjennomgang bobler det største gjenværende elementet til sin endelige plass på slutten.
Bytte om på to heltall
En gjenbrukbar hjelpefunksjon for bytting holder sorteringskoden ryddig.
#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;
}Implementering av boblesortering
Nøstede løkker: Den ytre løkken teller gjennomgangene, mens den indre løkken sammenligner tilstøtende par og bytter om på dem. Etter gjennomgang i er de siste i elementene sortert.
#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;
}Optimalisering med tidlig avslutning
Hvis en full gjennomgang ikke utfører noen bytter, er tabellen allerede sortert, og De kan stoppe. Dette gjør boblesortering til O(n) for inndata som allerede er sortert.
#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;
}Slik fungerer innsettingssortering
Innsettingssortering bygger opp et sortert område foran i tabellen. For hvert nytt element flyttes større sorterte elementer mot høyre, og det nye elementet settes inn på riktig plass, omtrent som når De sorterer spillekortene på hånden.
Implementering av innsettingssortering
Ta elementet key = a[i], flytt deretter hvert større element i a[0..i-1] én plass mot høyre, og sett key inn i mellomrommet.
#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;
}Innsettingssortering av nesten sorterte data
Innsettingssortering er svært effektiv når tabellen nesten er sortert: hvert element flyttes bare noen få plasser, slik at ytelsen nærmer seg O(n). Derfor brukes den som et avsluttende trinn i hybride sorteringsalgoritmer.
#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;
}Stabilitet
Begge sorteringsalgoritmene er stabile: Elementer med lik verdi beholder den opprinnelige innbyrdes rekkefølgen, fordi de bare bytter plass eller flyttes ved en streng større-enn-sammenligning. Stabilitet er viktig når poster sorteres etter flere nøkler.
Sammenligning av kompleksitet
Begge har O(n i andre) i gjennomsnitt og i verste fall, men oppfører seg forskjellig i praksis:
- Boblesortering: mange bytter, brukes sjelden i reell kode
- Innsettingssortering: færre skrivninger, svært god for små eller nesten sorterte tabeller
Beste tilfelle for begge med optimaliseringer er O(n).
Telle operasjoner
La oss telle hvor mange sammenligninger innsettingssortering utfører på en tabell sortert i omvendt rekkefølge, som er verste tilfelle.
#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;
}Sjekk forståelsen
Test forståelsen Deres av enkle sorteringsalgoritmer.
Oppsummering
De har lært to enkle sorteringsalgoritmer med O(n i andre).
- Boblesortering bytter tilstøtende par ved hver gjennomgang
- Innsettingssortering flytter elementer og setter dem inn i et sortert område foran
- Begge er stabile, og begge kan nå O(n) for sorterte inndata med optimalisering
- Innsettingssortering er det beste praktiske valget for små datamengder
Lær deg C med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 39
- Leksjoner
- 144
Ofte stilte spørsmål
Er leksjonen «Boble- og innsettingssortering» gratis?
Ja – hele teksten i «Boble- og innsettingssortering» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av C Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i C Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Boble- og innsettingssortering»?
Enkle sorteringer Du øver på C Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med C Academy?
Ingen tidligere erfaring er nødvendig. C Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «Boble- og innsettingssortering»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne C Academy-leksjonen?
Ja. Alle C Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Boble- og innsettingssortering
- Quicksort
- Mergesort
- Bruke qsort