Aanpassen — tel het aantal swaps
Leerdoel: je past bubble sort aan zodat hij naast de gesorteerde lijst ook het aantal swaps teruggeeft.
Opdracht
Schrijf bubble_sort_met_swaps(lijst) die twee dingen teruggeeft: de
gesorteerde lijst en het aantal swaps.
bubble_sort_met_swaps([1, 2, 3])→([1, 2, 3], 0)bubble_sort_met_swaps([3, 2, 1])→([1, 2, 3], 3)bubble_sort_met_swaps([3, 1, 4, 1, 5])→([1, 1, 3, 4, 5], 3)
Tip
Zet swaps = 0 vóór de buitenste lus en tel er bij elke swap één bij op.
Aan het eind geef je de lijst en swaps samen terug.
Antwoord
def bubble_sort_met_swaps(lijst):
n = len(lijst)
swaps = 0
for ronde in range(n - 1):
geswapt = False
for i in range(n - 1 - ronde):
if lijst[i] > lijst[i + 1]:
lijst[i], lijst[i + 1] = lijst[i + 1], lijst[i]
geswapt = True
swaps += 1
if not geswapt:
break
return lijst, swaps
Inversies — een wiskundig leuk feitje
Het aantal swaps dat bubble sort doet is precies gelijk aan het aantal
inversies in de lijst: paren (i, j) met i < j waarvoor
lijst[i] > lijst[j].
Neem [3, 1, 2]. Het paar (3, 1) is een inversie, want 3 is groter dan 1.
Het paar (3, 2) ook. Het paar (1, 2) niet, want die staan goed. Twee
inversies, en bubble sort doet er twee swaps over.
Het idee: elke swap herstelt precies één inversie (twee buren die fout stonden). Daarom is het aantal swaps gelijk aan het aantal inversies.
Verifieer dit zelf
Beide getallen zijn gelijk, en dat blijft zo voor elke lijst die je invult.
Door naar bouw zelf.