Question

IS there RandomizedQuickSort method in java API? OR we should write its code ourselves? thanks

Was it helpful?

Solution

Unless you know that Arrays.sort() is not going to work for you, I suggest you use that. Otherwise I suggest you test any alternative is as good as it suggests.

I added the following to the source suggested by @org.life.java as well as a shuffle()/sort() methods which should be both randomised and quicksorted.

long runTimeNS = 2 * 1000 * 1000 * 1000L;
for (int i = 0; i < 3; i++) {
    long start = System.nanoTime();
    long r;
    for (r = 1; r < runTimeNS; r++) {
        Arrays.sort(list7.clone());
        if (System.nanoTime() - start > runTimeNS) break;
    }
    long time = System.nanoTime() - start;
    System.out.println("Average Arrays.sort() time " + time / r / 1000 + " us.");

    long start1 = System.nanoTime();
    for (r = 1; r < runTimeNS; r++) {
        List<Integer> list = new ArrayList<Integer>();
        for (int j : list7) list.add(j);
        Collections.shuffle(list);
        Collections.sort(list);
        int[] ints = new int[list.size()];
        for (int j = 0; j < list.size(); j++) ints[j] = list.get(j);
        if (System.nanoTime() - start1 > runTimeNS) break;
    }

    long time1 = System.nanoTime() - start1;
    System.out.println("Average shuffle/sort time " + time1 / r / 1000 + " us.");

    long start2 = System.nanoTime();
    for (r = 1; r < runTimeNS; r++) {
        qrsort(list7.clone());
        if (System.nanoTime() - start2 > runTimeNS) break;
    }

    long time2 = System.nanoTime() - start2;
    System.out.println("Average qrsort() time " + time2 / r / 1000 + " us.");
}

and it prints

Average Arrays.sort() time 477 us.
Average shuffle/sort time 5964 us.
Average qrsort() time 36155 us.
Average Arrays.sort() time 474 us.
Average shuffle/sort time 5894 us.
Average qrsort() time 35078 us.
Average Arrays.sort() time 480 us.
Average shuffle/sort time 6211 us.
Average qrsort() time 34790 us.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top