Bubblesort

aus WB Wiki; freien Wissensdatenbank rund ums Thema Computer
Wechseln zu: Navigation, Suche

Bubblesort 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; in der Fachwelt wird er wegen seiner mangelnden Effizienz als schlechter Sortieralgorithmus bezeichnet.

Seinen Namen bekam Bubblesort, weil sein Erfinder dabei an aufsteigende Luftblasen in Wasser gedacht hat ~ kleine Blasen steigen nur langsam auf, große schneller, und alle gleichzeitig (die Gleichzeitigkeit ist in Bubblesort nicht implementiert).

Prinzip

Der Bubblesort–Algorithmus besteht hauptsächlich aus zwei Vorgehensweisen: 1) Er durchläuft die ganzen Elemente und vergleicht jeweils zwei benachbarte, ob Sie in der richtigen Reihenfolge vorliegen. Wenn das nicht der Fall sein sollte, dann vertauscht er die beiden Elemente. 2) Dies wiederholt er solange, bis alle Elemente in der richtigen Reihenfolge vorliegen (~ bis kein Tausch mehr stattgefunden hat).

Effizienz

Wegen seiner Langsamkeit solle Bubblesort nur bei kleinen Listen bzw. Felder benutzt werden, oder bei sehr geringem verfügbaren Ram. Seine Laufzeit hängt quadratisch von der Anzahl der Elemente ab, sprich der Größenordnung O(n²) (bei vorsortierter Liste O(n)). Weitaus bessere Sortieralgorithmen sind zum Beispiel QuickSort oder HeapSort (beide O(n * log n)) ; bei viel Ram Distribution Counting mit O(n).

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, was anschließend in der count Variable gespeichert wird und mit dem new Befehl dynamisch erstellt wird. In der for-Schleife wird jedem Element eine zufällig generierte Zahl zwischen 1 und 15 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!!