Lesson of 14 July 2009 (morning)

Improved QuickSort

File quicksort.cc

  1/*
  2   Algorithm quick sort, generalization
  3   by using C technique
  4 */
  5
  6#include <iostream> // use I/O of C++
  7#include <string.h> // for memcpy
  8#include <alloca.h> // for the use of alloca
  9
 10using namespace std ;
 11
 12/*
 13   Define the type Comparator as a pointer to 
 14   function used to compare two elements.
 15
 16   if return value is   
 17   0     : a is equal to b
 18   >= 1  : a is greater than b
 19   <= -1 : a is less than b
 20 */
 21
 22typedef int (*Comparator)( void * a, void * b ) ;
 23
 24/* function that calculate the addess of an element 
 25   of a generic vector given a pointer to the 
 26   begin of the vector at the size of each element */
 27   
 28void *
 29getAddress( void * beginOfVector,
 30            int    index,
 31            int    sizeOfElement ) {
 32  return (char*) beginOfVector + index * sizeOfElement ;  
 33}
 34
 35/*
 36  Sort a verctor of integer by quick sort algorithm
 37  (John O'Hara algorithm)
 38 */
 39void
 40quickSort ( void     * a,  // pointer to the a memory location where the vector lies.
 41            int        lo, // lo is the lower index of the region to be sorted
 42            int        hi, // hi is the upper index of the region to be sorted
 43            int        sizeOfElement, // size of the single element
 44            Comparator comp,          // pointer to the comparator fuction
 45            int        level
 46           ) {
 47  
 48  // level = level of recursion
 49  for ( int kk = 0 ; kk < level ; ++kk ) cout << " " ;
 50  cout << "[" << lo << ", " << hi << "]\n" ;
 51
 52  // sort only if we have at least 2 element
 53  if ( hi <= lo ) return ;
 54  
 55  // memory allocation to store the pivot.
 56  // We need sizeOfElement bytes of allocation.
 57  // You can use void * pivot = new char [sizeOfElement] ;
 58  // but char cab be BAD aligned in memory.
 59  // nelem is the minimum number of int that is larger of
 60  // sizeOfElement bytes 
 61  int    nelem = (sizeOfElement+sizeof(int)-1)/sizeof(int) ;
 62
 63  /*
 64  // new allocate memory for nelem int and return a poiter
 65  // to this memory
 66  int * pivot  = new int [nelem] ;
 67  
 68  // buffer of memory for swap elements
 69  int * buffer = new int [nelem] ;
 70  */
 71
 72  // use alloca instead of new
 73  int * pivot  = (int*)alloca(sizeOfElement) ;
 74  int * buffer = (int*)alloca(sizeOfElement) ;
 75  
 76  int i = lo ; // i is set to the beginning of the region
 77  int j = hi ; // j is set to the end of the region
 78
 79  //
 80  int ipivot = (lo+hi)/2 ; // (lo+hi)/2 the pivot is chosen
 81  
 82  // calculate the address of ipivot element
 83  // (char*) a is a "cast" to convert the void* pointer
 84  // to a char* pointer which point to element of size 1-byte
 85  //void * a_ipivot = (char*)a + ipivot * sizeOfElement ;
 86  void * a_ipivot = getAddress( a, ipivot, sizeOfElement ) ;
 87
 88  // copy the pivot to the allocated memory
 89  memcpy( pivot, a_ipivot, sizeOfElement ) ;
 90
 91  //  partition
 92  while ( j > i ) { // if i==j only one elemet: the region is sorted
 93                    // if i < j empty region, nothing to sort 
 94    
 95    
 96    // To compare a[i] with pivot use
 97    // int res = (*comp) ( getAddress( a, i, sizeOfElement ), pivot )
 98    // you can use the following sintactic glue
 99    // int res = comp( getAddress( a, i, sizeOfElement ), pivot )
100    //
101    
102    while ( comp( getAddress( a, i, sizeOfElement ), pivot ) < 0 ) i++ ; // a[ii] for ii <= i are less than pivot 
103    while ( comp( getAddress( a, j, sizeOfElement ), pivot ) > 0 ) j-- ; // a[jj] for jj >= j are greater than pivot
104
105    if ( i <= j ) { // check if the sub-regions are complete.
106      // if not, we need to exchange the elements outside the
107      // sub-regions
108      void * ai = getAddress( a, i, sizeOfElement ) ;
109      void * aj = getAddress( a, j, sizeOfElement ) ;
110      
111      // buffer = a[i] ;
112      memcpy( buffer, ai, sizeOfElement ) ;
113
114      // a[i] = a[j]
115      memcpy( ai, aj, sizeOfElement ) ;
116      
117      // a[j] = buffer
118      memcpy( aj, buffer, sizeOfElement ) ;
119
120      i++; j--; // a[i] and a[j] are in the correct region
121                // so that we do not need to check again
122    }
123  } ;
124
125  //  recursion onfy if region is not empty
126  quickSort(a, lo, j, sizeOfElement, comp, level+1);
127  quickSort(a, i, hi, sizeOfElement, comp, level+1);
128
129  // free the allocated memory
130  /*
131  using alloca no need to free memory
132  delete [] pivot ;
133  delete [] buffer ;
134  */
135}
136
137/*
138   Function that compare the pointer of two integer
139 */
140int
141comp_int( void * pa, void * pb ) {
142  // (int*)a tell to the compiler that a point to int type
143  // * ( ) read the memory (deferentiation)
144  int ia = * ((int*)pa) ; // copy the content at address pa to the variable ia
145  int ib = * ((int*)pb) ; // copy the content at address pb to the variable ib
146  if ( ia < ib ) return -1 ;
147  if ( ia > ib ) return +1 ;
148  return 0 ;
149}
150
151/*
152   Function that compare the pointer of two integer
153 */
154int
155comp_double( void * pa, void * pb ) {
156  // (double*)a tell to the compiler that a point to int type
157  // * ( ) read the memory (deferentiation)
158  double da = * ((double*)pa) ; // copy the content at address pa to the variable ia
159  double db = * ((double*)pb) ; // copy the content at address pb to the variable ib
160  if ( da < db ) return -1 ;
161  if ( da > db ) return +1 ;
162  return 0 ;
163}
164
165int
166main() {
167  int vec[100] ; // declare and instance a vector of 100 elements
168  
169  // initialize some elements
170  vec[0] = 9   ;
171  vec[1] = 1   ;
172  vec[2] = -1  ;
173  vec[3] = 2   ;
174  vec[4] = 2   ;
175  vec[5] = 6   ;
176  vec[6] = 5   ;
177  vec[7] = -23 ;
178  vec[8] = -2  ;
179  vec[9] = 1   ;
180  
181  quickSort( vec, 0, 9, sizeof(vec[0]), comp_int, 0 ) ;
182  
183  // cout = character out object
184  for ( int i = 0 ; i < 10 ; ++i )
185    cout << i << " " << vec[i] << '\n' ;
186    
187  // define and initialize a vector
188  int b[] = { 1, 2, -3, 0, -45, -1, 0, 3, 67} ;
189
190  // evaluate the size of vector b.
191  // sizeof return the size in byte of the element in argument
192  // sizeof(b) return the number of bytes used by  the whole vector
193  // sizeof(b[0]) return the number of bytes used by and element of the vector
194  int szb = sizeof(b)/sizeof(b[0]) ;
195  
196  quickSort( b, 0, szb-1, sizeof(vec[0]), comp_int, 0 ) ;
197
198  //cout = character out object
199  for ( int i = 0 ; i < szb ; ++i )
200    cout << i << " " << b[i] << '\n' ;
201    
202    
203  // allocate a vector of double
204  double * dvec = new double[ 10 ] ;
205  dvec[0] = 3 ;
206  dvec[1] = 1.2 ;
207  dvec[2] = 0.3 ;
208  dvec[3] = 1/4.;
209  dvec[4] = 2 ;
210  dvec[5] = -0.34 ;
211  dvec[6] = 0.000001 ;
212  dvec[7] = -0.000001 ;
213  dvec[8] = 1 ;
214  dvec[9] = 3 ;
215  
216  quickSort( dvec, 0, 9, sizeof(double), comp_double, 0 ) ;
217  for ( int i = 0 ; i < 10 ; ++i )
218    cout << i << " " << dvec[i] << '\n' ;
219
220  // free the memory used to allocate the vector
221  delete [] dvec ;
222
223  return 0 ;
224}

Infinite recursion

File stack.cc

 1// a simple infinite recursion to show stack overflow
 2
 3void
 4overflow(int i) {
 5 overflow(i+1) ;
 6 overflow(i+2) ;
 7 overflow(i+3) ;
 8 overflow(i+4) ;
 9 overflow(i+5) ;
10 overflow(i+6) ;
11 overflow(i+7) ;
12 overflow(i+8) ;
13 overflow(i+9) ;
14}
15
16int
17main() {
18  overflow(1) ;
19  return 1 ;
20}