Arndt - Algorithms for Programmers (523138), страница 35
Текст из файла (страница 35)
2{if ( f[n] < f[n-1] ) break;}return !n;}While the quicksort-algorithm presented below scales ∼ n log(n) (in the average case) it does not justobsolete the more simple schemes because (1) for arrays small enough the ‘simple’ algorithm is usually199CHAPTER 9. SORTING AND SEARCHING200the fastest method because of its minimal bookkeeping overhead and (2) therefore it is used inside thequicksort for lengths below some threshold.The main ingredient of quicksort is to partition the array: The corresponding routine reorders some elements where needed and returns some partition index k so that max(f0 , . . .
, fk−1 ) ≤ min(fk , . . . , fn−1 ):template <typename Type>ulong partition(Type *f, ulong n)// rearrange array, so that for some index p// max(f[0] ... f[p]) <= min(f[p+1] ... f[n-1]){swap( f[0], f[n/2]); // avoid worst case with already sorted inputconst Type v = f[0];ulong i = 0UL - 1;ulong j = n;while ( 1 ){do { ++i; } while ( f[i]<v );do { --j; } while ( f[j]>v );if ( i<j ) swap(f[i], f[j]);elsereturn j;}}which we want to be able to verify:template <typename Type>Type inline min(const Type *f, ulong n)// returns minimum of array{Type v = f[0];while ( n-- ) if ( f[n]<v ) v = f[n];return v;}template <typename Type>inline Type max(const Type *f, ulong n)// returns maximum of array{Type v = f[0];while ( n-- ) if ( f[n]>v ) v = f[n];return v;}template <typename Type>int is_partitioned(const Type *f, ulong n, ulong k){++k;Type lmax = max(f,k);Type rmin = min(f+k, n-k);return ( lmax<=rmin );}Quicksort calls partition on the whole array, then on the parts left and right from the partition indexand repeat.
When the size of the subproblems is smaller than a certain threshold selection sort is used.template <typename Type>void quick_sort(Type *f, ulong n){start:if ( n<8 ) // parameter: threshold for nonrecursive algorithm{selection_sort(f, n);return;}ulong p = partition(f, n);ulong ln = p + 1;ulong rn = n - ln;if ( ln>rn ) // recursion for shorter subarray{quick_sort(f+ln, rn); // f[ln] ... f[n-1]rightCHAPTER 9. SORTING AND SEARCHING}else{}201n = ln;quick_sort(f, ln);n = rn;f += ln;// f[0]...
f[ln-1]left}goto start;[FXT: file sort/sort.h]TBD: worst case and how to avoid it9.2SearchingThe reason why some data was sorted may be that a fast search has to be performed repeatedly. Thefollowing bsearch is ∼ log(n) and works by the obvious subdivision of the data:template <typename Type>ulong bsearch(const Type *f, ulong n, const Type v)// return index of first element in f[] that is == v// return ~0 if there is no such element// f[] must be sorted in ascending order// must have n!=0{ulong nlo=0, nhi=n-1;while ( nlo != nhi ){ulong t = (nhi+nlo)/2;if ( f[t] < v ) nlo = t + 1;elsenhi = t;}if ( f[nhi]==v ) return nhi;elsereturn ~0UL;}A simple modification of bsearch makes it search the first element greater than v: Replace the operator== in the above code by >= and you have it: [FXT: bsearch ge in sort/search.h].Approximate matches are found bytemplate <typename Type>ulong bsearch_approx(const Type *f, ulong n, const Type v, Type da)// return index of first element x in f[] for which |(x-v)| <= da// return ~0 if there is no such element// f[] must be sorted in ascending order// da must be positive// makes sense only with inexact types (float or double)// must have n!=0{ulong k = bsearch_ge(f, n, v-da);if ( k<n ) k = bsearch_le(f+k, n-k, v+da);return k;}where bsearch_le() searches for an element less or equal to a given value.When the values to be searched will themselves appear in monotone order you can reduce the total timeused for searching with:template <typename Type>inline long search_down(const Type *f, const Type v, ulong &i)// search v in f[], starting at i (so i must be < length)// f[i] must be greater or equal v// f[] must be sorted in ascending orderCHAPTER 9.
SORTING AND SEARCHING202// returns index k if f[k]==v or ~0 if no such k is found// i is updated so that it can be used for a following// search for an element u where u < v{while ( (f[i]>v) && (i>0) ) --i;if ( f[i]==v ) return i;elsereturn ~0UL;}[FXT: file sort/search.h]9.3Index sortingWhile the ‘plain’ sorting reorders an array f so that, after it has finished, fk ≤ fk+1 the following routinessort an array of indices without modifying the actual data:template <typename Type>void idx_selection_sort(const Type *f, ulong n, ulong *x){for (ulong i=0; i<n; ++i){Type v = f[x[i]];ulong m = i; // position-ptr of minimumulong j = n;while ( --j > i ) // search (index of) minimum{if ( f[x[j]]<v ){m = j;v = f[x[m]];}}swap(x[i], x[m]);}}Apart from the ‘read only’-feature the index-sort routines have the nice property to perfectly work onnon-contiguous data.The verification code looks like:template <typename Type>int is_idx_sorted(const Type *f, ulong n, const ulong *x){if ( 0==n ) return 1;while ( --n ) // n-1 ...
1{if ( f[x[n]] < f[x[n-1]] ) break;}return !n;}The index-sort routines reorder the indices in x such that x applied to f as a permutation (in the senseof section 7.13.3) will render f a sorted array.While the transformation of partition is straight forward:template <typename Type>ulong idx_partition(const Type *f, ulong n, ulong *x)// rearrange index array, so that for some index p// max(f[x[0]] ... f[x[p]]) <= min(f[x[p+1]] ... f[x[n-1]]){swap( x[0], x[n/2]);const Type v = f[x[0]];ulong i = 0UL - 1;CHAPTER 9. SORTING AND SEARCHING}203ulong j = n;while ( 1 ){do ++i;while ( f[x[i]]<v );do --j;while ( f[x[j]]>v );if ( i<j ) swap(x[i], x[j]);elsereturn j;}The index-quicksort itself deserves a minute of contemplation comparing it to the plain version:template <typename Type>void idx_quick_sort(const Type *f, ulong n, ulong *x){start:if ( n<8 ) // parameter: threshold for nonrecursive algorithm{idx_selection_sort(f, n, x);return;}ulong p = idx_partition(f, n, x);ulong ln = p + 1;ulong rn = n - ln;if ( ln>rn ) // recursion for shorter subarray{idx_quick_sort(f, rn, x+ln); // f[x[ln]] ...
f[x[n-1]] rightn = ln;}else{idx_quick_sort(f, ln, x); // f[x[0]] ... f[x[ln-1]] leftn = rn;x += ln;}goto start;}[FXT: file sort/sortidx.h]The index-analogues of bsearch etc. are again straight forward, they can be found in [FXT: filesort/searchidx.h].9.4Pointer sortingPointer sorting is an idea similar to index sorting which is even less restricted than index sort: The datamay be unaligned in memory. And overlapping. Or no data at all but port addresses controlling somehighly dangerous machinery.Thereby pointer sort is the perfect way to highly cryptic and powerful programs that seg-fault when youleast expect it.
Admittedly, all the ‘dangerous’ features of pointer sort except the unaligned one are alsothere in index sort. However, with index sort you will not so often use them by accident.Just to make the idea clear, the array of indices is replaced by an array of pointers:template <typename Type>void ptr_selection_sort(const Type *f, ulong n, Type **x){for (ulong i=0; i<n; ++i){Type v = *x[i];ulong m = i; // position-ptr of minimumulong j = n;while ( --j > i ) // search (index of) minimum{CHAPTER 9.
SORTING AND SEARCHING204if ( *x[j]<v ){m = j;v = *x[m];}}}}swap(x[i], x[m]);Find the pointer sorting code in [FXT: file sort/sortptr.h] and the pointer search routines in [FXT: filesort/searchptr.h].9.5Sorting by a supplied comparison functionThe routines in [FXT: file sort/sortfunc.h] are similar to the C-quicksort qsort that is part of thestandard library. A comparison function cmp has to be supplied by the called so that compound datatypes can be sorted with respect to some key contained.
Citing the manual page for qsort:The comparison function must return an integer less than, equal to, or greater thanzero if the first argument is considered to be respectively less than, equal to, orgreater than the second. If two members compare as equal, their order in thesorted array is undefined.Note that the numerous calls to cmp do have a negative impact on the performance. And then with C++you can provide a comparison ‘function’ for compound data by overloading the operators <, <, <= and>= and use the plain version. Back in performance land. Isn’t C++ nice? TBD: add a compile-timeinlined version?As a prototypical example here the version of selection sort:template <typename Type>void selection_sort(Type *f, ulong n, int (*cmp)(const Type &, const Type &)){for (ulong i=0; i<n; ++i){Type v = f[i];ulong m = i; // position of minimumulong j = n;while ( --j > i ) // search (index of) minimum{if ( cmp(f[j],v) < 0 ){m = j;v = f[m];}}swap(f[i], f[m]);}}The rest of the supplied routines a rather straight forward translation of the (plain-) sort analogues, thefunction one will most likely use beingtemplate <typename Type>void quick_sort(Type *f, ulong n, int (*cmp)(const Type &, const Type &))Sorting complex numbersYou want to sort complex numbers? Fine for me, but don’t tell your local mathematician.
To see themathematical problem we ask whether i is smaller or greater than zero. Assume i > 0: follows i · i > 0CHAPTER 9. SORTING AND SEARCHING205(we multiplied with a positive value) which is −1 > 0 and that is false. So, is i < 0? Then i · i > 0(multiplication with a negative value, as assumed). So −1 > 0, oops! The lesson is that there is no wayto impose an arrangement on the complex numbers that would justify the usage of the symbols < and >in the mathematical sense.Nevertheless we can invent a relation that allows us to sort: arranging (sorting) the complex numbersaccording to their absolute value (modulus) leaves infinitely many numbers in one ‘bucket’, namely allthose that have the same distance to zero. However, one could use the modulus as the major orderingparameter, the angle as the minor.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
