Apps für Android programmieren leicht gemacht!
Quicksort in Java

Quicksort

Wir hatten bereits über die Methode des Bubble Sort und dessen Algorithmus geschrieben.

Nun wollen wir uns gerne dem Algorithmus des Quicksort widmen. Der Name dieser Methode suggeriert uns bereits, dass diese Vorgehensweise einen Array zu sortieren besonders schnell sein soll. In der Tat ist es schneller einen Quicksort auf einen Array anzuwenden, als einen Bubble Sort.

Aber wozu überhaupt einen Sortieralgorithmus programmieren, wenn es für die meisten Dinge sowieso bereits fertige Funktionen gibt? In dieser Frage steckt bereits die Antwort. Es gibt für die meisten Dinge, wie Arrays Sortieralgorithmen, aber wenn man nun beispielsweise Objekte innerhalb von Arrays sortieren möchte wird dies schwerlich gehen. Somit muss eine eigene Funktion her.

Quicksort an sich wählt ein sogenanntes Pivot-Element. Alles links vom Pivot-Element wird nun angeschaut. Sind die Elemente kleiner oder gleich groß dem Pivot-Element bleiben sie an Ort und Stelle. Sind die Elemente größer dem Pivot-Element werden sie rechts des Pivot-Elements gesetzt.

Nun wiederholt sich das Ganze, nachdem die gesamte Liste in zwei Teile geteilt wurde. Das Pivot-Element steht dabei bereits fest an der Stelle, an die es gehört.

 

Nachfolgend findet ihr den Code zur Sortierung eines Zahlen-Arrays durch Quicksort.

public static void QuickSort(int Array[], int links, int rechts) {
        if (links < rechts) {
            
            int pivot, i, j, temp;
            pivot = Array[rechts];
            i     = links;
            j     = rechts-1;
            
            while(i<=j) {
                if (Array[i] > pivot) {
                    // setze das Element rechts des Pivot-Elements, weil es größer ist
                    temp = Array[i];
                    Array[i] = Array[j];
                    Array[j] = temp;
                    j--;
                } else i++;
            }
            
            temp      = Array[i];
            Array[i]      = Array[rechts];
            Array[rechts] = temp;

            QuickSort(Array,links,i-1);
            QuickSort(Array,i+1,rechts);
        }
    }

//Aufruf über:
int[] unsortierteListe = {0,5,4,6,2,8,1,3,7,9};
QuickSort(unsortierteListe, 0, unsortierteListe.lenght - 1);

Marvin

Ich bin 23 Jahre jung und studiere zurzeit Wirtschaftsinformatik an der Georg-August-Universität in Göttingen. Ich bin ein Mensch, der sich neben der Programmierung noch für tausend andere Dinge interessiert, die mal mehr und mal weniger verrückt sind. Vor allem aber bin ich Feuer und Flamme mit der Programmierung von eigenen kleinen Apps und Programmen, die mein Leben bereichern.

Kommentar hinzufügen

*Pflichtfeld