Bubble sort ja insertion sort
Koodatkaa molemmat kvadraattiset lajittelualgoritmit, ymmärtäkää, miksi niiden aikavaativuus on O(n²), ja tunnistakaa tilanne, jossa insertion sort päihittää merge sortin.
Bubble sort ja insertion sort on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Miksi O(n²)-lajittelua kannattaa opiskella
Kuplalajittelu ja lisäyslajittelu ovat pahimmassa tapauksessa O(n²), joten ne eivät sovellu suurille syötteille. Silti jokaisessa vakavasti otettavassa algoritmihaastattelussa odotetaan, että osaatte toteuttaa ja analysoida ne. Ne opettavat perustavanlaatuisia käsitteitä — vertailua, vaihtamista, vakaata lajittelua ja parhaan tapauksen suorituskykyä — joita sovelletaan edistyneemmissä algoritmeissa. Haastattelijat käyttävät niitä testatakseen, osaatteko päätellä silmukkainvariantit ja asymptoottisen merkintätavan perusteista lähtien.
# 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')Kuplalajittelu: maksimi kuplii ylös
Kuplalajittelu käy taulukon toistuvasti läpi ja vaihtaa keskenään vierekkäiset väärässä järjestyksessä olevat alkiot. Jokaisen kokonaisen kierroksen jälkeen suurin lajittelematon alkio kuplii lopulliseen paikkaansa loppuun. n-1 kierroksen jälkeen koko taulukko on lajiteltu. Nimi tulee siitä, että suuremmat alkiot nousevat ylöspäin kuplien tavoin. Kuplalajittelu on yksinkertaisin kuvattava lajittelualgoritmi, mutta sitä käytetään käytännössä harvoin.
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]Kuplalajittelu aikaisella lopetuksella
Optimoidussa kuplalajittelussa käytetään swapped-lippua: jos kokonaisen sisemmän kierroksen aikana ei tehdä yhtään vaihtoa, taulukko on jo lajiteltu ja suoritus lopetetaan. Tämä antaa jo valmiiksi lajitellulle syötteelle parhaan tapauksen O(n) — kuplalajittelun ainoan todellisen edun. Ilman tätä lippua algoritmi tekee aina O(n²) vertailua. Aikainen lopetus on se optimointi, jonka haastattelijat tarkistavat kysyessään kuplalajittelun parannuksista.
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 passKuplalajittelun kompleksisuusanalyysi
Kuplalajittelun ulompi silmukka suoritetaan n-1 kertaa. Sisempi silmukka suoritetaan kullakin kierroksella n-1-i kertaa: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 vertailua. Tästä saadaan keskimääräiseksi ja pahimman tapauksen aikavaativuudeksi O(n²). Aikaisen lopetuksen lipun kanssa parhaan tapauksen aikavaativuus pienenee lajitellulla syötteellä arvoon O(n). Tilavaativuus on O(1) — vain vaihtotoiminto tarvitsee tilapäisen muuttujan. Kuplalajittelu on vakaa: samanarvoiset alkiot säilyttävät keskinäisen järjestyksensä, koska vain aidosti suurempia alkioita vaihdetaan.
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=5Lisäyslajittelu: järjestetyn korttikäden rakentaminen
Lisäyslajittelu jäljittelee korttikäden lajittelua: seuraava kortti eli alkio poimitaan ja lisätään vasemmalla olevien jo lajiteltujen korttien joukkoon oikealle paikalleen. Invarianttina on, että arr[0:i] on aina lajiteltu. Jokaisen uuden alkion kohdalla suurempia alkioita siirretään oikealle tilan tekemiseksi. Tämä paikallaan toimiva, vakaa algoritmi toimii pahimmassa tapauksessa O(n²)-ajassa, mutta parhaan tapauksen aikavaativuus on lähes lajitellulla aineistolla O(n).
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]Lisäyslajittelu vaihe vaiheelta
Jäljitetään lisäyslajittelua taulukolla [3, 1, 4, 2]: i=1, key=1, siirretään 3 oikealle → [1, 3, 4, 2]. i=2, key=4, ei siirtoja → taulukko säilyy muuttumattomana. i=3, key=2, siirretään ensin 4 ja sitten 3 oikealle → [1, 2, 3, 4]. Kutakin alkiota verrataan vasemmalla oleviin alkioihin, kunnes sille löytyy oikea paikka. Sisempi while-silmukka tekee siirrot sijoituksilla (vaihtoja nopeammin, koska kutakin siirtoa kohti tarvitaan yksi sijoitus, kun taas vaihtoon tarvitaan kolme).
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]Lisäyslajittelu lähes lajitellulla aineistolla
Lisäyslajittelun ratkaiseva etu on sen O(n + inversiot) -aikavaativuus. Inversio on pari (i,j), jossa i < j mutta arr[i] > arr[j]. Jos taulukossa on vain muutama inversio, lisäyslajittelu on erittäin nopea — käytännössä joskus lomituslajittelua nopeampi yksinkertaisuutensa ja välimuistiystävällisen käyttömallinsa ansiosta. Pythonin Timsort käyttää lisäyslajittelua pienissä osataulukoissa juuri tästä syystä.
# 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)Vakaus lajittelussa
Lajittelualgoritmi on vakaa, jos samanarvoiset alkiot säilyttävät alkuperäisen keskinäisen järjestyksensä lajittelun jälkeen. Sekä kuplalajittelu että lisäyslajittelu ovat vakaita — ne eivät koskaan vaihda keskenään samanarvoisia alkioita. Vakaudella on merkitystä, kun lajitellaan peräkkäin useiden avainten perusteella: lajitelkaa ensin toissijaisen avaimen mukaan vakaasti ja sitten ensisijaisen avaimen mukaan vakaasti, jotta toissijaisen avaimen järjestys säilyy tasatilanteissa. Myös lomituslajittelu on vakaa; keoslajittelu ja pikalajittelu eivät yleensä ole.
# 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 => stableLisäyslajittelu binäärihaun avulla
Lisäyslajittelun sisempi silmukka etsii oikean paikan ja siirtää alkioita. Paikan voi etsiä binäärihaulla O(log i) -vertailulla, mutta siirrot vievät edelleen O(i) aikaa — joten kokonaisaikavaativuus säilyy muodossa O(n²). Optimointi vähentää vertailujen määrää (mikä on hyödyllistä, jos vertailufunktiot ovat kalliita), mutta ei operaatioiden kokonaismäärää. Tätä binaarista lisäyslajittelua käytetään Timsortissa pienille lohkoille.
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]Kuplalajittelu vai lisäyslajittelu: milloin kumpaakin käytetään
Ilmaiskaa tämä vertailu työhaastattelussa itsevarmasti: lisäyslajittelu on aidosti kuplalajittelua parempi — molempien pahimman tapauksen aikavaativuus on O(n²) ja tilavaativuus O(1), mutta lisäyslajittelu tekee vähemmän kirjoitusoperaatioita (O(n+k) k:lle inversiolle verrattuna kuplalajittelun O(n²):een), on välimuistiystävällisempi ja on käytännöllinen valinta pienillä n:n arvoilla (Timsort käyttää sitä). Kuplalajittelun ainoa todellinen etu on pedagoginen yksinkertaisuus. Tuotantokoodissa käyttäkää aina kielen sisäänrakennettua lajittelua.
# 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]Inversioiden laskeminen mittarina
Taulukon inversioiden määrä on niiden parien (i,j) lukumäärä, joissa i < j mutta arr[i] > arr[j]. Lisäyslajittelu tekee täsmälleen inversioiden lukumäärää vastaavan määrän siirtoja — hyödyllinen oivallus. Inversioiden tehokas laskeminen (O(n log n)) edellyttää muunneltua lomituslajittelua. Haastattelijat kysyvät toisinaan lajittelua käsitellessä jatkokysymyksenä: kuinka hyvin algoritmisi ottaa inversiot huomioon?
# 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 invertedPikatarkistus
Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteistä.
Oppitunnin kertaus
Tässä oppitunnissa opitte: kuplalajittelu tekee n-1 kierrosta, joista jokaisella kulloinenkin maksimi kuplii lopulliseen paikkaansa; pahimman tapauksen aikavaativuus on O(n²), mutta aikaisen lopetuksen lipun avulla parhaan tapauksen aikavaativuus on O(n), lisäyslajittelu siirtää alkioita oikealle sijoittaakseen kulloisenkin avaimen oikeaan lajiteltuun paikkaan, ja sen aikavaativuus on O(n + inversioiden määrä), mikä tekee siitä optimaalisen lähes lajitellulle aineistolle ja molemmat algoritmit ovat vakaita, käyttävät O(1) tilaa ja toimivat pahimmassa tapauksessa O(n²)-ajassa — mutta lisäyslajittelu on käytännössä aina kuplalajittelua suositeltavampi. Seuraavaksi toteutamme lomituslajittelun alusta alkaen.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Bubble sort ja insertion sort” ilmainen?
Kyllä – oppitunnin ”Bubble sort ja insertion sort” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Bubble sort ja insertion sort”?
Koodatkaa molemmat kvadraattiset lajittelualgoritmit, ymmärtäkää, miksi niiden aikavaativuus on O(n²), ja tunnistakaa tilanne, jossa insertion sort päihittää merge sortin. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Bubble sort ja insertion sort”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Bubble sort ja insertion sort
- Merge sort: jaa, lajittele, yhdistä
- Quick sort ja pivotin valinta
- Vertailusta riippumattomat lajittelut ja Pythonin sort()