Lesson of 14 July 2009 (afternoon)

QuickSort rewritten with an header and an implementation file

File quicksort.hh

 1/*
 2  Parametrize the type for quickSort,
 3  valueType is an alias for double
 4 */
 5
 6typedef double valueType ;
 7
 8/*
 9   Algorithm quick sort
10 */
11
12extern // means that the routine here declared is defined somewhere
13void
14quickSort ( valueType a[], // vector to be sorted
15            int const n    // number of element of the vector to be sorted
16           ) ;

File quicksort.cc

 1/*
 2   Algorithm quick sort
 3 */
 4#include "quicksort.hh"
 5#include <iostream> // use I/O of C++
 6#include <algorithm> // use STL algorithm
 7
 8using namespace std ; // load the functions in standard namespace
 9
10// declare the prototype for the routine that perform the sort
11static void quickSort ( valueType a[], int lo, int hi, int level ) ;
12
13// implementation of quickSort
14void
15quickSort ( valueType a[], int const n ) {
16  // due to overloading quickSort is selected by 
17  // the matching of its arguments
18  quickSort (a, 0, n-1, 0) ;
19}
20
21/*
22  Sort a verctor of integer by quick sort algorithm
23  (John O'Hara algorithm)
24 */
25static  // static means the routine is visible only in "this file"
26void
27quickSort (valueType a[], int lo, int hi, int level) {
28  // a[]: a is a pointer to the vector,
29  // to access the element use a[0] = the first element
30  // a[1] the second element, a[k] the k+1 element.
31  //
32  // lo is the lower index, hi is the upper index
33  // of the region of array a that is to be sorted
34  //
35  // level = level of recursion
36  for ( int kk = 0 ; kk < level ; ++kk ) cout << " " ;
37  cout << "[" << lo << ", " << hi << "]\n" ;
38
39  // sort only if we have at least 2 element
40  if ( hi <= lo ) return ;
41  
42  int i     = lo ; // i is set to the beginning of the region
43  int j     = hi ; // j is set to the end of the region
44  int pivot = a[(lo+hi)/2] ; // (lo+hi)/2 the pivot is chosen
45                             // in the middle of the vector
46                             // but any index between lo and hi 
47                             // can be used.
48                             // (lo+hi)/2 is truncated to 
49                             // the lower near integer
50  //  partition
51  while ( j > i ) { // if i==j only one element: the region is sorted
52                    // if i < j empty region, nothing to sort 
53    
54    while ( a[i] < pivot ) i++ ; // a[ii] for ii <= i are less than pivot 
55    while ( a[j] > pivot ) j-- ; // a[jj] for jj >= j are greater than pivot
56
57    if ( i <= j ) { // check if the sub-regions are complete.
58      // if not, we need to exchange the elements outside the
59      // sub-regions
60      swap( a[i], a[j] ) ;
61      i++; j--; // a[i] and a[j] are in the correct region
62                // so that we do not need to check again
63    }
64  } ;
65
66  //  recursion onfy if region is not empty
67  quickSort(a, lo, j, level+1);
68  quickSort(a, i, hi, level+1);
69}

File prova.cc

 1#include "quicksort.hh"
 2#include <iostream>
 3
 4using namespace std ;
 5
 6int
 7main() {
 8
 9  // define and initialize a vector
10  valueType b[] = { 1.2, 2.2, -0.3, 0, -45, -1, 0, 3, 67} ;
11
12  // evaluate the size of vector b.
13  // sizeof return the size in byte of the element in argument
14  // sizeof(b) return the number of bytes used by  the whole vector
15  // sizeof(b[0]) return the number of bytes used by and element of the vector
16  int szb = sizeof(b)/sizeof(b[0]) ;
17  
18  quickSort( b, szb ) ;
19
20  //cout = character out object
21  for ( int i = 0 ; i < szb ; ++i )
22    cout << i << " " << b[i] << '\n' ;
23
24  return 0 ;
25}

Multiple version of QuickSort by using overloading an macros

