HiveBrain v1.2.0
Get Started
← Back to all entries
snippetjavaMinor

Is this quicksort efficient and acceptable?

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thisefficientquicksortandacceptable

Problem

In order to complete one of my assignment I needed to include a quicksort so I was wondering if this is correct and acceptable.

The code:

private ArrayList sort(ArrayList ar, int lo, int hi){
        if (lo  ar, int lo, int hi){
        String pivot = ar.get(lo);
        lo--;
        hi++;
        while (true){
            lo++;
            while (lolo && ar.get(hi).compareTo(pivot) >= 0){
                hi--;
            }
            if (lo<hi){
                swap(ar, lo, hi);
            }else {
                return hi;
            }
        }
    }


The additional swap method:

private ArrayList swap(ArrayList ar, int a, int b){
        String temp = ar.get(a);
        ar.set(a, ar.get(b));
        ar.set(b, temp);
        return ar;
    }


If this is incorrectly done can you please give me some pointers and tell me why. Otherwise I would gladly accept any suggestions you have.

Solution

Those are pure functions that don't access any instance variables. You can therefore make them static.

You could use generics more generically. Your code should work with any List, as long as it supports an efficient .get(i) for arbitrary i. The elements of the list can be any kind of Comparable object.

The .sort() function should have a void return type to avoid giving the false impression that it returns a copy of the original array.

private static , L extends List & RandomAccess>
void sort(L ar, int lo, int hi) {
    if (lo , L extends List & RandomAccess>
int partition(L ar, int lo, int hi){
    E pivot = ar.get(lo);
    lo--;
    hi++;
    while (true){
        lo++;
        while (lolo && ar.get(hi).compareTo(pivot) >= 0){
            hi--;
        }
        if (lo, L extends List & RandomAccess>
void swap(L ar, int a, int b){
    E temp = ar.get(a);
    ar.set(a, ar.get(b));
    ar.set(b, temp);
}

Code Snippets

private static <E extends Comparable<E>, L extends List<E> & RandomAccess>
void sort(L ar, int lo, int hi) {
    if (lo < hi) {
        int splitPoint = partition(ar, lo, hi);
        sort(ar, lo, splitPoint);
        sort(ar, splitPoint +1, hi);
    }
}

private static <E extends Comparable<E>, L extends List<E> & RandomAccess>
int partition(L ar, int lo, int hi){
    E pivot = ar.get(lo);
    lo--;
    hi++;
    while (true){
        lo++;
        while (lo<hi && ar.get(lo).compareTo(pivot) < 0){
            lo++;
        }
        hi--;
        while (hi>lo && ar.get(hi).compareTo(pivot) >= 0){
            hi--;
        }
        if (lo<hi){
            swap(ar, lo, hi);
        }else {
            return hi;
        }
    }
}

private static <E extends Comparable<E>, L extends List<E> & RandomAccess>
void swap(L ar, int a, int b){
    E temp = ar.get(a);
    ar.set(a, ar.get(b));
    ar.set(b, temp);
}

Context

StackExchange Code Review Q#41189, answer score: 4

Revisions (0)

No revisions yet.