| |
Quick Sort -- O(n*logn) |
|
|
Subject: Quick Sort -- O(n*logn)
Author: Alex_Raj
In response to: Merge Sort -- O(n*logn)
Posted on: 12/27/2013 02:04:37 AM
/**
* Average case performance: O(nlogn)
* Best case performance: O(nlogn)
* Worst case performance: O(n^2)
*/
public class QuickSort {
/**
* @param a Array of integers which are sorted when returns.
*/
public static void sort(int[] a){
quickSort(a, 0, a.length-1);
}
/**
* @param src Array of integers
* @param first Low index of array
* @param last High index of array
*/
private static void quickSort(int[] a, int first, int last)
{
if(last<=first)
return;
int pivot = a[first];
int pos = first;
for(int k=first+1; k<=last; k++ ){
if(a[k]<pivot){
swap(a, ++pos, k);
}else{
// skip those ordered in nature
}
}
swap(a, first, pos);
// split without pivot
quickSort(a, first, pos-1);
quickSort(a, pos+1, last);
}
private static void swap(int[] a, int j, int k) {
int temp = a[j];
a[j] = a[k];
a[k] = temp;
}
}
>
> On 12/27/2013 02:01:30 AM Alex_Raj wrote:
/**
* Average case performance: O(nlogn)
* Best case performance: O(nlogn)
* Worst case performance: O(nlogn)
*/
public class MergeSort {
/**
* @param a Array of integers which are sorted when returns.
*/
public static void sort(int[] a){
int[] help = new int[a.length];
mergeSort(a, help, 0, a.length);
}
/**
* @param src Array of integers
* @param dest Helper array
* @param low Low index of array
* @param high High index of array
*/
private static void mergeSort(int[] src, int[] dest, int low, int high)
{
int len = high - low;
if(len==1){
dest[low] = src[low];
return;
}
int mid = (low+high)>>>1;
// split
mergeSort(src, dest, low, mid);
mergeSort(src, dest, mid, high);
// merge
int p1 = low;
int p2 = mid;
for(int k=low; k<high; k++){
if(p1<mid&&p2<high){
if(dest[p1]<=dest[p2]){ // '=' for stable
src[k] = dest[p1++];
}else{
src[k] = dest[p2++];
}
}else if(p1<mid){
src[k] = dest[p1++];
}else if(p2<high){
src[k] = dest[p2++];
}
}
// copy back to dest
for(int k=low; k<high; k++){
dest[k] = src[k];
}
}
}
References:
|
|
|
|
