snippetjavaMinor
Is this quicksort efficient and acceptable?
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:
The additional swap method:
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.
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
You could use generics more generically. Your code should work with any
The
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.