Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
   
  •  
    Biologie
    Themen der Chemie
    Deutsch online artikel
    Englisch / Englische
    Franzosisch
    Geographie
    Geschichte
    Informatik
    Kunst
    Mathematik / Studium
    Musik
    Philosophie
    Physik
    Recht
    Sport
    Wirtschaft & Technik



    Biographie

    Impressum

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
E-Mail - Elektronische Post
Das Suchen in Arrays
Wie ist das Wahlverfahren von ICANN ?
Was ist deterministisches Chaos?
NIS - Network Information Service
Ansätze der Kryptoanalyse
Grundsätzliche Funktionsweise
WAN (Wide Area Network) Weitverkehrsnetz
Die Technik hinter USB und FIREWIRE
Einführung in das Internet:





Datenschutz

Zum selben thema
Netzwerk
Software
Entwicklung
Windows
Programm
Unix
Games
Sicherheit
Disk
Technologie
Bildung
Mp3
Cd
Suche
Grafik
Zahlung
Html
Internet
Hardware
Cpu
Firewall
Speicher
Mail
Banking
Video
Hacker
Design
Sprache
Dvd
Drucker
Elektronisches
Geschichte
Fehler
Website
Linux
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.