Quick Sort
Definition
- Quick-sort is a randomized sorting algorithm based on the divide-and-conquer paradigm:
- Divide: pick a random element x (called pivot) and partition S into
- L elements less than x
- E elements equal x
- G elements greater than x
- Recur: sort L and G
- Conquer: join L, E and G
- Divide: pick a random element x (called pivot) and partition S into
Partion
- We partition an input sequence as follows:
- We remove, in turn, each element y from S and
- We insert y into L, E or G, depending on the result of the comparison with the pivot x
- Each insertion and removal is at the beginning or at the end of a sequence, and hence takes O(1) time
- Thus, the partition step of quick-sort takes O(n) time
Algorithm partition(S, p)
Input sequence S, position p of pivot
Output subsequences L, E, G of the
elements of S less than, equal to,
or greater than the pivot, resp.
L, E, G ← empty sequences
x ← S.remove(p)
while ¬S.isEmpty()
y ← S.remove(S.first())
if y < x
L.insertLast(y)
else if y = x
E.insertLast(y)
else { y > x }
G.insertLast(y)
return L, E, G
Quick-Sort Tree
- An execution of quick-sort is depicted by a binary tree
- Each node represents a recursive call of quick-sort and stores
- Unsorted sequence before the execution and its pivot
- Sorted sequence at the end of the execution
- The root is the initial call
- The leaves are calls on subsequences of size 0 or 1
- Each node represents a recursive call of quick-sort and stores
Worst-case Running Time
- The worst case for quick-sort occurs when the pivot is the unique minimum or maximum element
- One of L and G has size n − 1 and the other has size 0
- The running time is proportional to the sum
- n + (n − 1) + …+ 2 + 1
- Thus, the worst-case running time of quick-sort is O(n2)
Expected Running Time
- Consider a recursive call of quick-sort on a sequence of size s
- Good call: the sizes of L and G are each less than 3s/4
- Bad call: one of L and G has size greater than 3s/4
- A call is good with probability 1/2
- 1/2 of the possible pivots cause good calls:
- Probabilistic Fact: The expected number of coin tosses required in order to get k heads is 2k
- For a node of depth i, we expect
- i/2 ancestors are good calls
- The size of the input sequence for the current call is at most (3/4)i/2n
- Therefore, we have
- For a node of depth 2log4/3n, the expected input size is one
- The expected height of the quick-sort tree is O(log n)
- The amount or work done at the nodes of the same depth is O(n)
- Thus, the expected running time of quick-sort is O(n log n)
In-Place Quick-Sort
- Quick-sort can be implemented to run in-place
- In the partition step, we use replace operations to rearrange the elements of the input sequence such that
- the elements less than the pivot have rank less than h
- the elements equal to the pivot have rank between h and k
- the elements greater than the pivot have rank greater than k
- The recursive calls consider
- elements with rank less than h
- elements with rank greater than k
Algorithm inPlaceQuickSort(S, l, r)
Input sequence S, ranks l and r
Output sequence S with the elements of rank between l and r rearranged in increasing order
if l ≥ r
return
i ← a random integer between l and r
x ← S.elemAtRank(i)
(h, k) ← inPlacePartition(x)
inPlaceQuickSort(S, l, h − 1)
inPlaceQuickSort(S, k + 1, r)
In-Place Partitioning
Perform the partition using two indices to split S into L and E U G (a similar method can split E U G into E and G).
Repeat until j and k cross:
- Scan j to the right until finding an element > x.
- Scan k to the left until finding an element < x.
- Swap elements at indices j and k
Code
package examples;
import java.lang.management.ManagementFactory;
import java.lang.management.ThreadMXBean;
import java.util.ArrayList;
import java.util.Random;
/**
* @author ps
* Various sort programs for int arrays
*/
public class SortTest {
public static long cnt;
static Random rand = new Random();
static int [] b;
/**
* @param a int aray
* @return 'true' if 'a' is sorted
*/
public static boolean sortCheck(int[] a) {
for (int i=0;i<a.length-1;i++){
if (a[i]>a[i+1]) return false;
}
return true;
}
/**
* Wrapper which calls the recursive version of the
* quick sort program
* @param a the int array to be sorted
*/
public static void quickSort(int [] a){
qSort(a,0,a.length-1);
}
/**
* recursive version of quick sort (sorts
* the range a[from..to] of the int array 'a')
* @param a
* @param from
* @param to
*/
private static void qSort(int []a, int from, int to){
if (from >= to) return; // nothing to do if sequence has length 1 or less
int piv = partition(a,from,to);
// now a[to..piv-1] <= a[piv] and
// a[piv+1..to]>=a[piv]
qSort(a,from,piv-1);
qSort(a,piv+1,to);
}
/**
* retuns piv and partitions the
* range a[from..to] such that all of the elements
* in the range a[from..piv-1] are <= a[piv] and
* all elements in the range a[piv+1..to] are >= a[piv]
* @param a
* @param from
* @param to
* @return the position 'piv' of the pivot
*/
private static int partition(int []a, int from, int to){
if (from==to) return from;
swap(a,rand.nextInt(to-from)+from,to); // chooses a random pivot
int pivot = a[to];
int left = from-1;
int right = to;
while (true){
while(a[++left]< pivot); // a[left] is now a candidate to swap
while(a[--right] > pivot && right>from);
if (left >= right) break;
swap(a,left,right);
}
swap(a,left,to);
return left; // return the final position of the pivot (to be changed!)
}
/**
* swap the array elements a[i] and a[k]
* @param a int array
* @param i position in the array 'a'
* @param k position in the array 'a'
*/
static void swap(int [] a, int i, int k){
int tmp=a[i];
a[i]=a[k];
a[k]=tmp;
cnt++;
}
public static void main(String[] args) {
long t1=0,t2=0,te1=0,te2=0,eTime=0,time=0;
int n = 50000000;
// we need a random generator
Random rand=new Random(Integer.MAX_VALUE);
//rand.setSeed(54326346); // initialize always in the same state
ThreadMXBean threadBean = ManagementFactory.getThreadMXBean();
// new array
int [] a = new int[n];
// fill it randomly
for (int i=0;i<a.length ;i++) {
a[i]=rand.nextInt(n);
}
for (int i=0;i<a.length ;i++) {
swap(a,i,rand.nextInt(n-1));
}
cnt=0; // for statistcs reasons
// get Time
te1=System.nanoTime();
t1 = threadBean.getCurrentThreadCpuTime();
quickSort(a);
// System.out.println("heap? "+heapCheck(a));
te2 = System.nanoTime();
t2 = threadBean.getCurrentThreadCpuTime();
time=t2-t1;
eTime=te2-te1;
System.out.println("# elements: "+n);
System.out.println("CPU-Time usage: "+time/1000000.0+" ms");
System.out.println("elapsed time: "+eTime/1e6+" ms");
System.out.println("sorted? "+sortCheck(a));
System.out.println("swap operation needed: "+cnt);
}
}