Der BubbleSort, in seiner einfachsten Form, kann durch eine kleine
Verbesserung in sofern optimiert werden, dass er nach einem Durchlauf
entscheiden kann, ob die Datenmenge bereits in einer sortierten Ordnung
vorliegt. Stellt der Algorithmus, dass er im letzten Durchlauf keine Elemnte
vertauscht hat, so liegt die Menge dann sortiert vor und weitere Durläufe wären
nur überflüssig. In einer Implementierung wird man eine boolsche Variable
halten die zu Begin eines Durchlaufs auf false gesetzt wird. Sobald zwei Elemente
während des Druchlaufs vertauscht werden, wird diese Variable auf true gesetzt.
Nach dem Durchlauf sorgt eine Abfrage der Variable auf false ob der Algorithmus abgebrochen werden kann.
![\begin{listing}{1}
for( i = num - 1; i > 0; i-- )
{
swapped = true;
for( j =...
...1];
data[j-1] = tmp;
}
}
\par if( swapped == false )
break;
} \end{listing}](img15.png)
Nächste Seite
Aufwärts
Vorherige Seite
Inhalt
Nächste Seite: Biderektionaler BubbleSort
Aufwärts: Optimierungen
Vorherige Seite: Optimierungen
Inhalt
2002-05-09
