QuickSort in Java
Print This Post
Quick Sort is an optimal comparison sorting algorithm which provides an average O(n lg n) running time and worst case in O(n^2). It is an in-place, adaptive but not stable sorting algorithm. Although its worst running time is up to O(n^2), we can practically achieve the average time by cleverly choosing the pivot. In the following implementation, the pivot is chosen at the middle of the lowest position and the highest one.
Noted that this implementation referenced Introduction to Algorithms, Data Structures & Problem Solving Using Java and Bragaadeesh's blog.
First of all, to achieve a better OO design, I create an abstract for all the sorting algorithms I practiced. This abstract class is pretty straightforward, you instantiate by providing the array you wanted to sort, and the type inside the array needs to implement Comparable or you need to provide a Comparator instead. After instantiation, just call sorter.sort() and retrieve the array by using sorter.getArray(). Here is the code for this class.
/**
* Author: I-Fan Chu
*/
package com.ifanchu.algorithm.sorting;
import java.util.Collection;
import java.util.Comparator;
import java.util.NoSuchElementException;
/**
* An abstract class for sorting algorithms.
*/
public abstract class AbstractSorter<T> {
/**
* Backend array
*/
protected T[] array;
//make non-argument constructor protected to permit inheritance
protected AbstractSorter(){}
//Customized comparator
private Comparator<T> comp;
public AbstractSorter(T[] input, Comparator<T> comp){
array = input;
this.comp = comp;
}
public AbstractSorter(T[] input){
this(input, null);
}
public AbstractSorter(Collection<T> c, Comparator<T> comp){
c.toArray(array);
this.comp = comp;
}
public AbstractSorter(Collection<T> c){
this(c, null);
}
/**
* Check if the array is sorted in ascending order based on the comparator or the type's
* natural order if the comparator is not present.
*
* @return true if the array is in ascending order; false otherwise
* @throws NullPointerException if the array is null
*/
protected boolean isSorted(){
if(array==null)
throw new NullPointerException();
for(int i=0; i<array.length-1; i++){
if(compare(array[i], array[i+1]) > 0)
return false;
}
return true;
}
/**
* This method needs to be implemented by subclasses
*/
public abstract void sort();
/************************************
* Getter and Setter *
***********************************/
public T[] getArray(){
return array;
}
public void setArray(T[] input){
array = input;
}
public Comparator<T> getComp() {
return comp;
}
public void setComp(Comparator<T> comp) {
this.comp = comp;
}
/************************************
* Helper Methods *
***********************************/
/**
* Given two index, swap them
*
* @param index1
* @param index2
* @throws NoSuchElementException If either of the given index is out of range
*/
protected void swap(int index1, int index2){
if(!(checkRange(index1) && checkRange(index2)))
throw new NoSuchElementException();
T temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
/**
* Check if the index is valid
*
* @param index
* @return
*/
protected boolean checkRange(int index){
if(index<0 || index>array.length-1)
return false;
return true;
}
/**
* An internal compare method to perform comparison between two given object,
* if the <i>comp</t> has been specified, based on it; if not, the generic type
* must have implemented <tt>Comparable</tt> and this operations will then be
* performed based on it; otherwise, throw exception.
*
* @param t1 The first element to be compared
* @param t2 The second element to be compared
* @return An integer to indicate the result of comparison between <i>t1</i> and <i>t2</i>.
* If t1>t2, return a positive number; if t1<t2, return a negative number;
* return 0 if they are considered equal.
* @throws IllegalArgumentException If neither the <i>comp</i> has been specified nor the generic
* type did not implement <tt>Comparable</tt>
*/
protected int compare(T t1, T t2){
if(comp != null){
return comp.compare(t1, t2);
}else{
if(t1 instanceof Comparable<?> && t2 instanceof Comparable<?>){
return ((Comparable<T>) t1).compareTo(t2);
}else{
throw new IllegalArgumentException("The generic type must either implement Comparable" +
" or specify a customized Comparator");
}
}
}
}
After having this class, here is the implementation of Quick Sort.
/**
* Author: I-Fan Chu
*/
package com.ifanchu.algorithm.sorting;
import java.util.Collection;
import java.util.Comparator;
/**
* Charateristic Table:
* In-place: true
* Adaptive: true
* Stable: false
*
* Quick sort sorts <i>n</i> numbers of elements in-place, but its worst running time is
* <b>Theta(n^2)</b>. Its expected running time is <b>Theta(n lg n)</b>.
*
* This is a popular sorting algorithm for sorting large input arrays.
* This is a comparison sort, which has a lower bound running time of <b>Omega(n lg n)</b>.
*/
public class QuickSort<T> extends AbstractSorter<T> {
public QuickSort(T[] input){
super(input);
}
public QuickSort(T[] input, Comparator<T> comp){
super(input, comp);
}
public QuickSort(Collection<T> c, Comparator<T> comp){
super(c, comp);
}
public QuickSort(Collection<T> c){
super(c, null);
}
protected boolean isSorted(){
for(int i=0; i<array.length-1; i++){
if(compare(array[i], array[i+1]) > 0)
return false;
}
return true;
}
/* (non-Javadoc)
* @see com.ifanchu.algorithm.sorting.AbstractSorter#sort()
*/
@Override
public void sort() {
quicksort(0, array.length-1);
}
/**
* Quick sort driver
*
* @param lo The lowest position
* @param hi The highest position
*/
private void quicksort(int lo, int hi){
if(hi<=lo) return;
int q = partition(lo, hi);
quicksort(lo, q-1);
quicksort(q, hi);
}
/**
* Get the partition location
*
* @param lo The lowest position
* @param hi The highest position
* @return The partition location
*/
private int partition(int lo, int hi){
int i = lo;
int j = hi;
T pivot = array[(lo+hi)>>1];
while(i<=j){
// find item on lo to swap
while (compare(array[i], pivot)<0)
i++;
// find item on hi to swap
while (compare(array[j], pivot)>0)
j--;
if(i<=j)
swap(i++, j--);
}
return i;
}
}
Please leave comments if there is any mistake or improvement or question. Thank you very much.
Clap
Loading ...