Blosenzortéierung

D'Blosenzortéierung (och Bubblesort) ass e stabille vergläichbaséierten Zortéierungsalgorithmus. Beim Zortéiere klammen déi méi grouss Elementer wéi Blosen am Waasser (dohier den Numm) ëmmer weider no uewen, dat heescht, un de Schluss vun der Lëscht. Et ginn och ëmmer zwou Zuele mateneen a „Blose“ vertosch.

An der Praxis gëtt d'Blosenzortéierung kaum agesat, well aner Procedéen e bessert Lafzäitbehuelen hunn. Den Algorithmus spillt allerdéngs an der Léier eng Roll, well en einfach z'erklären an ze noweisen ass. Nach dozou eegent sech den Algorithmus fir Technike wéi schrackweis Optiméierungen, Lafzäit- respektiv Komplexitéits- a Korrektheetsanalysen anzeféieren.

Prinzip

Déi maximal optiméiert Blosenzortéierung an enger Zuelelëscht

Beim Zortéiere gëtt d'Lëscht vu lénks no riets duerchgelaf, sou dacks bis déi ganz Lëscht zortéiert ass. Dobäi gëtt a jiddwer Schrëtt dat aktuellt Element mam rietsen Noper verglach. Wa béid Elementer den Zortéierkrittär verletzen, gi se ausgetosch.

Verschidde Variante vum Algorithmus

Fir d'Duerstellung vum Algorithmus net ze komplizéieren, gëtt am Follgenden als Vergläichsrelatioun $>$ (méi grouss wéi) benotzt. Wéi bei jiddwer vergläichbaséierte Zortéierverfahre kann dësen och duerch eng aner Relatioun ersat ginn, déi eng total Uerdnung definéiert.

Den Algorithmus a senger einfachster Form als Pseudocode:

bubbleSort(Array A)
 for (n=A.size; n>1; n=n-1){
 for (i=0; i<n-1; i=i+1){
 if (A[i] > A[i+1]){
 A.swap(i, i+1)
 } // Schluss vum if
 } // Schluss vun der bannenzeger for-Schleef
 } // Schluss vun der baussenzeger for-Schleef

D'Elementer sinn an enger Rei gespäichert. Déi baussenzeg Schleef mécht schrëttweis déi riets Grenz fir d'Blosephas méi kleng, well no all Zortéierung an der rietser Positioun dat gréisst Element vum jeeweils onzortéierte Reschtelement steet. An der bannenzeger for-Schleef gëtt den nach net zortéierten Deel vum Feld duerchgelaf. Dobäi ginn zwéin Nopeschdaten ausgetosch, wa si an der falscher Reiefolleg stinn a sou den Zortéierkrittär verletzen.

Allerdéngs notzt dës einfachst Variant net d'Proprietéit aus, datt no enger Iteratioun, an där keen Austausch geschitt och am Rescht vun den Iteratioune keen Austausch méi passéiere kann. De follgende Pseudocode berécksiichtegt dat:

bubbleSort2(Array A)
 n = A.size
 do{
 swapped = false
 for (i=0; i<n-1; ++i){
 if (A[i] > A[i+1]){
 A.swap(i, i+1)
 swapped = true
 } // Schluss vum if
 } // Schluss vum for
 n = n-1
 } while (swapped == true)

Déi baussenzeg Schleef duerchleeft déi Donnéeën déi zortéiert ginn, bis keen Ausstausch méi gemaach ka ginn.

Eng weider Optiméierung ass d'Ausnotze vun der Eegenschaft, datt um Ennn vun enger baussenzeger Iteratioun all Elementer riets vun der leschter Tauschpositioun schonn an hirer endgëlteger Positioun stinn:

bubbleSort3(Array A)
 n = A.size
 do{
 newn = 1
 for (i=0; i<n-1; ++i){
 if (A[i] > A[i+1]){
 A.swap(i, i+1)
 newn = i+1
 } // Schluss vum if
 } // Schluss vum for
 n = newn
 } while (n > 1)

Beispill

Eng Rei vu fënnef Zuele soll vu kleng no grouss zortéiert ginn. Déi fett gedréckt Zuele gi jeeweils verglach. Zuelen déi ausgetosch ginn, si blo markéiert.

Déi fett gedréckt Zuele gi jeeweils verglach. Ass déi lénks Zuel méi grouss wéi déi vu riets, sou ginn déi zwou ausgetosch; d'Zuelekoppele si blo markéiert. Am éischten Duerchlaf geet déi gréisst Zuel ganz no riets, déi brauch net méi verglach ze ginn. Am zweeten Duerchlaf braucht sou déi lescht an déi virlescht Positioun net méi verglach ze ginn. → Drëtten Duerchlaf: kee Verglach leschten/virleschten/virvirleschten....

{{{1}}}