Quicksort-Algorithmus - zufälliges Pivot wählen

[Zrebna]

Hi!

Ich frage mich, wie man den QuickSort-ALG implementieren kann, indem man für das Pivot-Element ein zufälliges Element wählt,
statt z.B. einfach das erste oder letzte Element eines Arrays als Pivot festzulegen?

So geht es schon mal nicht:

import java.util.Random;

public class QuickSortWithRandomPivot {
    public static void main(String[] args) {
      //  Random ran = new Random();

        int[] array = {34, 45, 12, 34, 23, 18, 38, 17, 43, 51};
   //     int first = ran.nextInt(array.length - 1);
        // first = ran.nextInt(last - first) + first;
        int first = 0;
        int last = array.length-1;

        quickSort(array, first, last);
        for(int i = 0; i < array.length; i++) {
            if(i == array.length - 1) {
                System.out.println(array[i]);
                break;
            }
            System.out.print(array[i] + ", ");
        }
    }

    private static void quickSort(int[] arr, int first, int last) {
        int part = 0; // separation value


        if(first < last) {
            part = PreparePartition(arr, first, last, part);

            quickSort(arr, first, part-1);
            quickSort(arr, part+1, last);
        }
    }

    private static int PreparePartition(int[] arr, int first, int last, int part) {
        Random ran = new Random();
        int pivotIndex = ran.nextInt(arr.length - 1);

        int pivot = arr[pivotIndex];
        part = first-1;


        for(int i = first; i <= last; i++) {
            if(arr[i] <= pivot) {
                part++;
                // swapping
                int temp = arr[part];
                arr[part] = arr[i];
                arr[i] = temp;
            }
        }
        // swapping
        int temp = arr[part];
        arr[part] = arr[first];
        arr[first] = temp;

        return part;
    }
}

Ich weiß nicht, wo ich genau das zufällige Pivot-Element vergeben muss, damit das gesamte Array sortiert wird und nicht nur Teile davon...
Kann Jemand helfen?

Lg
Zrebna

 

[kneitzel]

Wenn Du das Array von first (Parameter) bis last (Parameter) sortieren willst, dann muss das Pivot-Element doch in diesem Bereich liegen.
Du wählst es aber derzeit beliebig aus dem ganzen Array - und das ist natürlich falsch.

Und der Parameter part sieht auch dubios aus, denn egal was du übergibst: Der Wert wird sofort überschrieben ...

 

[Zrebna]

Ja, stimmt - habe es nochmal überarbeitet:

import java.util.Random;

public class QuickSortWithRandomPivot {
    public static void main(String[] args) {
      //  Random ran = new Random();

        int[] array = {34, 45, 12, 34, 23, 18, 38, 17, 43, 51};
   //     int first = ran.nextInt(array.length - 1);
        // first = ran.nextInt(last - first) + first;
        int first = 0;
        int last = array.length-1;

        quickSort(array, first, last);
        for(int i = 0; i < array.length; i++) {
            if(i == array.length - 1) {
                System.out.println(array[i]);
                break;
            }
            System.out.print(array[i] + ", ");
        }
    }

    private static void quickSort(int[] arr, int first, int last) {
        int part = 0; // separation value


        if(first < last) {
            part = preparePartition(arr, first, last, part);

            quickSort(arr, first, part-1);
            quickSort(arr, part+1, last);
        }
    }



    private static int preparePartition(int[] arr, int first, int last, int part) {
        random(arr,first,last);

        int pivot = arr[first];
        part = first-1;


        for(int i = first; i <= last; i++) {
            if(arr[i] <= pivot) {
                part++;
                // swapping
                int temp = arr[part];
                arr[part] = arr[i];
                arr[i] = temp;
            }
        }
        // swapping
        int temp = arr[part];
        arr[part] = arr[first];
        arr[first] = temp;

        return part;
    }

    private static void random(int[] arr, int first, int last) {
        Random ran = new Random();
        int pivot = ran.nextInt(last - first) + first;

        int temp = arr[pivot];
        arr[pivot] = arr[first];
        arr[first] = temp;
    }
}

Passt nun - gucke es mir aber noch im Debugger in Ruhe an, um alles besser nachvollziehen zu können...

 

[kneitzel]

            quickSort(arr, first, part-1);
            quickSort(arr, part+1, last);

Du sortiert also von 0-3 und 5-8? Was ist mit der 4 (part)?

Wäre jetzt so ein Punkt, der mit ins Auge fällt.

 

[Zrebna]

So wie ich es aus der Vorlesung verstanden habe, ist diese "Lücke" quasi der Trennwert, der bereits einsortiert ist...also vorher...

 

[kneitzel]

Sorry für die späte Antwort. Du hast das natürlich richtig verstanden und ich habe mich in dem Punkt vertan. (Sowas passiert leider, wenn man sich nicht regelmäßig mit so einem Thema beschäftigt.)

Und ja: Dein Code passt so. Ich kannte aber in erster Linie eine etwas andere Implementation, bei der mit zwei Zeigern von links und rechts heran gegangen wird.

Was ich noch anpassen würde - was aber kein Fehler ist denn der Code funktioniert auch so:

a) preparePartition benötigt den Parameter part nicht. Den kann man weg löschen und part zu einer lokalen Variable machen.

b) Beim preparePartition würde ich noch anpassen:

1.) part läuft bei links los und nicht bei links-1.
2.) die Schleife läuft bei links+1 los und nicht bei links. (links enthält ja das pivot element.)
3.) Tauschen bei < und nicht bei <= innerhalb der Schleife.

Die Punkte gleichen sich aus, denn du vergleichst das Element bei links mit dem pivot Element (Element bei links). Daher setzt Du part hoch (und das wird dann zu links und tauscht das Element mit sich selbst was nichts verändert und danach wird i hochgezählt.

Durch die Änderung sparst Du Dir aber paar Täusche (und du kommst näher an die Darstellung des Algorithmus auf Wikipedia.

 

[Zrebna]

Sorry für die späte Antwort. Du hast das natürlich richtig verstanden und ich habe mich in dem Punkt vertan. (Sowas passiert leider, wenn man sich nicht regelmäßig mit so einem Thema beschäftigt.)

Und ja: Dein Code passt so. Ich kannte aber in erster Linie eine etwas andere Implementation, bei der mit zwei Zeigern von links und rechts heran gegangen wird.

Was ich noch anpassen würde - was aber kein Fehler ist denn der Code funktioniert auch so:

a) preparePartition benötigt den Parameter part nicht. Den kann man weg löschen und part zu einer lokalen Variable machen.

b) Beim preparePartition würde ich noch anpassen:

1.) part läuft bei links los und nicht bei links-1.
2.) die Schleife läuft bei links+1 los und nicht bei links. (links enthält ja das pivot element.)
3.) Tauschen bei < und nicht bei <= innerhalb der Schleife.

Die Punkte gleichen sich aus, denn du vergleichst das Element bei links mit dem pivot Element (Element bei links). Daher setzt Du part hoch (und das wird dann zu links und tauscht das Element mit sich selbst was nichts verändert und danach wird i hochgezählt.

Durch die Änderung sparst Du Dir aber paar Täusche (und du kommst näher an die Darstellung des Algorithmus auf Wikipedia.

Hi!
Kein Ding und danke fürs Feedback!