Sortowanie bąbelkowe i przez wstawianie
Proste algorytmy sortowania
Sortowanie bąbelkowe i przez wstawianie to bezpłatna lekcja C Academy na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.
Proste algorytmy sortowania
Sortowanie bąbelkowe i sortowanie przez wstawianie to dwa najprostsze algorytmy sortowania przez porównywanie. W najgorszym przypadku oba mają złożoność O(n kwadrat), ale są łatwe do zrozumienia i przydatne dla małych lub prawie posortowanych tablic.
Jak działa sortowanie bąbelkowe
Sortowanie bąbelkowe wielokrotnie przechodzi przez tablicę, zamieniając sąsiednie pary znajdujące się w niewłaściwej kolejności. Po każdym pełnym przejściu największy z pozostałych elementów wypływa na swoją końcową pozycję na końcu tablicy.
Zamiana dwóch liczb całkowitych
Wielokrotnego użytku funkcja pomocnicza do zamiany elementów pozwala zachować przejrzystość kodu sortowania.
#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;
}Implementacja sortowania bąbelkowego
Zagnieżdżone pętle: pętla zewnętrzna zlicza przejścia, a wewnętrzna porównuje sąsiednie pary i zamienia je miejscami. Po przejściu i ostatnie i elementów jest posortowanych.
#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;
}Optymalizacja z wczesnym zakończeniem
Jeśli podczas pełnego przejścia nie wykonano żadnej zamiany, tablica jest już posortowana i można zakończyć działanie. Dzięki temu sortowanie bąbelkowe ma złożoność O(n) dla już posortowanych danych.
#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;
}Jak działa sortowanie przez wstawianie
Sortowanie przez wstawianie buduje posortowany obszar na początku tablicy. Dla każdego nowego elementu przesuwa większe posortowane elementy w prawo i umieszcza nowy element na właściwym miejscu, podobnie jak podczas układania kart w dłoni.
Implementacja sortowania przez wstawianie
Pobierz element key = a[i], następnie przesuń każdy większy element z zakresu a[0..i-1] o jedną pozycję w prawo i wstaw key w powstałą lukę.
#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;
}Sortowanie przez wstawianie prawie posortowanych danych
Sortowanie przez wstawianie jest szczególnie skuteczne, gdy tablica jest prawie posortowana: każdy element przesuwa się tylko o kilka pozycji, a złożoność zbliża się do O(n). Dlatego jest używane jako końcowy etap sortowania hybrydowego.
#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;
}Stabilność
Oba algorytmy są stabilne: równe elementy zachowują swój pierwotny względny porządek, ponieważ zamiana lub przesunięcie następuje tylko przy ścisłym porównaniu większe niż. Stabilność ma znaczenie podczas sortowania rekordów według wielu kluczy.
Porównanie złożoności
Oba algorytmy mają średnio i w najgorszym przypadku złożoność O(n kwadrat), ale w praktyce się różnią:
- Bąbelkowe: wiele zamian, rzadko używane w rzeczywistym kodzie
- Przez wstawianie: mniej zapisów, świetne dla małych lub prawie posortowanych tablic
Dzięki optymalizacjom najlepszy przypadek obu algorytmów ma złożoność O(n).
Zliczanie operacji
Policzmy porównania wykonywane przez sortowanie przez wstawianie dla tablicy posortowanej odwrotnie, czyli dla najgorszego przypadku.
#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;
}Szybkie sprawdzenie
Sprawdź swoje rozumienie prostych algorytmów sortowania.
Podsumowanie
Nauczyłeś(-aś) się dwóch prostych algorytmów sortowania o złożoności O(n kwadrat).
- Sortowanie bąbelkowe zamienia sąsiednie pary podczas każdego przejścia
- Sortowanie przez wstawianie przesuwa elementy i wstawia je w posortowanym obszarze z przodu
- Oba algorytmy są stabilne; dzięki optymalizacji oba osiągają O(n) dla posortowanych danych
- Sortowanie przez wstawianie jest praktyczniejszym wyborem dla małych zbiorów danych
Ucz się C dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 39
- Lekcje
- 144
Często zadawane pytania
Czy lekcja „Sortowanie bąbelkowe i przez wstawianie” jest bezpłatna?
Tak — pełny tekst „Sortowanie bąbelkowe i przez wstawianie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Sortowanie bąbelkowe i przez wstawianie”?
Proste algorytmy sortowania Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć C Academy?
Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Sortowanie bąbelkowe i przez wstawianie”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?
Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Sortowanie bąbelkowe i przez wstawianie
- Quicksort
- Mergesort
- Używanie qsort