Bubblesort: Unterschied zwischen den Versionen

Version vom 7. Juli 2008, 15:47 Uhr

Bubblesort (Sortieren nach Aufsteigen) ist ein einfacher und stabiler Sortieralgorithmus der eine Reihe von Elementen nach der Größe sortiert. Wegen seiner Einfachheit ist dieser Algorithmus, besonders bei Anfängern sehr beliebt, aber in der Fachwelt wird er wegen seiner mangelnden Effizienz als schlechter Sortieralgorithmus bezeichnet.

Prinzip

Der Bubblesort – Algorithmus besteht hauptsächlich aus zwei Vorgehensweisen. Einmal durchläuft er die ganze Reihe und vergleicht zwei Elemente, ob Sie in der richtigen Reihenfolge vorliegen. Wenn das nicht der Fall sein sollte, dann vertauscht er die benachbarten Elemente. Dies wiederholt er solange bis alle Elemente in der richtigen Reihenfolge vorliegen. Wegen seiner Komplexität sollten Sie Bubblesort nur bei kleinen Listen bzw. Felder benutzen. Seine Laufzeit hängt quadratisch von der Anzahl der Elemente ab, sprich der Größenordnung O(n²).

Weitaus bessere Sortieralgorithmen sind zum Beispiel QuickSort oder HeapSort.

Beispiel: An diesem Beispiel wird verdeutlicht wie der Bubblesort Algorithmus funktioniert.

1 4 6 2 6 3

1 2 4 6 6 3

1 2 4 6 3 6

1 2 4 3 6 6

1 2 3 4 6 6

Implementierung in C++

#include <iostream>
#include <ctime>
using namespace std; 

void bubblesort (int *pFeld, int size) {
	for (int i = size-1; i > 0; i--) {
		for (int pos = 0; pos < i; pos++) {
			if (pFeld[pos] > pFeld[pos+1]){
				int temp;
				temp = pFeld[pos];
				pFeld[pos] = pFeld[pos+1];
				pFeld[pos+1] = temp;
			}
		}
	}
}

int main () {
	int count; 
	srand (time(NULL));
	cout << "Wie viel Elemente wollen Sie in der Liste zufällig generieren?";
	cin >> count;
	int *pArray = new int[count];
		for (int i = 0; i < count; i++) {
			pArray[i] = 1 + rand()%15;
		}
		cout <<"\n Elemente in der Liste vorher: "; 
		for (int i = 0; i < count; i++){
			cout << pArray[i] <<" ";
		}
		bubblesort (pArray, count);
		cout <<"\n Elemente in der Liste nach dem Sortieren: ";
		for (int i= 0; i < count; i++){
			cout << pArray[i] <<" ";;
		} 
} 

Der eigentliche Hauptteil dieses Programmes liegt bei der Funktion bubblesort(), das am Anfang des Programmquelltexts implementiert wurde. Der Funktion werden zwei Parameter übergeben. Einmal ein Zeiger auf das Array-Feld und die Anzahl der zu sortierenden Elemente. Der Algorithmus ist in zwei for-Schleifen unterteilt. Die äußerste Schleife durchläuft die zu sortierenden Elemente und das genau n-1 mal. Die innere Schleife überprüft die Elemente und vertauscht Sie, wenn das vordere Element größer ist als das hintere. In der main() Funktion wird der Benutzer aufgefordert die Anzahl der Elemente zu bestimmen, das anschließend in der count Variable gespeichert wird und mit dem new Befehl dynamisch erstellt wird. In der for-Schleife wird jedem Element ein zufällig generierte Zahl zugewiesen und anschließend durch die darauffolgende for-Schleife ausgegeben. Jetzt wird die vorher geschriebene bubblesort() Funktion eingesetzt und aufgerufen. Zum Schluss werden die sortierten Elemente wieder ausgegeben.

Ausgabe des Programmes

Wie viel Elemente wollen Sie in der Liste zufällig generieren?

4

Elemente in der Liste vorher: 13 10 13 3

Elemente in der Liste nach dem Sortieren: 3 10 13 13

Achtung: Die Zahlen in der Liste können sich unterscheiden, weil das zufällig erzeugte Zahlen sind!!