Informatik :: JavaScript :: Sortieralgorithmen

Sortieralgorithmen

[Allgemeines] [SelectSort] [BubbleSort] [Aufgaben]

Allgemeines

Es gibt sehr viele Sortierverfahren, die unterschiedlich effizient arbeiten.

Einige Sortierverfahren benötigen neben dem zur Speicherung des Arrays nötigen noch weiteren Speicherplatz.

Komplexität und Speicherbedarf hängen bei einigen Sortierverfahren von der anfänglichen Anordnung der Werte im Array ab, man unterscheidet dann zwischen Best Case (bester Fall), Average Case (Durchschnittsverhalten) und Worst Case (schlechtester Fall).

Die wichtigsten Sortieralgorithmen seien hier nur genannt:
Binary Tree Sort, Bubblesort, Countingsort, Cocktailsort, Gnomesort, Heapsort, Insertionsort, Introsort, Mergesort, Quicksort, Selectionsort, Shellsort, Slowsort, Smoothsort, Radixsort, Stoogesort

Die beiden einfachsten Sortierverfahren wollen wir hier kennenlernen.


Seitenanfang

SelectSort

Prinzip:

aufsteigend / absteigend

Beispiel:

Die Zahlen 5, 3, 6, 1 und 4 sollen aufgesteigend sortiert werden.

Vergleich des 1. Elementes mit den folgenden
5 3 6 1 4 Tausch
3 5 6 1 4 kein Tausch
3 5 6 1 4 Tausch
1 5 6 3 4 kein Tausch
Vergleich des 2. Elementes mit den folgenden
1 5 6 3 4 kein Tausch
1 5 6 3 4 Tausch
1 3 6 5 4 kein Tausch
Vergleich des 3. Elementes mit den folgenden
1 3 6 5 4 Tausch
1 3 5 6 4 Tausch
Vergleich des 4. Elementes mit dem 5.
1 3 4 6 5 Tausch
Das Array ist jetzt fertig sortiert
1 3 4 5 6

Struktogramm / Syntax:

 

for (i = 0; i < anzahl-1; i++)
{
  for (j = i + 1; j < anzahl; j++)
  {
   if (zahl[j] < zahl[i]) //absteigend
   {
    //-----Tausch-----
    h = zahl[i];
    zahl[i] = zahl[j];
    zahl[j] = h;
   }
  }
}

Beispiel: Aufsteigendes Sortieren von 50 Zahlen im Feld zahl[50]

 

for (i = 0; i <= 48; i++)
{
  for (j = i + 1; j <= 49; j++)
  {
   if (zahl[i] > zahl[j])
   {
    //-----Tausch-----
    h = zahl[i];
    zahl[i] = zahl[j];
    zahl[j] = h;
   }
  }
}


Seitenanfang

BubbleSort

Prinzip:

Der Algorithmus vergleicht der Reihe nach zwei benachbarte Elemente und
vertauscht sie, falls sie in der falschen Reihenfolge vorliegen.
Dieser Vorgang wird solange wiederholt, bis keine Vertauschungen mehr nötig sind. Hierzu sind in der Regel mehrere Durchläufe erforderlich.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt, an das Ende der Reihe.

Der BubbleSort-Algorithmus eignet sich vor allen bei vorsortierten Datenreihen.

Beispiel:

Die Zahlen 5, 3, 6, 1 und 4 sollen aufgesteigend sortiert werden.

1. Durchlauf
5 3 6 1 4 Tausch
3 5 6 1 4 kein Tausch
3 5 6 1 4 Tausch
3 5 1 6 4 Tausch
2. Durchlauf
3 5 1 4 6 kein Tausch
3 5 1 4 6 Tausch
3 1 5 4 6 Tausch
3. Durchlauf
3 1 4 5 6 Tausch
1 3 4 5 6 kein Tausch
4. Durchlauf
1 3 4 5 6 kein Tausch
Das Array ist jetzt fertig sortiert
1 3 4 5 6

Struktogramm / Syntax:

 

n = anzahl;
do
{
  vertauscht = false;
  for (i = 0; i < n-1; i++)
  {
    if (zahl[i+1] < zahl[i+1])
    {
      //-----Tausch-----
      h = zahl[i];
      zahl[i] = zahl[i + 1];
      zahl[i + 1] = h;
      vertauscht = true;
    }
  }
  n--;
}
while (vertauscht == true);

Beispiel: Aufsteigendes Sortieren von 50 Zahlen im Feld zahl[50]

 

n = 50;
do
{
  vertauscht = false;
  for (i = 0; i < n-1; i++)
  {
    if (zahl[i+1] < zahl[i+1])
    {
      //-----Tausch-----
      h = zahl[i];
      zahl[i] = zahl[i + 1];
      zahl[i + 1] = h;
      vertauscht = true;
    }
  }
  n--;
}
while (vertauscht == true);


Seitenanfang

Aufgaben

  1. SelectSort
  2. BubbleSort
  3. Vergleich von Select- und BubbleSort