Arndt - Algorithms for Programmers (523138), страница 36

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 36)

Or the real part as the major and the imaginary part as the minor.The latter is realized instatic inline intcmp_complex(const Complex &f, const Complex &g){int ret = 0;double fr = f.real();double gr = g.real();if ( fr==gr ){double fi = f.imag();double gi = g.imag();if ( fi!=gi ) ret = (fi>gi ? +1 : -1);}elseret = (fr>gr ? +1 : -1);return ret;}which, when used as comparison with the above function-sort as invoid complex_sort(Complex *f, ulong n)// major order wrt.

real part// minor order wrt. imag part{quick_sort(f, n, cmp_complex);}can indeed be the practical tool you had in mind.9.6UniqueThis section presents a few utility functions that revolve around whether values in a (sorted) array arerepeated or unique.Testing whether all values are unique:template <typename Type>int test_unique(const Type *f, ulong n)// for a sorted array test whether all values are unique//(i.e. whether no value is repeated)//// returns 0 if all values are unique// else returns index of the second element in the first pair found//// this function is not called "is_unique()" because it// returns 0 (=="false") for a positive answer{for (ulong k=1; k<n; ++k){if ( f[k] == f[k-1] ) return k; // k != 0}return 0;}The same thing, but for inexact types (floats): the maximal (absolute) difference within which twocontiguous elements will still be considered equal can be provided as additional parameter.

One subtleCHAPTER 9. SORTING AND SEARCHING206point is that the values can slowly ‘drift away’ unnoticed by this implementation: Consider a long arraywhere each difference computed has the same sign and is just smaller than da, say it is d = 0.6·da. Thedifference of the first and last value then is 0.6 · (n − 1) · d which is greater than da for n ≥ 3.template <typename Type>int test_unique_approx(const Type *f, ulong n, Type da)// for a sorted array test whether all values are// unique within some tolerance//(i.e. whether no value is repeated)//// returns 0 if all values are unique// else returns index of the second element in the first pair found//// makes mostly sense with inexact types (float or double){if ( da<=0 ) da = -da; // want positive tolerancefor (ulong k=1; k<n; ++k){Type d = (f[k] - f[k-1]);if ( d<=0 ) d = -d;if ( d < da ) return k; // k != 0}return 0;}An alternative way to deal with inexact types is to applytemplate <typename Type>void quantise(Type *f, ulong n, double q)//// in f[] set each element x to q*floor(1/q*(x+q/2))// e.g.: q=1 ==> round to nearest integer//q=1/1000 ==> round to nearest multiple of 1/1000// For inexact types (float or double){Type qh = q * 0.5;Type q1 = 1.0 / q;while ( n-- ){f[n] = q * floor( q1 * (f[n]+qh) );}}[FXT: quantise in aux1/quantise.h] before using test_unique_approx.

One should use a quantizationparameter q that is greater than the value used for da.Minimalistic demo:Random values:0: 0.97277502431: 0.29251678452: 0.77135769823: 0.52674497954: 0.76991383665: 0.4002286223Quantization with q=0.01Quantised & sorted :0: 0.29000000001: 0.40000000002: 0.53000000003: 0.77000000004: 0.77000000005: 0.9700000000First REPEATED value at index 4Unique’d array:0: 0.29000000001: 0.40000000002: 0.53000000003: 0.77000000004: 0.9700000000(and 3)quantise() turns out to be also useful in another context, cf. [FXT: symbolify by size andsymbolify by order in aux1/symbolify.h].CHAPTER 9. SORTING AND SEARCHING207Counting the elements that appear just once:template <typename Type>int unique_count(const Type *f, ulong n)// for a sorted array return the number of unique values// the number of (not necessarily distinct) repeated//values is n - unique_count(f, n);{if ( 1>=n ) return n;ulong ct = 1;for (ulong k=1; k<n; ++k){if ( f[k] != f[k-1] ) ++ct;}return ct;}Removing repeated elements:template <typename Type>ulong unique(Type *f, ulong n)// for a sorted array squeeze all repeated values// and return the number of unique values// e.g.: [1, 3, 3, 4, 5, 8, 8] --> [1, 3, 4, 5, 8]// the routine also works for unsorted arrays as long//as identical elements only appear in contiguous blocks//e.g.

[4, 4, 3, 7, 7] --> [4, 3, 7]// the order is preserved{ulong u = unique_count(f, n);if ( u == n ) return n; // nothing to doType v = f[0];for (ulong j=1, k=1; j<u; ++j){while ( f[k] == v ) ++k; // search next different elementv = f[j] = f[k];}return u;}9.7MiscA sequence is called monotone if it is either purely ascending or purely descending.

