{"id":4049,"date":"2024-09-19T13:09:57","date_gmt":"2024-09-19T11:09:57","guid":{"rendered":"https:\/\/www.capri-soft.de\/blog\/?p=4049"},"modified":"2024-09-19T13:11:19","modified_gmt":"2024-09-19T11:11:19","slug":"algorithmen-und-datenstrukturen-der-single-pivot-quicksort-in-java","status":"publish","type":"post","link":"https:\/\/www.capri-soft.de\/blog\/?p=4049","title":{"rendered":"Algorithmen und Datenstrukturen: Der „Randomized Single-Pivot QuickSort“ in Java"},"content":{"rendered":"\n

Der Algorithmus<\/h2>\n\n\n\n

Der QuickSort-Algorithmus ist ein rekursiver Sortieralgorithmus nach dem Teile- und Herrsche-Prinzip. Er ruft sich so lange selber auf, bis alle Array-Elemente auf der linken und rechten Stack-Seite eines Pivot-Elements sortiert sind. Zun\u00e4chst wird die zu sortierende Liste in zwei Teillisten (\u201elinke\u201c und \u201erechte\u201c Teilliste) getrennt. Dazu w\u00e4hlt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die gr\u00f6\u00dfer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, k\u00f6nnen sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.<\/p>\n\n\n\n

Anschlie\u00dfend muss man also noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgef\u00fchrt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so weiter. Diese Selbstaufrufe werden als Rekursion bezeichnet. Wenn eine Teilliste der L\u00e4nge eins oder null auftritt, so ist diese bereits sortiert und es erfolgt der Abbruch der Rekusion.<\/p>\n\n\n\n

Der Prinzip:<\/p>\n\n\n\n

    \n
  1. Auswahl eine zuf\u00e4lligen Pivot-Elements (muss nicht das kleinste Element im Array sein)<\/li>\n\n\n\n
  2. Sortierung aller kleineren Zahlen als das Pivot-Element auf die linke Seite des Stapels\/Stacks<\/li>\n\n\n\n
  3. Sortierung aller gr\u00f6\u00dferen Zahlen als das Pivot-Element auf die rechte Seite des Stapels\/Stacks<\/li>\n\n\n\n
  4. Rekursiver Aufruf f\u00fcr die linke Seite des Stapels\/Stacks bis sich die zwei Left- und Right-Pointer \u00fcberschneiden, weil keine kleinere Zahl mehr gefunden wurde, die links vom Pivot-Element einsortiert werden kann.<\/li>\n\n\n\n
  5. Rekursiver Aufruf f\u00fcr die rechte Seite des Stapels\/Stacks bis sich die zwei Left- und Right-Pointer \u00fcberschneiden, weil keine gr\u00f6\u00dfere Zahl mehr gefunden wurde, die rechts vom Pivot-Element einsortiert werden kann.<\/li>\n<\/ol>\n\n\n
    \npackage AlgoDat;\n \npublic class QuickSort {\n    \/\/ Zu sortierendes Array\n    private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};\n \n    \/\/ H\u00e4lt die Klasse als instanziertes Objekt\n    @SuppressWarnings("unused")\n    private static QuickSort program;\n    private java.util.Random rnd = new java.util.Random();\n \n    \/\/ Hilfsfunktion f\u00fcr das Ausgeben des Arrays\n    public void OutputOfIntArray(int myArray[])\n    {\n        if (myArray != null)\n        {\n            for (int i = 0; i < myArray.length; i++) {\n                if (i > 0) System.out.print(";");\n                System.out.print(myArray[i]);\n            }\n \n            System.out.println();\n        }\n    }\n \n    \/\/ Generiert ein zuf\u00e4lliges Integer-Array der Gr\u00f6\u00dfe size mit Werten zwischen 0 und upperLimit\n    public int[] generateIntegerArrayOfSize(int size, int upperLimit)\n    {       \n        int[] generatedArray = new int[size];\n         \n        for (int i = 0; i < generatedArray.length; i++)\n        {\n            generatedArray[i] = rnd.nextInt(upperLimit);\n        }\n \n        return generatedArray;\n    }\n \n    public void makeQuickSort(int[] arrayToSort, int fromIndex, int toIndex)\n    {\n        \/\/ Rekursionsabbruch\n        if (fromIndex >= toIndex)\n        {\n            return;\n        }\n \n        \/\/ Das Pivot-Element muss beim Teile-Herrsche-Prinzip nicht die kleinste Zahl im Array sein \n        \/\/ und kann willk\u00fcrlich gew\u00e4hlt werden - wie hier das letzte Element des Array\n        int pivot = arrayToSort[toIndex];\n        \/\/ Im Average Case performt der Quicksort aber besser, wenn es zuf\u00e4llig ausgew\u00e4hlt wird\n        \/\/ int pivotIndex = rnd.nextInt(toIndex - fromIndex) + fromIndex;\n        \/\/ int pivot = arrayToSort[pivotIndex];\n \n        \/\/ Diese Pointer beinhalten den Index der Elemente, die miteinander verglichen und ggfs. vertauscht werden, wenn sie kleiner\/gr\u00f6\u00dfer als das Pivot sind.\n        int leftPointer = fromIndex;\n        int rightPointer = toIndex;\n \n        \/\/ Partitioniere, so lange wie sich die Pointer nicht in die Quere kommen\n        while (leftPointer < rightPointer)\n        {\n            \/\/ Verschiebe leftPointer so lange, bis ein Element gefunden wird, was gr\u00f6\u00dfer als das Pivot ist\n            \/\/ (oder wie sich die Pointer nicht \u00fcberschneiden)\n            while (arrayToSort[leftPointer] <= pivot && leftPointer < rightPointer)\n            {\n                leftPointer++;\n            }\n \n            \/\/ Verschiebe rightPointer so lange, bis ein Element gefunden wird, was gr\u00f6\u00dfer als das Pivot ist\n            \/\/ (oder wie sich die Pointer nicht \u00fcberschneiden)\n            while (arrayToSort[rightPointer] >= pivot && leftPointer < rightPointer)\n            {\n                rightPointer--;\n            }\n \n            \/\/ Vertausche die Elemente am Index von leftPointer und rightPointer\n            int swapVar = arrayToSort[leftPointer];\n            arrayToSort[leftPointer] = arrayToSort[rightPointer];\n            arrayToSort[rightPointer] = swapVar;\n        }\n \n        \/\/ Vertausche die Elemente am Array-Index von leftPointer und toIndex\n        int swapVar = arrayToSort[leftPointer];\n        arrayToSort[leftPointer] = arrayToSort[toIndex];\n        arrayToSort[toIndex] = swapVar;\n \n        \/\/ QuickSort f\u00fcr die linke Seite vom Pivot-Element\n        this.makeQuickSort(arrayToSort, fromIndex, leftPointer - 1);\n \n        \/\/ QuickSort f\u00fcr die rechte Seite vom Pivot-Element\n        this.makeQuickSort(arrayToSort, leftPointer + 1, toIndex);\n    }\n \n    \/\/ Konstruktor\n    public QuickSort()\n    {\n        System.out.print("Vorher: ");\n        this.OutputOfIntArray(myArray);\n \n        long startZeit = System.nanoTime();\n \n        \/\/ this.OutputOfIntArray(this.generateIntegerArrayOfSize(1000, 100));\n        this.makeQuickSort(myArray, 0, myArray.length - 1);\n \n        long endZeit = System.nanoTime();\n \n        System.out.print("Nachher: ");\n        this.OutputOfIntArray(myArray);\n \n        System.out.println("Ich habe " + (endZeit - startZeit) + " ns gebraucht.");\n    }\n \n    public static void main(String[] args) \n    {\n        \/\/ Instanziere aus den statischem Programm ein echtes Objekt\n        \/\/ damit nicht alle Methoden und Variablen static sein m\u00fcssen.\n        program = new QuickSort();\n    }\n}\n<\/pre><\/div>\n\n\n
    Ausgabe<\/h2>\n\n\n
    \nVorher: 22;6;2;4;10;3;9;7;5;8;1\nNachher: 1;2;3;4;5;6;7;8;9;10;22\nIch habe 7200 ns gebraucht.\n<\/pre><\/div>\n\n\n
    Komplexit\u00e4t: O-Notation (Ordnung)<\/h2>\n\n\n\n
    Der Quick-Sort hat im Average-Case die Komplexit\u00e4t\u00a0O(n* log(n))<\/strong>\u00a0und im Worst-Case die Komplexit\u00e4t\u00a0O(n\u00b2)<\/strong>.<\/p>\n\n\n\n
    <\/p>\n