Algorithm:Divide & Conquer
1. Phase:Partition O(N) Time
2. Phase: Divide the array in two part Recursively & call partition function until we are run out of array O(nlogn)
Recursive Function Looks Like T(n)=2*T(n/2)+O(n)
Working Code:
public class QuickSort
{
public static int SIZE = 1000000;
public int[] sort(int[] input) {
quickSort(input, 0, input.length-1);
return input;
}
public static void main(String args[]){
int[] a = new int[SIZE];
for(int i=0;i
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
}
//Time taken to sort a million elements : 156 milliseconds
Time Complexity O(nlogn)
Space Complexity O(logn)
Run Here http://ideone.com/clone/ClBCZ
Complexity Analysis ( More Focus on Space )
very Few of us Know & are abale to come up space compelxity of quick sort if asked during the interview isn't it ?
Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that
* in-place partitioning is used. This requires O(1).
* After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(logn) space. Then the other partition is sorted using tail-recursion or iteration.
The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made O(logn) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most O(logn) nested recursive calls, it uses O(logn) space. The worst case makes O(n) nested recursive calls, and so needs O(n) space.
However, if we consider sorting arbitrarily large lists, we have to keep in mind that our variables like left and right can no longer be considered to occupy constant space; it takes O(logn) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires O(log2n) bits of space in the best and average case and O(nlogn) space in the worst case. This isn't too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy O(nlogn) bits of space.
1 comment :
/* quicksort */
#include
#include
typedef int T; /* type of item to be sorted */
typedef int tblIndex; /* type of subscript */
#define compGT(a,b) (a > b)
#define compLT(a,b) (a < b)
void sortByInsertion(T *x, tblIndex lb, tblIndex ub) {
tblIndex i, j;
for (i = lb + 1; i <= ub; i++) {
T t = x[i];
/* shift down until insertion point found */
for (j = i-1; j >= 0 && compGT(x[j], t); j--)
x[j+1] = x[j];
/* insert */
x[j+1] = t;
}
}
tblIndex partition(T *x, tblIndex lb, tblIndex ub) {
/* select a pivot */
double pivot = x[(lb+ub)/2];
/* work from both ends, swapping to keep */
/* values less than pivot to the left, and */
/* values greater than pivot to the right */
tblIndex i = lb - 1;
tblIndex j = ub + 1;
while (1) {
T t;
while (compGT(x[--j], pivot));
while (compLT(x[++i], pivot));
if (i >= j) break;
/* swap x[i], x[t] */
t = x[i];
x[i] = x[j];
x[j] = t;
}
return j;
}
void quickSort(T *x, tblIndex lb, tblIndex ub) {
tblIndex m;
if (lb >= ub) return;
m = partition(x, lb, ub);
quickSort(x, lb, m);
quickSort(x, m + 1, ub);
}
void quickSortImproved(T *x, tblIndex lb, tblIndex ub) {
while (lb < ub) {
tblIndex m;
/* quickly sort short lists */
if (ub - lb <= 50) {
sortByInsertion(x, lb, ub);
return;
}
m = partition(x, lb, ub);
/* eliminate tail recursion and */
/* sort the smallest partition first */
/* to minimize stack requirements */
if (m - lb <= ub - m) {
quickSortImproved(x, lb, m);
lb = m + 1;
} else {
quickSortImproved(x, m + 1, ub);
ub = m;
}
}
}
void fill(T *a, tblIndex lb, tblIndex ub) {
tblIndex i;
srand(1);
for (i = lb; i <= ub; i++) a[i] = rand();
}
int main(int argc, char *argv[]) {
tblIndex maxnum, lb, ub;
T *a;
/* command-line:
*
* qui maxnum
*
* qui 2000
* sorts 2000 records
*
*/
maxnum = atoi(argv[1]);
lb = 0; ub = maxnum - 1;
if ((a = malloc(maxnum * sizeof(T))) == 0) {
fprintf (stderr, "insufficient memory (a)\n");
exit(1);
}
fill(a, lb, ub);
quickSortImproved(a, lb, ub);
return 0;
}
Post a Comment