Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
  


informatik artikel (Interpretation und charakterisierung)

Bubble sort


1. Java
2. Viren

= Sortieren durch direktes Austauschenr />

Laufzeit:
Bubble Sort benötigt im Durchschnitt und im ungünstigsten Fall ungefähr n²/2 Vergleiche und n²/2 Austauschoperationen.

Funktionsweise:
Hier wird die Datei immer wieder durchlaufen und wenn das maximale Element gefunden wird, wird es mit jedem rechts von ihm stehenden Element getauscht; solange, bis es das rechte Ende des Feldes erreicht hat.




Beschreibung:
1. Durchgang:
In der 1. Zeile wird der 8er mit dem 5er verglichen und da sie nicht in der Reihenfolge stehen, werden sie vertauscht.
In der 2. Zeile wird der 8er mit dem 9er verglichen, da sie in gleicher Reihenfolge stehen, wird kein Tauschvorgang vorgenommen.
In der 3. Zeile wird der 9er mit dem 7er verglichen und vertauscht.
In der 4. Zeile wird der 9er mit dem 1er verglichen und vertauscht.
In der 5. Zeile wird der 9er mit dem 6er verglichen und vertauscht.
In der 6. Zeile wird der 9er mit dem 3er verglichen und vertauscht.
In der 7.Zeile steht nun das größte Element (=9) an letzter Stelle, aber von sortierten Zahlen ist noch keine Rede. Es wird daher noch ein Durchgang benötigt. Es müssen allerdings nur mehr 6 Elemente statt 7 Elemente durchsucht werden.


2. Durchgang:
Beim 2. Durchgang wird ganz genauso vorgegangen wie beim 1., bis wieder das größte Element an letzter bzw. an vorletzter Stelle steht, also vor dem 9er.
Bis jedoch das gesamte Feld sortiert ist, sind noch ein paar Durchgänge notwendig.
Wie man sieht, wandert immer das größte Element nach hinten. Dadurch sind nach jedem Durchgang nur mehr N-1 Elemente zu durchsuchen.
Das ist der große Vorteil des Bubble Sort.

Um den Vergleich der Methoden weiterzuführen, ist es erforderlich, die Kosten von Vergleichs- und Austauschoperationen zu analysieren, ein Faktor, der wiederum von der Größe der Datensätze und Schlüssel abhängt. Wenn zum Beispiel die Datensätze, wie in den obigen Implementationen, aus einem Wort bestehende Schlüssel sind, so dürfte ein Austausch (zwei Zugriffe auf das Feld) etwa doppelt so teuer sein wie ein Vergleich. In einer solchen Situation sind die Laufzeiten von Selection Sort und Insertion Sort grob gesagt, vergleichbar, während Bubble Sort doppelt so viel Zeit benötigt. (Tatsächlich dürfte Bubble Sort unter nahezu allen Umständen halb so schnell sein wie Insertion Sort!) Falls jedoch die Datensätze im Vergleich zu den Schlüsseln groß sind, ist der Selection Sort am besten geeignet.

 
 

Datenschutz
Top Themen / Analyse
indicator E-Mail - Elektronische Post
indicator Das Suchen in Arrays
indicator Wie ist das Wahlverfahren von ICANN ?
indicator Was ist deterministisches Chaos?
indicator NIS - Network Information Service
indicator Ansätze der Kryptoanalyse
indicator Grundsätzliche Funktionsweise
indicator WAN (Wide Area Network) Weitverkehrsnetz
indicator Die Technik hinter USB und FIREWIRE
indicator Einführung in das Internet:


Datenschutz
Zum selben thema
icon Netzwerk
icon Software
icon Entwicklung
icon Windows
icon Programm
icon Unix
icon Games
icon Sicherheit
icon Disk
icon Technologie
icon Bildung
icon Mp3
icon Cd
icon Suche
icon Grafik
icon Zahlung
icon Html
icon Internet
icon Hardware
icon Cpu
icon Firewall
icon Speicher
icon Mail
icon Banking
icon Video
icon Hacker
icon Design
icon Sprache
icon Dvd
icon Drucker
icon Elektronisches
icon Geschichte
icon Fehler
icon Website
icon Linux
icon Computer
A-Z informatik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.
dsolution