Sortieren

BubbleSort

Das vermutlich bekannteste Sortierverfahren ist BubbleSort. Hier wird in einem Felddurchlauf für je zwei Nachbarelemente geschaut, ob sie sich in der richtigen Reihenfolge befinden. Wenn nicht, so werden sie getauscht (paarweises Tauschen). Auf diese Weise rutscht das größte Element im ersten Durchlauf an die letzte Position, das zweitgrößte Element im zweiten Durchlauf an die vorletzte Position usw. Es ergibt sich insgesamt eine quadratische Laufzeit.

public void doBubbleSort(int[] feld) {

    int hilfe;

    for (int i=feld.length-1; i>=1; i--) {

      for (int j=0; j<=i-1; j++) {

        if (feld[j] > feld[j+1]) {
          hilfe = feld[j];
          feld[j] = feld[j+1];
          feld[j+1] = hilfe;
        }

      }

    }

}

Straight Selection

Beim Sortieren durch Auswahl bzw. Straight Selection wird im ersten Durchlauf das kleinste Element an die 0-te Stelle des Felds, im zweiten Durchlauf das zweitkleinste Element an die 1-te Stelle des Felds usw. gebracht. Bei der Suche nach dem verbleibenden kleinsten Element wird das Restfeld von vorn nach hinten durchlaufen. Es ergibt sich wieder eine quadratische Laufzeit.

public void doStraightSelection(int[] feld) {

    int hilfe;

    for (int i=0; i<feld.length; i++) {

      for (int j=i+1; j<feld.length; j++) {

        if (feld[j]<feld[i]) {
          hilfe = feld[j];
          feld[j] = feld[i];
          feld[i] = hilfe;
        }

      }
    }

}

Straight Insertion

Beim Sortieren durch Einfügen (Straight Insertion) wird nach und nach ein immer größer werdendes sortiertes Teilfeld aufgebaut. Im ersten Schritt ist das Teilfeld, das nur aus dem ersten Element besteht, bereits sortiert. Nun wird das zweite Element mit in das sortierte Teilfeld aufgenommen, d.h. es wird an der passenden Einfügestelle eingefügt. Diese Idee wiederholt sich so lange, bis das gesamte Feld sortiert ist. Auch dieses Verfahren weist wieder quadratische Laufzeit auf.

public void doStraightInsertion(int[] feld) {

    int hilfe;

    for (int i=1; i<feld.length; i++) {

      int j=0;

      while ((j<i) && (feld[j]<feld[i])) {
        j++;
      }

      hilfe = feld[i];

      for (int k=i; k>=j+1; k--) {
        feld[k] = feld[k-1];
      }

      feld[j] = hilfe;

    }

}

Schnelle Sortierverfahren

Es gibt weitere Sortierverfahren, die mit n log n eine Laufzeit aufweisen, die der quadratischen überlegen ist. Stellvertretend sei hier QuickSort genannt, das als rekursives Verfahren im Abschnitt Rekursive Algorithmen vorgestellt wird.

results matching ""

    No results matching ""