AdViews-Sponsor Werbepartner
WebSite Vermarktung


Navigation-Bar

 
Home
Tutorials
Links
Downloads
Seminare
Impressum


Seminare

 
ePayment
Wissensmanag.
Informationsman.
SmartCards
mCommerce
PKI
ASP


 

BubbleSort

 

BubbleSort zählt zu den Elementaren Sortierverfahren und ist im weitesten Sinne eine Fortentwicklung von InsertionSort.
BubbleSort verfährt nach folgender Methode:

Man durchläuft die Liste a[1]...a[N] der Datensätze und betrachtet dabei je zwei benachbarte Elemente a[i] und a[i+1]. Ist a[i].key > a[i+1].key, so vertauscht man a[i] und a[i+1]. Das Durchlaufen des Arrays wird solange wiederholt, bis keine Elemente mehr vertauscht wurden, das Array also sortiert ist.

 Das Verfahren hat seinen Namen, da größere Elemente wie Luftblasen nach oben/rechts aufsteigen.

 Bsp.:

Feld B =                              15,2,43,17,4,8,47

Nach 1. Durchlauf:               2,15,17,4,8,43,47

Nach 2. Durchlauf:               2,15,4,8,17,43,47

Nach 3. Durchlauf:               2,4,8,15,17,43,47

Keine Vertauschungen mehr bei 4. Durchlauf à Feld Sortiert

 Analyse:

  • WorstCase: Feld ist nach absteigenden Schlüsseln sortiert!

à O(n²)

Warum:  Ist  das Feld absteigend sortiert, so muss das erste Element n Schritte bewegt werden, das zweite Element (n-1), das n. Element 1 Schritt bewegt werden.

à Es sind [n + (n-1) +(n-2) + ... + 1 ]* c = [c*n*(n-1)] / 2  Schritte notwendig.(c=const.)

à [c*n*(n-1)] / 2  Є O(n²)

  • AveragCase O(n²)

  • BestCase O(n)

  • Iterativer Algorithmus

  • In-Place  

 

Skripte Top 5

 
  Bubblesort
  Heapsort
  .htaccess
  Mergesort
  Quicksort


Der Klassiker

 
 
Algorithmen


 

   Home | Tutorials | Links | Downloads | Seminare | Impressum  

All Rights reserved by Greenbutter.de, 2000,2001