Blosenzortéierung

Vu Wikipedia
Wiesselen op: Navigatioun, sichen
Visualiséierung vun der Blosenzortéierung

D'Blosenzortéierung (och Bubblesort) ass e stabile 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- bzw. Komplexitéits- a Korrektheetsanalysen anzeféieren.

Prinzip[änneren | Quelltext änneren]

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éiercritère verletzen, gi se ausgetosch.

Verschidde Variante vum Algorithmus[änneren | Quelltext änneren]

Fir d'Duerstellung vum Algorithmus net ze komplizéieren, gëtt am Folgenden 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 banneschter for-Schläif
 } // Schluss vun der bausseschter for-Schläif

D'Elementer sinn an enger Rei gespäichert. Déi baussescht Schläif 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 banneschter for-Schläif 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éiercritère 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 folgende Pseudocode berücksichtegt 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 Schläif 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 Eegeschaft, 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[änneren | Quelltext änneren]

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 soumat déi lescht an déi virlescht Positioun net méi verglach ze ginn. → Drëtten Duerchlaf: kee Verglach leschten/virleschten/virvirleschten....

55 07 78 12 42   1. Duerchlaf
07 55 78 12 42
07 55 78 12 42
07 55 12 78 42   Leschte Verglach
07 55 12 42 78   2. Duerchlaf
07 55 12 42 78
07 12 55 42 78   Leschte Verglach
07 12 42 55 78   3. Duerchlaf
07 12 42 55 78   Leschte Verglach
07 12 42 55 78   4. Duerchlaf + Leschte Verglach
07 12 42 55 78   Fäerdeg zortéiert.