Quick Sort 

Quick sort partitions the array into two sections, the first of "small" elements and the second of "large" elements. It then sorts the small and large elements separately. Ideally, partitioning would use the median of the given values, but the median can only be found by scanning the whole array and this would slow the algorithm down. In that case the two partitions would be of equal size; In the simplest versions of quick sort an arbitrary element, typically the first element is used as an estimate (guess) of the median. quicksort(int a[], int lo, int hi) /* sort a[lo..hi] */ { int left, right, median, temp; if( hi > lo ) /* i.e. at least 2 elements, then */ { left=lo; right=hi; median=a[lo]; /* NB. just an estimate! */ while(right >= left) /* partition a[lo..hi] */ /* a[lo..left1]<=median and a[right+1..hi]>=median */ { while(a[left] < median) left++; /* a[left] >= median */ while(a[right] > median) right; /* a[left] >= median >= a[right] */ if(left > right) break; //swap: temp=a[left]; a[left]=a[right]; a[right]=temp; left++; right } /* a[lo..left1]<=median and a[right+1..hi]>=median and left > right */ quicksort(a, lo, right);// divide and conquer quicksort(a, left, hi); } }/*quicksort*/ function quick(a, N) /* sort a[1..N], N.B. 1 to N */ { quicksort(a, 1, N); } Change the data in the HTML FORM below, click `go', and experiment: ComplexityTimeIn the best case, the partitions are of equal size at each recursive call, and there are then log_{2}(N) levels of recursive calls. The whole array is scanned at each level of calls, so the total work done is O(N*log(N)). The average time complexity is also O(N*log(N)). The worst case time complexity is O(N^{2}). This occurs when the estimate of the median is systematically always poor, e.g. on already sorted data, but this is very unlikely to happen by chance. SpaceAs coded above the best and averagecase spacecomplexity is O(log(N)), for the stackspace used. The worstcase spacecomplexity is O(N), but it can be limited to O(log(N)) if the code is modified so that the smaller half of the array is sorted first (and an explicit stack, or the tailrecursion optimisation, used). In that case, the bestcase spacecomplexity becomes O(1)
StabilityQuick sort is not stable. TestingIt is very easy to make errors when programming Quick sort. The basic idea is simple but the details of the manipulation of the "pointers" hi, lo, left, right, are very easily messed up  this is the voice of bitter experience! Notes


↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Monday, 15Apr2024 13:19:47 UTC. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 