Sortowanie bąbelkowe i przez wstawianie
Napiszą Państwo oba algorytmy sortowania kwadratowego, zrozumieją, dlaczego mają złożoność O(n²), i poznają przypadek, w którym sortowanie przez wstawianie przewyższa sortowanie przez scalanie.
Sortowanie bąbelkowe i przez wstawianie to bezpłatna lekcja Coding Interview Prep 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Dlaczego warto uczyć się sortowań O(n²)
Sortowanie bąbelkowe i sortowanie przez wstawianie mają złożoność O(n²) w najgorszym przypadku, przez co są niepraktyczne dla dużych danych wejściowych. Mimo to każda poważna rozmowa techniczna dotycząca algorytmów wymaga ich zaimplementowania i przeanalizowania. Algorytmy te uczą podstawowych pojęć — porównywania, zamiany, stabilnego sortowania i zachowania w najlepszym przypadku — które mają zastosowanie w bardziej zaawansowanych algorytmach. Osoby prowadzące rozmowy wykorzystują je do sprawdzania, czy potrafią Państwo od podstaw rozumować o niezmiennikach pętli i notacji asymptotycznej.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')Sortowanie bąbelkowe: przesuwanie maksimum ku górze
Sortowanie bąbelkowe wielokrotnie przegląda tablicę i zamienia sąsiednie elementy, które są w niewłaściwej kolejności. Po każdym pełnym przejściu największy nieposortowany element „wypływa” na swoją końcową pozycję na końcu tablicy. Po n-1 przejściach cała tablica jest posortowana. Nazwa pochodzi od sposobu, w jaki większe elementy unoszą się ku górze niczym bąbelki. Jest to najprostszy do opisania algorytm sortowania, ale w praktyce rzadko się go używa.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]Sortowanie bąbelkowe z wcześniejszym zakończeniem
Zoptymalizowane sortowanie bąbelkowe wykorzystuje flagę swapped: jeśli pełne przejście pętli wewnętrznej nie spowoduje żadnej zamiany, tablica jest już posortowana i można zakończyć działanie wcześniej. Dzięki temu dla już posortowanych danych złożoność w najlepszym przypadku wynosi O(n) — jest to jedyna rzeczywista zaleta sortowania bąbelkowego. Bez tej flagi algorytm zawsze wykonuje O(n²) porównań. To właśnie optymalizację polegającą na wcześniejszym zakończeniu osoby prowadzące rozmowy sprawdzają, pytając o usprawnienia sortowania bąbelkowego.
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passAnaliza złożoności sortowania bąbelkowego
Pętla zewnętrzna sortowania bąbelkowego wykonuje n-1 przejść. Pętla wewnętrzna wykonuje n-1-i iteracji w każdym przejściu: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 porównań. Daje to O(n²) w średnim i najgorszym przypadku. Dzięki fladze wcześniejszego zakończenia złożoność w najlepszym przypadku spada do O(n) dla posortowanych danych. Złożoność pamięciowa wynosi O(1) — do zamiany potrzebna jest tylko jedna tymczasowa zmienna. Sortowanie bąbelkowe jest stabilne: równe elementy zachowują swój względny porządek, ponieważ zamieniamy tylko elementy, z których pierwszy jest ściśle większy od drugiego.
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5Sortowanie przez wstawianie: budowanie uporządkowanej ręki kart
Sortowanie przez wstawianie naśladuje sortowanie kart trzymanych w ręce: należy wziąć kolejną kartę (element) i wstawić ją na właściwe miejsce wśród już posortowanych kart po lewej stronie. Niezmiennik mówi, że arr[0:i] jest zawsze posortowane. Dla każdego nowego elementu większe elementy należy przesunąć w prawo, aby zrobić miejsce. Ten działający w miejscu i stabilny algorytm ma złożoność O(n²) w najgorszym przypadku, ale O(n) w najlepszym przypadku dla danych prawie posortowanych.
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]Sortowanie przez wstawianie krok po kroku
Prześledźmy sortowanie przez wstawianie dla [3, 1, 4, 2]: i=1, key=1, przesuń 3 w prawo → [1, 3, 4, 2]. i=2, key=4, brak przesunięć → bez zmian. i=3, key=2, przesuń najpierw 4, a następnie 3 w prawo → [1, 2, 3, 4]. Każdy element jest porównywany z elementami po lewej stronie, dopóki nie znajdziemy dla niego właściwego miejsca. Wewnętrzna pętla while wykonuje przesunięcia za pomocą przypisań (jest to szybsze niż zamiany, ponieważ jedno przesunięcie wymaga jednego przypisania, a zamiana — trzech).
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]Sortowanie przez wstawianie dla danych prawie posortowanych
Najważniejszą zaletą sortowania przez wstawianie jest złożoność O(n + liczba inwersji). Inwersja to para (i,j), w której i < j, ale arr[i] > arr[j]. W przypadku prawie posortowanych tablic, zawierających tylko kilka inwersji, sortowanie przez wstawianie jest niezwykle szybkie — w praktyce czasami szybsze od sortowania przez scalanie ze względu na prostotę i przyjazny dla pamięci podręcznej sposób dostępu. Pythonowy Timsort korzysta z sortowania przez wstawianie dla małych podtablic właśnie z tego powodu.
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)Stabilność sortowania
Algorytm sortowania jest stabilny, jeśli równe elementy zachowują swój pierwotny względny porządek po sortowaniu. Zarówno sortowanie bąbelkowe, jak i sortowanie przez wstawianie są stabilne — nigdy nie zamieniają równych elementów. Stabilność ma znaczenie podczas sortowania według wielu kluczy: najpierw należy stabilnie sortować według klucza drugorzędnego, a następnie stabilnie według klucza głównego, aby zachować kolejność według klucza drugorzędnego wśród elementów o tych samych wartościach klucza głównego. Stabilne jest również sortowanie przez scalanie; sortowanie przez kopcowanie i sortowanie szybkie na ogół nie są stabilne.
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stableSortowanie przez wstawianie z wyszukiwaniem binarnym
Pętla wewnętrzna sortowania przez wstawianie jednocześnie znajduje właściwe miejsce i przesuwa elementy. Można użyć wyszukiwania binarnego, aby znaleźć tę pozycję w O(log i) porównań, ale przesuwanie nadal zajmuje O(i) czasu — dlatego ogólna złożoność pozostaje O(n²). Ta optymalizacja zmniejsza liczbę porównań (co jest przydatne w przypadku kosztownych funkcji porównujących), ale nie zmniejsza łącznej liczby operacji. Ten „binarny wariant sortowania przez wstawianie” pojawia się w algorytmie Timsort dla małych rozmiarów fragmentów.
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]Sortowanie bąbelkowe a sortowanie przez wstawianie: kiedy stosować
Na rozmowie technicznej warto przedstawić to porównanie z przekonaniem: sortowanie przez wstawianie jest wyraźnie lepsze od sortowania bąbelkowego — oba algorytmy mają złożoność O(n²) w najgorszym przypadku i O(1) pamięci, ale sortowanie przez wstawianie wykonuje mniej zapisów (O(n+k) dla k inwersji w porównaniu z O(n²) dla sortowania bąbelkowego), jest bardziej przyjazne dla pamięci podręcznej i stanowi praktyczny wybór dla małych wartości n (korzysta z niego Timsort). Jedyną rzeczywistą zaletą sortowania bąbelkowego jest jego prostota dydaktyczna. W kodzie produkcyjnym należy zawsze używać wbudowanego sortowania danego języka.
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]Liczenie inwersji jako miara
Liczba inwersji w tablicy jest równa liczbie par (i,j), w których i < j, ale arr[i] > arr[j]. Sortowanie przez wstawianie wykonuje dokładnie tyle przesunięć, ile jest inwersji — to przydatna obserwacja. Efektywne zliczanie inwersji (w czasie O(n log n)) wymaga zmodyfikowanego sortowania przez scalanie. Osoby prowadzące rozmowy techniczne czasami pytają: „w jakim stopniu algorytm uwzględnia inwersje?” jako pytanie dodatkowe podczas omawiania sortowania.
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs invertedSzybki test
Proszę sprawdzić swoje zrozumienie koncepcji Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo: sortowanie bąbelkowe wykonuje n-1 przejść, a w każdym z nich bieżące maksimum trafia na końcową pozycję; ma złożoność O(n²) w najgorszym przypadku, ale O(n) w najlepszym dzięki fladze wcześniejszego zakończenia, sortowanie przez wstawianie przesuwa elementy w prawo, aby wstawić bieżący klucz na właściwą pozycję w posortowanej części; działa w czasie O(n + liczba inwersji), dzięki czemu jest optymalne dla danych prawie posortowanych oraz oba algorytmy są stabilne, wymagają O(1) pamięci i mają złożoność O(n²) w najgorszym przypadku — jednak sortowanie przez wstawianie jest zdecydowanie preferowane przed sortowaniem bąbelkowym we wszystkich praktycznych sytuacjach. W następnej kolejności zaimplementujemy od podstaw sortowanie przez scalanie.
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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Sortowanie bąbelkowe i przez wstawianie”?
Napiszą Państwo oba algorytmy sortowania kwadratowego, zrozumieją, dlaczego mają złożoność O(n²), i poznają przypadek, w którym sortowanie przez wstawianie przewyższa sortowanie przez scalanie. Ćwiczysz Coding Interview Prep 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ąć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep 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 Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep 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
- Sortowanie przez scalanie: podziel, posortuj, scal
- Quick Sort i wybór pivota
- Sortowania nieporównawcze i sort() w Pythonie