File macro/quicksort.hh

 1/*
 2   Algorithm quick sort
 3 */
 4
 5#define VALUE int
 6#include "quicksort.hxx"
 7#undef VALUE
 8
 9#define VALUE double
10#include "quicksort.hxx"
11#undef VALUE
12
13#define VALUE float
14#include "quicksort.hxx"
15#undef VALUE
16
17/*
18
19extern void quickSort ( int    a[], int const n ) ;
20extern void quickSort ( double a[], int const n ) ;
21
22*/

File macro/quicksort.hxx

1/*
2   Algorithm quick sort
3 */
4
5extern // means that the routine here declared is defined somewhere
6void
7quickSort ( VALUE     a[], // vector to be sorted
8            int const n    // number of element of the vector to be sorted
9           ) ;

File macro/quicksort.cc

 1#include "quicksort.hh"
 2#include <iostream> // use I/O of C++
 3#include <algorithm> // use STL algorithm
 4
 5using namespace std ; // load the functions in standard namespace
 6
 7#define VALUE int
 8#include "quicksort.cxx"
 9#undef VALUE
10
11#define VALUE double
12#include "quicksort.cxx"
13#undef VALUE
14
15#define VALUE float
16#include "quicksort.cxx"
17#undef VALUE

File macro/quicksort.cxx

 1/*
 2   Algorithm quick sort
 3 */
 4
 5// declare the prototype for the routine that perform the sort
 6static void quickSort ( VALUE a[], int lo, int hi, int level ) ;
 7
 8// implementation of quickSort
 9void
10quickSort ( VALUE a[], int const n ) {
11  // due to overloading quickSort is selected by 
12  // the matching of its arguments
13  quickSort (a, 0, n-1, 0) ;
14}
15
16/*
17  Sort a verctor of integer by quick sort algorithm
18  (John O'Hara algorithm)
19 */
20static  // static means the routine is visible only in "this file"
21void
22quickSort (VALUE a[], int lo, int hi, int level) {
23  // a[]: a is a pointer to the vector,
24  // to access the element use a[0] = the first element
25  // a[1] the second element, a[k] the k+1 element.
26  //
27  // lo is the lower index, hi is the upper index
28  // of the region of array a that is to be sorted
29  //
30  // level = level of recursion
31  for ( int kk = 0 ; kk < level ; ++kk ) cout << " " ;
32  cout << "[" << lo << ", " << hi << "]\n" ;
33
34  // sort only if we have at least 2 element
35  if ( hi <= lo ) return ;
36  
37  int i       = lo ; // i is set to the beginning of the region
38  int j       = hi ; // j is set to the end of the region
39  VALUE pivot = a[(lo+hi)/2] ; // (lo+hi)/2 the pivot is chosen
40                               // in the middle of the vector
41                               // but any index between lo and hi 
42                               // can be used.
43                               // (lo+hi)/2 is truncated to 
44                               // the lower near integer
45  //  partition
46  while ( j > i ) { // if i==j only one elemet: the region is sorted
47                    // if i < j empty region, nothing to sort 
48    
49    while ( a[i] < pivot ) i++ ; // a[ii] for ii <= i are less than pivot 
50    while ( a[j] > pivot ) j-- ; // a[jj] for jj >= j are greater than pivot
51
52    if ( i <= j ) { // check if the sub-regions are complete.
53      // if not, we need to exchange the elements outside the
54      // sub-regions
55      swap( a[i], a[j] ) ;
56      i++; j--; // a[i] and a[j] are in the correct region
57                // so that we do not need to check again
58    }
59  } ;
60
61  //  recursion onfy if region is not empty
62  quickSort(a, lo, j, level+1);
63  quickSort(a, i, hi, level+1);
64}

