The unit purpose of the quicksort is given below. Code is self explanatory and sufficiently commented. So, we have two pointers and a pivot value. Left pointer makes sure it has crossed smaller values, while the right makes sure, it has crossed larger value than the pivot. When the left pointer points to a larger value and the right pointer points to a smaller value, they swap their values. And at last, the pivot is swapped at the endpoint of the starting pointer. The partition program should be called recursively in the left and right sub arrays, to achieve the Quicksort.
public class Partition {
public static void main (String[] args) {
int toSort[] = {32,3,3,45,67,98,89,102,35,45,21,5};
Partition part = new Partition();
part.partitionIt(toSort);
for(int i = 0; i < (toSort.length); i++) {
System.out.print(toSort[i] + ", ");
}
}
public void partitionIt(int[] numbers) {
//Let us choose the first value as pivot
int pivot = numbers[0];
// Start after the pivot
int startptr = 1;
// Start from the endpoint
int endptr = numbers.length - 1;
while (endptr >= startptr) {
// Move right as long as the values are smaller than the pivot
while (numbers[startptr] <= pivot) {
startptr++;
}
// Move left as long as the values are larger than the pivot
while (numbers[endptr] > pivot) {
endptr--;
}
//Stop before the pointers cross each other
if(endptr > startptr) {
swap(numbers, startptr, endptr);
}
}
// Swap the startptr with that of the pivot
swap(numbers, 0, startptr-1);
}
public void swap(int[] numbers, int x, int y) {
numbers[x] = numbers[x] + numbers[y];
numbers[y] = numbers[x] - numbers[y];
numbers[x] = numbers[x] - numbers[y];
}
}
To make it generic, we substitute variables in the place of mere numbers used and insert a quicksort function as shown.
public void quicksort(int[] numbers) {
partitionIt(numbers, 0, numbers.length - 1);
}
public void partitionIt(int[] numbers, int start, int end) {
//Let us choose the first value as pivot
int pivot = numbers[start];
// Start after the pivot
int startptr = start+1;
// Start from the endpoint
int endptr = end;
/**
Function unaltered
**/
// Swap the startptr with that of the pivot
swap(numbers, start, startptr-1);
}
Ok, This does the same partition, but partition the left and right sub array divided by the pivot value in between. For doing that, return the pivot value’s index , so that the left and right sub arrays has its endpoint and startpoint. Add a base case. Also include a condition if the first value is the largest value, otherwise you might end up in ArrayIndexOutOfBound Exception.
public class Partition {
public static void main (String[] args) {
int toSort[] = {1000, 1100, 32, 3, 3, 45, 67, 9008, 809, 102, 35, 415, 670, 45,21,5};
Partition part = new Partition();
part.quicksort(toSort, 0, toSort.length - 1);
for(int i = 0; i < (toSort.length); i++) {
System.out.print(toSort[i] + ", ");
}
}
public void quicksort(int[] numbers, int start, int end) {
// If this condition is not there, stack overflows, remember the 'base case'
if(end <= start) {
return;
}
int pivot = partitionIt(numbers, start, end);
quicksort(numbers, start, pivot -1);
quicksort(numbers, pivot+1, end);
}
public int partitionIt(int[] numbers, int start, int end) {
//Let us choose the first value as pivot
int pivot = numbers[start];
// Start after the pivot
int startptr = start+1;
// Start from the endpoint
int endptr = end;
while (endptr >= startptr) {
// Keep moving right as long as the value is smaller than the pivot
// (startptr <= end) is inserted because, if the first value is the largest, then the startptr keeps on incrementing
while ((startptr <= end) && numbers[startptr] pivot) {
endptr--;
}
//Stop before the pointers cross each other
if(endptr > startptr) {
swap(numbers, startptr, endptr);
}
}
// Swap the startptr with that of the pivot
swap(numbers, start, startptr-1);
return startptr - 1;
}
public void swap(int[] numbers, int x, int y) {
if(numbers[x] == numbers[y]) {
return;
}
numbers[x] = numbers[x] + numbers[y];
numbers[y] = numbers[x] - numbers[y];
numbers[x] = numbers[x] - numbers[y];
}
}
Analyzing Quicksort’s Big O and about space complexity in the next post…..
My 2 Bytes 