This includes the casewhere subsequent elements are equal. Whether a constant sequence is considered ascending or descendingin this context is a matter of convention.template <typename Type>int is_monotone(const Type *f, ulong n)// return//+1 for ascending order//-1 for descending order//else 0{if ( 1>=n ) return +1;ulong k;for (k=1; k<n; ++k) // skip constant start{if ( f[k] != f[k-1] ) break;}if ( k==n ) return +1; // constant is considered ascending hereint s = ( f[k] > f[k-1] ? +1 : -1 );if ( s>0 ) // was: ascending{// scan for descending pair:CHAPTER 9. SORTING AND SEARCHING}for ( ; k<n; ++k) if ( f[k] < f[k-1] )}else // was: descending{// scan for ascending pair:for ( ; k<n; ++k) if ( f[k] > f[k-1] )}return s;208return 0;return 0;A strictly monotone sequence is a monotone sequence that has no identical pairs of elements. The testturns out to be slightly easier:template <typename Type>int is_strictly_monotone(const Type *f, ulong n)// return//+1 for strictly ascending order//-1 for strictly descending order//else 0{if ( 1>=n ) return +1;ulong k = 1;if ( f[k] == f[k-1] ) return 0;int s = ( f[k] > f[k-1] ? +1 : -1 );if ( s>0 ) // was: ascending{// scan for descending pair:for ( ; k<n; ++k) if ( f[k] <= f[k-1] )}else // was: descending{// scan for ascending pair:for ( ; k<n; ++k) if ( f[k] >= f[k-1] )}return s;}return 0;return 0;[FXT: file sort/monotone.h]A sequence is called convex if it starts with an ascending part and ends with a descending part.

A concavesequence starts with a descending and ends with an ascending part. Whether a monotone sequence isconsidered convex or concave again is a matter of convention (i.e. you have the choice to consider the firstor the last element as extremum). Lacking a term that contains both convex and concave the followingroutine is called is_convex:template <typename Type>long is_convex(Type *f, ulong n)//// return//+val for convex sequence (first rising then falling)//-val for concave sequence (first falling then rising)//else 0//// val is the (second) index of the first pair at the point// where the ordering changes; val>=n iff seq. is monotone.//// note: a constant sequence is considered any of rising/falling//{if ( 1>=n ) return +1;ulong k = 1;for (k=1; k<n; ++k) // skip constant start{if ( f[k] != f[k-1] ) break;}if ( k==n ) return +n; // constant is considered convex hereint s = ( f[k] > f[k-1] ? +1 : -1 );if ( s>0 ) // was: ascendingCHAPTER 9.

SORTING AND SEARCHING{}// scan for strictly descending pair:for ( ; k<n; ++k) if ( f[k] < f[k-1] )s = +k;209break;}else // was: descending{// scan for strictly ascending pair:for ( ; k<n; ++k) if ( f[k] > f[k-1] ) break;s = -k;}if ( k==n ) return s; // sequence is monotone// check that the ordering does not change again:if ( s>0 ) // was: ascending --> descending{// scan for strictly ascending pair:for ( ; k<n; ++k) if ( f[k] > f[k-1] ) return 0;}else // was: descending{// scan for strictly descending pair:for ( ; k<n; ++k) if ( f[k] < f[k-1] ) return 0;}return s;The test for strictly convex (or concave) sequences is:template <typename Type>long is_strictly_convex(Type *f, ulong n)//// return//+val for strictly convex sequence//(i.e.

first strictly rising then strictly falling)//-val for strictly concave sequence//(i.e. first strictly falling then strictly rising)//else 0//// val is the (second) index of the first pair at the point// where the ordering changes; val>=n iff seq. is strictly monotone.//{if ( 1>=n ) return +1;ulong k = 1;if ( f[k] == f[k-1] ) return 0;int s = ( f[k] > f[k-1] ? +1 : -1 );if ( s>0 ) // was: ascending{// scan for descending pair:for ( ; k<n; ++k) if ( f[k] <= f[k-1] ) break;s = +k;}else // was: descending{// scan for ascending pair:for ( ; k<n; ++k) if ( f[k] >= f[k-1] ) break;s = -k;}if ( k==n ) return s; // sequence is monotoneelse if ( f[k] == f[k-1] ) return 0;// check that the ordering does not change again:if ( s>0 ) // was: ascending --> descending{// scan for ascending pair:for ( ; k<n; ++k) if ( f[k] >= f[k-1] ) return 0;}else // was: descending{// scan for descending pair:for ( ; k<n; ++k) if ( f[k] <= f[k-1] ) return 0;CHAPTER 9.

SORTING AND SEARCHING}}return210s;[FXT: file sort/convex.h]The tests given are mostly useful as assertions used inside more complex algorithms.9.8Heap-sortAn alternative algorithm for sorting uses the heap data structure introduced in section 10.5 (p.218).A heap can be sorted by swapping the first (and biggest) element with the last and ‘repairing’ the arrayof size n − 1 by a call to heapify1.

Applying this idea recursively until there is nothing more to sortleads to the routinetemplate <typename Type>void heap_sort_ascending(Type *x, ulong n)// sort an array that has the heap-property into ascending order.// On return x[] is _not_ a heap anymore.{Type *p = x - 1;for (ulong k=n; k>1; --k){swap(p[1], p[k]);// move largest to end of array--n;// remaining array is one element lessheapify1(p, n, 1); // restore heap-property}}that needs time O(n log(n)).

Характеристики

Список файлов книги