5.1 Einfache Sortierverfahren

Zielsetzung

Sortieren spielt in der Informatik eine zentrale Rolle – nicht nur aus praktischen Gründen, sondern auch als klassisches Problem der Algorithmentheorie. Immer dann, wenn Daten effizient durchsucht, ausgewertet oder übersichtlich dargestellt werden sollen, ist es hilfreich, sie vorher zu sortieren. Ganz gleich, ob es sich um Zahlen, Namen, Dateien oder Objekte handelt – eine geordnete Struktur ermöglicht oft schnelleren Zugriff und bessere Übersicht.

In diesem Abschnitt lernen Sie einfache Sortierverfahren kennen, die sich gut für kleinere Datenmengen eignen und didaktisch besonders anschaulich sind. Dabei werden grundlegende Prinzipien deutlich, die auch bei komplexeren Sortieralgorithmen eine Rolle spielen: der Vergleich von Elementen, das Tauschen von Positionen und das schrittweise Annähern an die richtige Reihenfolge.

Inhalt dieser Seite

1. In Arrays suchen und finden

In welchem der beiden Arrays können Sie bestimmte Zahlen schneller finden?

Array 1:

Array 2:

2. Die Klasse "Liste"

Es gibt unheimlich viele Sortierverfahren auf der Welt, die man sich unmöglich alle merken kann. Aus dem Schulunterricht kennen sie bestimmt schon die drei einfachsten Verfahren:

• Bubblesort
• Selectionsort
• Insertionsort

Im Leistungskurs wurde vielleicht auch schon der Quicksort behandelt.

Die drei einfachen Sortierverfahren Bubblesort, Selectionsort und Insertionsort wollen wir hier in Java implementieren. Ausgangspunkte für alle drei Verfahren ist zunächst eine Java-Klasse, die wir einfach mal Liste nennen.

Hier ist der kompletten Quelltext dieser Klasse. Am besten kopieren Sie sich den Quelltext in die Zwischenablage und legen dann in einem neuen Projekt eine leere Klasse Liste an.

import java.util.Random;

public class Liste
{
    public static final int MAX = 100; 
    private int[] zahl;     

    public Liste()
    {
        zahl = new int[MAX];  
    }

    public void erzeugen()
    {
        Random zufall = new Random();  
        for (int i = 0; i < MAX; i++)
            zahl[i] = zufall.nextInt(10*MAX)+1;
    }
    
    public void anzeigen()
    {
       for (int i=1; i<=MAX; i++)
       {
          System.out.printf("%6d",zahl[i-1]); 
          if (i % 10 == 0) System.out.println();
       }
    }
}

Die Zahl der Arrayelemente wurde hier als Konstante definiert, erkennbar an dem Schlüsselwort final. Auf das Schlüsselwort static wurde hier verzichtet.