Bubble sort og insertion sort
Enkle sorteringsalgoritmer
Bubble sort og insertion sort er en gratis C Academy-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i C Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. C Academy-kurset indeholder 4 lektioner i alt.
Simple sorteringsalgoritmer
Boblesortering og indsættelsessortering er de to enkleste sammenligningsbaserede sorteringsalgoritmer. Begge har O(n i anden) i værste tilfælde, men er lette at forstå og nyttige til små eller næsten sorterede arrays.
Sådan fungerer boblesortering
Boblesortering gennemgår gentagne gange arrayet og bytter tilstødende par, der står i forkert rækkefølge. Efter hver komplet gennemgang bobler det største resterende element til sin endelige plads i slutningen.
Ombytning af to heltal
En genanvendelig ombytningshjælpefunktion holder sorteringskoden overskuelig.
#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 af boblesortering
Næstede løkker: Den ydre løkke tæller gennemgange, og den indre løkke sammenligner tilstødende par og bytter dem. Efter gennemgang i er de sidste i elementer sorterede.
#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;
}Optimering med tidlig afslutning
Hvis en komplet gennemgang ikke foretager nogen ombytninger, er arrayet allerede sorteret, og du kan stoppe. Det giver boblesortering O(n) for allerede sorteret input.
#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;
}Sådan fungerer indsættelsessortering
Indsættelsessortering opbygger et sorteret område forrest. For hvert nyt element flytter den større sorterede elementer mod højre og placerer det nye element på den rigtige plads, ligesom når du sorterer spillekort på hånden.
Implementering af indsættelsessortering
Hent elementet key = a[i], flyt derefter hvert større element i a[0..i-1] én plads mod højre, og indsæt key i mellemrummet.
#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;
}Indsættelsessortering på næsten sorterede data
Indsættelsessortering er særligt effektiv, når arrayet næsten er sorteret: hvert element flyttes kun få pladser, så den nærmer sig O(n). Derfor bruges den som afsluttende trin 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 sorteringsalgoritmer er stabile: Elementer med samme værdi bevarer deres indbyrdes oprindelige rækkefølge, fordi de kun bytter eller flyttes ved en streng større-end-sammenligning. Stabilitet er vigtig, når poster sorteres efter flere nøgler.
Sammenligning af kompleksitet
Begge har O(n i anden) i gennemsnit og i værste tilfælde, men adskiller sig i praksis:
- Boblesortering: mange ombytninger og sjældent brugt i rigtig kode
- Indsættelsessortering: færre skrivninger og fremragende til små eller næsten sorterede arrays
Bedste tilfælde for begge med optimeringer er O(n).
Optælling af operationer
Lad os tælle, hvor mange sammenligninger indsættelsessortering udfører på et omvendt sorteret array, altså det værste tilfælde.
#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;
}Hurtigt tjek
Test din forståelse af simple sorteringsalgoritmer.
Opsummering
Du har lært to simple sorteringsalgoritmer med O(n i anden).
- Boblesortering bytter tilstødende par ved hver gennemgang
- Indsættelsessortering flytter elementer og indsætter dem i en sorteret begyndelse
- Begge er stabile, og begge når O(n) på sorteret input med optimering
- Indsættelsessortering er det bedste praktiske valg til små datamængder
Lær C med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 39
- Lektioner
- 144
Ofte stillede spørgsmål
Er lektionen “Bubble sort og insertion sort” gratis?
Ja — hele teksten til “Bubble sort og insertion sort” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af C Academy-kurset, skal du opgradere til CoddyKit PRO. C Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Bubble sort og insertion sort”?
Enkle sorteringsalgoritmer Du øver dig i C Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på C Academy?
Der kræves ingen tidligere erfaring. C Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “Bubble sort og insertion sort”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne C Academy-lektion?
Ja. Alle C Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Bubble sort og insertion sort
- Quicksort
- Mergesort
- Brug af qsort