Artikel pedia
| Home | Kontakt | Artikel einreichen | Oberseite 50 artikel | Oberseite 50 autors
 
 


Artikel kategorien
Letztes fugte hinzu
    Ms-access

   Instrumentation + schnittstellen

   Pc tuning - volle kraft voraus für ihr system

   Informatorische grundlagen

   Javascript

   Interne sortieralgorithmen - der kern der sache

   Plotter und sonstige drucker

   Frage 20 (rössl priska)

   Internet - programmierung

   Monitore

   Semesterarbeit und spezialgebiet für informatik

   Erörterungs zum thema

   Inhaltsverzeichnis

   Einführung in die entwicklung ganzheitlicher informationssysteme:

   Titel dokument
alle kategorien

  1

  1. Selection Sort (Sortieren durch direktes Auswählen)       Dieser Algorithmus läuft wie folgt ab: Finde zuerst das kleinste Element im Feld und tausche es gegen das an der ersten Stelle befindliche Element aus, finde danach das zweitkleinste Element und tausche es gegen das an zweiter Stelle befindliche Element aus und fahre in dieser Weise fort, bis das gesamte Feld sortiert ist. Diese Methode wird Selection Sort (Sortieren durch direktes Auswählen) genannt, da sie darin besteht, daß wiederholt das kleinste verbliebene Element >>ausgewählt<< wird, wie in Abbildung 1 dargestellt ist.   Das nachfolgende Programm ist eine Implementation dieses Prozesses. Für jedes i von 1 bis N - 1 tauscht es a[i] gegen das kleinste Element in a[i], ..

..., a[N] aus:       void straightselection (int a[ ], int N) { int i, j, min, t; for ( i = 1; i < N; i++ ) { min = i; for ( j = i + 1; j <= N; j++ ) if ( a[j] < a[min] ) min = j; t = a[min]; a[min] = a[i]; a[i] = t; } }       Während der Index i von links nach rechts durch die Datei wandert, befinden sich die Elemente links vom Index auf ihrer entgültigen Position im Feld (und werden nicht wieder berührt), so daß das Feld vollständig sortiert ist, wenn der Index das rechte Ende erreicht.   Vorteil dieser Methode ist, daß jedes Element wirklich höchstens einmal bewegt wird.           i = 1: i = 5: min = 1 6 min = 5 6 8 j = 2 3 4 5 6 7 8 j = 6 7 8 t = 01 t = 16   i = 2: i = 6: min = 2 6 min = 6 j = 3 4 5 6 7 8 j = 7 8 t = 04 t=   i = 3: i = 7: min = 3 4 6 min = 7 8 j = 4 5 6 7 8 j = 8 t= 07 t= 55   i = 4: min = 4 8 j = 5 6 7 8 t = 12                   Abbildung 1 Selection Sort 2.

Insertion Sort (Sortieren durch direktes Einfügen)     Dies ist die Methode, die Menschen oft beim Kartenspielen anwenden, um ihre Karten zu sortieren: Betrachte die Elemente eines nach dem anderen und füge jedes an seinen richtigen Platz zwischen den bereits betrachteten ein (wobei diese sortiert bleiben). Das gerade betrachtete Element wird eingefügt, indem die größeren Elemente einfach um eine Position nach rechts bewegt werden und das Element dann auf dem freigewordenen Platz eingefügt wird, wie Abbildung 2 zeigt.   Dieser Prozeß ist im folgenden Programm implementiert. Für jedes i von 2 bis N werden die Elemente a[1], ...

.., a[i] sortiert, indem a[i] an die entsprechende Stelle in der sortierten Liste von Elementen in a[1], ....

