Implementierung

Ausgehend davon, eine Datenmenge, welche als zusammenhängender Speicher vorliegt, und Elemente des Typs INT beinhaltet, kann eine einfache Implementierung des Algorithmus in C wie im Folgenden aussehen. 'i' ist die Marke, welche von hinten nach vorne rückt und somit den jeweiligen Durchlauf identifiziert, während 'j' die aktuelle Position im aktuellen Durchlauf darstellt. Durch eine Abfrage wird festgestellt, ob die Elemente falsch zu einander positioniert sind. Falls ja, werden diese augenblicklich vertauscht, wozu eine Hilfsvariable benötigt wird. Bei der folgenden Routine wird ihr die Adresse der Datenmenge und die Anzahl der Elemente, die sie beinhaltet, übergeben. Der vollständigkeitshalber sei hier erwaehnt das in C Arrayfelder Null indiziert angesprochen werden, was auch der Grund dafür ist, dass das letzte Element mit 'num - 1' angesprochen wird!

$\begin{listing}{1} void bubble_sort( int * data, int num ) { int i, j, tmp; ... ...{ tmp = data[j]; data[j] = data[j-1]; data[j-1] = tmp; } } } \end{listing}$

Man beachte, dass diese Implementierung die Datenmenge aufsteigend sortiert. Allerdings gestalltet sich das Sortieren der Menge in umgekehrterer Richtung nicht allzu schwierig, da nur das Ändern des Vergleiches notwendig ist.
Statt einem if( data[j] < data[j-1] ) ist lediglich ein if( data[j] > data[j-1] ) zu machen.

Bemerkenswert ist, dass kein Vergleich auf die Gleichheit zweier Elemente notwendig ist und nur zu einer grösseren Anzahl an Tauschoperationen beitragen würde. Falls die Elemente die gleiche Wertigkeit haben liegen sie ja schon in richtiger Ordnung zu einander, da es egal ist ob 10 vor 10 kommt, oder 10 vor 10 ;-).

Nächste Seite Aufwärts Vorherige Seite Inhalt

Nächste Seite: Optimierungen Aufwärts: BubbleSort Vorherige Seite: Laufzeitkomplexität Inhalt

2002-05-09