Quicksort mit Random-Pivot

Java-Forum Allgemeine Themen
1

Hi,

ich hoffe mir kann jemand helfen. Ich habe einen Quicksort-Algorithmus und möchte dort mit einem zufällig generierten Pivotelement sortieren. Jedoch sortiert er mir mein Array immer falsch. Hier ist meine Methode für das Sortieren:



void qsort(int start, int end) {
        int pivot, i, j;        


        if (end > start) {
            i = start;
            j = end - 1;
            pivot = arr[(int) (start + (Math.random() * ((end - start))))].key();


            while (true) {
                while (arr**.key() < pivot)
                {
                    i++;
                }


                while ((j >= 0) && (arr[j].key() >= pivot))
                {
                    j--;
                }


                if (i >= j)
                    break;


                swap(i, j);
            }
            swap(i, end);
            qsort(start, i - 1);
            qsort(i + 1, end);
        }
    }

Ich habe leider keine Ahnung was ich falsch mache. Danke schon mal :).

VG Marco

2

Funktioniert es denn mit einem nicht-random-Pivot? Hab’s jetzt nicht getestet und Uhrzeigbedingt auch nicht „im Kopf compiliert“ :smiley: aber ein allgemeiner Hinweis: Praktisch IMMER, wenn man irgendwas mit Zufall machen will, ist es besser, java.util.Random zu verwenden. Von Math.random würde ich grundsätzlich abraten. Das liefert irgendwelche nicht vorhersehbaren Ergebnisse. Bei java.util.Random kann man einen Seed angeben, so dass man immer die gleichen Zufallszahlen erhält:

private static final Random RANDOM = new Random(0);

....

int index = RANDOM.nextInt(maxValue);

Damit, und mit einem Debugger (oder notfalls ein paar System.out.println’s), sollte man das ganze nachvollziehen können.

Wenn es dann wieder ‚echt‘ zufällig sein soll, verwendet man new Random() statt new Random(0).