File macro/prova.cc

 1#include "quicksort.hh"
 2#include <iostream>
 3
 4using namespace std ;
 5
 6int
 7main() {
 8
 9  // define and initialize a vector
10  double b[] = { 1.2, 2.2, -0.3, 0, -45, -1, 0, 3, 67} ;
11
12  // evaluate the size of vector b.
13  // sizeof return the size in byte of the element in argument
14  // sizeof(b) return the number of bytes used by  the whole vector
15  // sizeof(b[0]) return the number of bytes used by and element of the vector
16  int szb = sizeof(b)/sizeof(b[0]) ;
17  
18  quickSort( b, szb ) ;
19
20  //cout = character out object
21  for ( int i = 0 ; i < szb ; ++i )
22    cout << i << " " << b[i] << '\n' ;
23
24  return 0 ;
25}

Multiple version of QuickSort by using templates

File template/quicksort.hh

 1#include <iostream>
 2
 3/*
 4   Algorithm quick sort
 5 */
 6
 7template <typename VALUE>
 8void quickSort ( VALUE a[], int lo, int hi, int level ) ;
 9
10
11// VALUE can be any type
12template <typename VALUE>
13void quickSort ( VALUE a[], int const n ) ;
14
15/*
16   Algorithm implementation
17 */
18
19// implementation of quickSort
20template <typename VALUE>
21void
22quickSort ( VALUE a[], int const n ) {
23  quickSort (a, 0, n-1, 0) ;
24}
25
26template <typename VALUE>
27void
28quickSort (VALUE a[], int lo, int hi, int level) {
29
30  using namespace std ;
31
32  for ( int kk = 0 ; kk < level ; ++kk ) cout << " " ;
33  cout << "[" << lo << ", " << hi << "]\n" ;
34
35  // sort only if we have at least 2 element
36  if ( hi <= lo ) return ;
37  
38  int i       = lo ; // i is set to the beginning of the region
39  int j       = hi ; // j is set to the end of the region
40  VALUE pivot = a[(lo+hi)/2] ; // (lo+hi)/2 the pivot is chosen
41                               // in the middle of the vector
42                               // but any index between lo and hi 
43                               // can be used.
44                               // (lo+hi)/2 is truncated to 
45                               // the lower near integer
46  //  partition
47  while ( j > i ) { // if i==j only one elemet: the region is sorted
48                    // if i < j empty region, nothing to sort 
49    
50    while ( a[i] < pivot ) i++ ; // a[ii] for ii <= i are less than pivot 
51    while ( a[j] > pivot ) j-- ; // a[jj] for jj >= j are greater than pivot
52
53    if ( i <= j ) { // check if the sub-regions are complete.
54      // if not, we need to exchange the elements outside the
55      // sub-regions
56      swap( a[i], a[j] ) ;
57      i++; j--; // a[i] and a[j] are in the correct region
58                // so that we do not need to check again
59    }
60  } ;
61
62  //  recursion onfy if region is not empty
63  quickSort(a, lo, j, level+1);
64  quickSort(a, i, hi, level+1);
65}

File template/prova.cc

 1#include "quicksort.hh"
 2#include <iostream>
 3#include <algorithm> // to include "sort" 
 4
 5using namespace std ;
 6
 7int
 8main() {
 9
10  // define and initialize a vector
11  //double b[] = { 1.2, 2.2, -0.3, 0, -45, -1, 0, 3, 67} ;
12  unsigned long b[] = { 1, 2, 3, 0, 45, 1, 0, 3, 67} ;
13
14  // evaluate the size of vector b.
15  // sizeof return the size in byte of the element in argument
16  // sizeof(b) return the number of bytes used by  the whole vector
17  // sizeof(b[0]) return the number of bytes used by and element of the vector
18  unsigned szb = sizeof(b)/sizeof(b[0]) ;
19  
20  quickSort( b, szb ) ;
21
22  //cout = character out object
23  for ( int i = 0 ; i < szb ; ++i )
24    cout << i << " " << b[i] << '\n' ;
25    
26  
27  // define and initialize a vector
28  //double b[] = { 1.2, 2.2, -0.3, 0, -45, -1, 0, 3, 67} ;
29  int bb[] = { 1, 2, 3, 0, 45, 1, 10, 3, 67} ;
30
31  // use STL to sort the vector
32  sort( bb, bb + 9 ) ;
33  //cout = character out object
34  for ( int i = 0 ; i < szb ; ++i )
35    cout << i << " " << bb[i] << '\n' ;
36
37  return 0 ;
38}