, a[i - 1] gesetzt wird:       void straightinsertion (int a[ ], int N)   { int i, j, v; for ( i = 2; i <= N; i++ ) { v = a[i]; a[0] = v; j = i - 1; while (v < a[j]) { a[j + 1] = a[j]; j--; } a[j+1] = v; } }     Beim Selection Sort sind die Elemente links vom Zeiger i während des Sortierens in einer sortierten Reihenfolge angeordnet, doch sie befinden sich nicht auf ihrer endgültigen Position, da sie möglicherweise bewegt werden müssen, um für später gefundene kleinere Elemente Platz zu machen. Das Feld ist jedoch vollständig sortiert, wenn der Zeiger das rechte Ende erreicht.   Es muß jeoch eine wichtige Einzelheit beachtet werden: Für die meisten Eingaben funktioniert die Prozedur insertion nicht! Die while-Anweisung läuft über das linke Ende des Feldes hinaus, wenn v das kleinste Element im Feld ist. Um Abhilfe zu schaffen, setzen wir einen >>Marken<<-Schlüssel auf a[0], den wir mindestens so klein wählen wie das kleinste Element im Feld. Marken werden gewöhnlich in Situationen wie dieser verwendet, um die Aufnahme eines nahezu im positiv ausfallenden Test (im vorliegenden Falle j > i) in die innere Schleife zu vermeiden.         i = 2: i = 6: v = 07 v = 01 a[0] = 07 a[0] = 01 j = 1 j = 5 4 3 2 1   i = 3: i = 7: v = 23 v = 63 a[0] = 23 a[0] = 63 j = 2 j = 6   i = 4: i = 8: v = 16 v = 12 a[0] = 16 a[0] = 12 j = 3 2 j = 7 6 5 4   i = 5: v = 55 a[0] = 55 j = 4                   Abbildung 2 Insertion Sort 3.


Bubblesort (Sortieren durch direktes Austauschen)     Das Prinzip ist folgendes: Durchlaufe immer wieder das Feld und vertausche jedesmal, wenn es notwendig ist, benachbarte Elemente; wenn bei einem Durchlauf kein Austausch mehr erforderlich ist, ist das Feld sortiert. Eine Implementation des Verfahrens wird nachfolgend angegeben:   void bubblesort (int a[ ], int N) { int i, j, x; for ( i = n; i >= 2; i--) for ( j = 1; j < i; j++) if ( a[j] > a[j+1]) { x = a[j]; a[j] = a[j+1]; a[j+1] = x; } }     Man muß etwas nachdenken, um sich davon zu überzeugen, daß dieser Weg überhaupt zum Ziel führt. Hierzu bemerken wir, daß jedesmal, wenn während des ersten Durchlaufs das maximale Element vorgefunden wird, dieses mit jedem der rechts von ihm befindlichen Elemente vertauscht wird, und dies so lange, bis es die Position am rechten Ende des Feldes erreicht hat. Während des zweiten Durchlaufs wird dann das zweitgrößte Element an die richtige Position bewegt usw. Somit läuft der Bubble Sort wie eine Abart des Selection Sort ab, obwohl viel mehr Aufwand getrieben wird, um jedes Element an die richtige Position zu bringen.             i = 8: i = 4: j = 1 2 3 4 5 6 7 j = 1 2 3 x= 23 55 63 x = 04   i = 7: i = 3: j = 1 2 3 4 5 6 j = 1 2 x = 23 55 x =   i = 6: i = 2: j = 1 2 3 4 5 j = 1 x = 16 23 x =   i = 5: j = 1 2 3 4 x = 07 16                           Abbildung 3 Bubble Sort 4.

Abschätzung           Selection Sort Insertion Sort Bubblesort C min     n - 1     n² - n 2     n² - n 2   C Æ     n² + n - 2 4     n² - n 2     n² - n 2   C max     n² + n - 2 2     n² - n 2     n² - n 2   M min     ( n - 1 ) * 3     3 ( n - 1)   0 M Æ     n² + 9n - 10 4     n ( ln(n) + 0,577... )   3 ( n² - n² ) 4 M max     n² + 5n - 6 2     3 ( n - 1 ) + trunc n² 4   3 ( n² - 1 ) Ordnung     n²     n²   n²

Suchen artikel im kategorien
Schlüsselwort
  
Kategorien
  
  
   Zusammenfassung Der Vorleser

   sachtextanalyse

   interpretation zwist

   Fabel interpretation

   literarische charakteristik

   interpretation bender heimkehr

   felix lateinbuch

   interpretation der taucher von schiller

   textbeschreibung

   charakterisierung eduard selicke
Anmerkungen:

* Name:

* Email:

URL:


* Diskussion: (NO HTML)




| impressum | datenschutz

© Copyright Artikelpedia.com