Multiple version of Max by using templates

File template/max.cc

 1#include <iostream>
 2
 3using namespace std ;
 4
 5template <typename T>
 6T
 7massimo( T const & a, T const & b) {
 8  if ( a > b ) return a ;
 9  else         return b ;
10}
11
12template <typename T1, typename T2>
13T2
14massimo1( T1 const & a, T2 const & b) {
15  if ( a > b ) return a ;
16  else         return b ;
17}
18
19
20int
21main() {
22
23  cout << massimo1( 2,3.2 ) << '\n' ;
24  cout << massimo1( 2.3,1)  << '\n' ;
25
26  return 0 ;
27}

STL Vector and Maps

File template/vectorTest.cc

 1#include <iostream>
 2#include <vector> // to include "vector"
 3#include <algorithm> // to include "sort" 
 4
 5using namespace std ;
 6
 7int
 8main() {
 9
10  vector<float> v ; // declare an empty vector of 0-size
11  vector<float> w(100) ; // declare an empty vector of size 100
12  
13  // fill a vector incrementally
14  
15  for ( int i = 0 ; i < 10 ; ++i ) {
16    cout << "Size of v = " << v . size() << '\n' ;
17    v . push_back( (i*23) % 5 ) ; // add an element to vector and increase by one its size
18    cout << "Size of v = " << v . size() << '\n' ;
19  }
20  
21  // access to element directly
22  v[3] = 4.5 ;
23  
24  for ( vector<float>::iterator iv = v . begin() ; // get iterator pointing 
25                                                   // to the first element
26        iv != v . end() ; // check if the iterator point to the (past) to
27                          // the last element
28        ++iv // move the iterator to "point" the next element
29      )
30    cout << *iv << '\n' ; 
31        
32  sort( v . begin() , v . end() ) ;
33  
34  for ( vector<float>::iterator iv = v . begin() ; // get iterator pointing 
35                                                   // to the first element
36        iv != v . end() ; // check if the iterator point to the (past) to
37                          // the last element
38        ++iv // move the iterator to "point" the next element
39      )
40    cout << *iv << '\n' ; 
41  
42  int i = 0 ;
43  int i1 = i++ ; 
44  int i2 = ++i ;
45  cout << i << " " << i1 << " " << i2 << '\n' ;
46
47  return 0 ;
48}

File template/mapTest.cc

 1#include <iostream>
 2#include <map> // to include "map"
 3#include <algorithm> // to include "sort" 
 4#include <string>
 5
 6using namespace std ;
 7
 8int
 9main() {
10
11  map<string,string> months ; // declare an empty map
12  
13  months["january"]   = "31";
14  months["february"]  = "28";
15  months["march"]     = "31";
16  months["april"]     = "30";
17  months["may"]       = "31";
18  months["june"]      = "30";
19  months["july"]      = "31";
20  months["august"]    = "31";
21  months["september"] = "30";
22  months["october"]   = "31";
23  months["november"]  = "30";
24  months["december"]  = "31";
25
26  
27  for ( map<string,string>::iterator im = months . begin() ; 
28        im != months . end() ;
29        ++im ) {
30    cout << im -> first << " " << im -> second << '\n' ;
31  }
32
33  // (*im).first ;
34  map<int,double> sparsev ;
35  
36  sparsev[1]        = 1.23 ;
37  sparsev[1001]     = 1.23 ;
38  sparsev[-2345233] = 1.23 ;
39
40  for ( map<int,double>::iterator im = sparsev . begin() ; 
41        im != sparsev . end() ;
42        ++im ) {
43    cout << im -> first << " " << im -> second << '\n' ;
44  }
45
46  return 0 ;
47}