Kinesia Online Course
Data Structures
Kinesia LLC, 2003

    1. Basic Concepts
    2. The Standard Library Container Class
    3. Vectors and Component Reuse
    4. Lists: A Dynamic Data Structure
    5. Stacks and Queues
    		  
    6. Sets and Multisets
    7. Trees
    8. Hashing

    Self-knowledge is best learned, not by contemplation,
but by action.  Strive to do your duty and you will soon
discover of what stuff you are made.

					Johann Goethe
    Vectors and Component Reuse
    1. Templates

      sorting strings 

      #include "str.h"

void sort ( String *a, int n )
{
  int changed;
  String temp;

  do {
    changed = 0;
    for ( int i = 0; i < n - 1; i++ ) {
      if ( a[i+1] < a[i] ) {
	temp = a[i];
	a[i] = a[i+1];
	a[i+1] = temp;
	changed = 1;
      }
    } 
  } while ( changed );
}

      sorting floating point numbers 

      void sort ( float *a, int n )
{
  int changed;
  float temp;

  do {
    changed = 0;
    for ( int i = 0; i < n - 1; i++ ) {
      if ( a[i+1] < a[i] ) {
	temp = a[i];
	a[i] = a[i+1];
	a[i+1] = temp;
	changed = 1;
      }
    } 
  } while ( changed );
}

      sorting integers? characters? Objects? ....

      use template to handle all cases 

      //sorttemp.cpp 
//an example of using templates

template <class T>
void sort ( T *a, int n )
{
  int changed;
  T temp;

  do {
    changed = 0;
    for ( int i = 0; i < n - 1; i++ ) {
      if ( a[i+1] < a[i] ) {
	temp = a[i];
	a[i] = a[i+1];
	a[i+1] = temp;
	changed = 1;
      }
    } 
  } while ( changed );
}

#include "str.h"
#include <iostream>

int main()
{
  const int max = 10;
  int x[max] = {5, 6, 16, 9, 8, 20, 3, 12, 32, 28 };
  
  //sort integers
  sort ( x, max );
  for ( int i = 0; i < max; ++i )
    cout << x[i] << " , ";
  cout << endl;

  //sort strings
  String list[max] = { "The", "quick", "brown", "fox", "jumps", 
	"over", "the", "lazy", "dog,", "and" };
  sort ( list, max );
  for ( int i = 0; i < max; ++i )
    list[i].prints();

  //sort floats
  float f[max] = { 3, 1.4, 1.5, 9, 2.6, 5.3, 8.9, 2.7, 1.2, 4.0 };
  sort ( f, max );
  for ( int i = 0; i < max; ++i )
    cout << f[i] << " , ";
  cout << endl;
}

    2. Sorting

      a) Bubble Sort

      largest element bubbles to the top

      if ( data[i+1] < data[i] ) swap_data;

      index     data                  
      5
      4
      3
      2
      1
      0      		 2
      6
      3
      0
      4
      1      		 2
      6
      3
      0
      4
      1      		 2
      6
      3
      4
      0
      1      		 2
      6
      4
      3
      0
      1      		 2
      6
      4
      3
      0
      1      		 6
      2
      4
      3
      0
      1      		 |
      |
      |
      |
      |
      |      		 6
      2
      4
      3
      0
      1      		 6
      2
      4
      3
      1
      0      		 6
      2
      4
      3
      1
      0      		 6
      2
      4
      3
      1
      0      		 6
      4
      2
      3
      1
      0      		 |
      |
      |
      |
      |
      |      		 6
      4
      2
      3
      1
      0      		 6
      4
      2
      3
      1
      0      		 6
      4
      2
      3
      1
      0      		 6
      4
      3
      2
      1
      0

      complexity ~ O(n2)

      b) Selection Sort

      find index of largest element; put it on top ( swap with top element )

      index     data        
      5
      4
      3
      2
      1
      0      		   2
      6←
      3
      0
      4
      1      		 6
      2
      3
      0
      4←
      1      		 6
      4
      3←
      0
      2
      1      		 6
      4
      3
      0
      2←
      1      		 6
      4
      3
      2
      0
      1←      		 6
      4
      3
      2
      1
      0

      less swaps but more comparisons     O(n2 )

      c) Insertion Sort

      insert an element into the proper position of a sorted list by swapping

      index       data            
      5
      4
      3
      2
      1
      0      		 2
      6
      3
      0
      4
      1      		 2
      6
      3
      0
      4←
      1      		 2
      6
      3
      0←
      4
      1      		 2
      6
      3
      4
      0←
      1      		 2
      6
      3
      4
      1
      0      		 2
      6
      3←
      4
      1
      0      		 2
      6
      4
      3
      1
      0      		 2
      6←
      4
      3
      1
      0      		 2
      6
      4
      3
      1
      0      		 2←
      6
      4
      3
      1
      0      		 6
      2←
      4
      3
      1
      0      		 6
      4
      2←
      3
      1
      0      		 6
      4
      3
      2←
      1
      0      		 6
      4
      3
      2
      1
      0

      O(n2)

      d) Shell Sort

      The shell sort is a "diminishing increment sort", also known as a "comb sort".

      Shell Sort is basically a trick to make Insertion Sort run faster. It sorts the subsequences of elements spaced k elements apart. There are k such sequences starting at positions 0 through k-1 in the array. In these sorts, elements k positions apart are exchanged.

      That is, the algorithm makes multiple passes through the list, and each time sorts a number of equally sized sets using the insertion sort.

      e.g. we use insertion sort to sort elements 4 apart, 2 apart then 1 apart ( entire list )
      index       data   k = 4   k = 2   k = 1
      7
      6
      5
      4
      3
      2
      1
      0      		 8
      5
      2
      6
      3
      0
      4
      1      		 8
      5
      2
      6
      3
      0
      4
      1       		8
      5
      4
      6
      3
      0
      2
      1       		8
      5
      4
      6
      3
      0
      2
      1       		8
      6
      4
      5
      3
      1
      2
      0       		8
      6
      4
      5
      3
      1
      2
      0       		8
      6
      5
      4
      3
      2
      1
      0

      O(n2)


      Sorting algorithms with complexity O( n2 )

      e) Merge Sort

      The merge sort splits the list to be sorted into two equal halves, and places them in separate arrays. Each array is recursively sorted, and then merged back together to form the final sorted list. Like most recursive sorts, the merge sort has an algorithmic complexity of O(n log n).

      First divide,

        8   5   2   6     3   0   4   1  
        8   5   2   6  
        3   0   4   1  
        8   5
        2   6  
        3   0
        4   1  
        8     5     2     6  
        3     0     4     1  

      Then sort-and-merge
        5   8
        2   6  
        0   3
        1   4  
        2   5   6   8     0   1   3   4  
        0   1   2   3     4   5   6   8   

      //mergesort.cpp
#include "mergesort.h"

//center serves the end of first half and the beginning of second 
template <class Itr, class T>
void merge( Itr start, Itr center, Itr end, T &temp )
{
  Itr p1 = start;
  Itr p2 = center + 1;
  int n = end - start + 1;
  int j = 0;
  vector <T> v( n );
  while ( p1 <= center && p2 <= end ) {
    if ( *p1 < *p2 )
	v[j++] = *p1++;
    else
	v[j++] = *p2++;
  }
  //copy remaining ( only one while loop is executed )
  while ( p1 <= center )
	v[j++] = *p1++;
  while ( p2 <= end )
	v[j++] = *p2++;

  // copy back from the temporary vector 
   for (j = 0; j < n; j++)
      start[j] = v[j];
}

//typedef T *iterator;
template <class Itr, class T>
void m_sort ( Itr start, int low, int high, T &temp )
{
  //cout << "low = " << low << " high = " << high << endl;
  if ( low  < high ){
    int center = ( high + low ) / 2;
    m_sort ( start, low, center, temp );
    m_sort ( start, center+1, high, temp );
    merge( start + low, start + center, start + high, temp );
  }
}

template <class T>
void mergeSort( vector<T> &s )
{
  //vector<T> temp( s.size() ); //temporary storage
  T temp;               //to hold datatype
  m_sort( s.begin(), 0, s.size()-1, temp );
}

/*
 Unfortunaley, as of this date ( 10/03 ), we still cannot link 
 object files using template.  So I use  stubs to provide the 
 interface.
	T.L. Yu
*/

//sort integers
void sort_int( vector<int> &a )
{
  mergeSort ( a );
}

//sort double
void sort_double( vector<double> &a )
{
  mergeSort( a );
}

//sort string
void sort_string( vector<string> &a )
{
  mergeSort( a );
}
  

      //mergesort.h
//the following interfaces are exposed to users

#ifndef MERGESORT_H
#include <vector>
#include <string>

void sort_int( vector<int> &a );
void sort_double( vector<double> &a );
void sort_string( vector<string> &a );

#endif
  

      //mergemain.cpp
#include <vector>
#include <math.h>
#include <iostream>
#include <time.h>
#include <stdio.h>
#include "mergesort.h"


template <class T>
void print(vector<T> &a)
/* PURPOSE:  print all elements in a vector
   RECEIVES: a - the vector to print
*/ 
{  int i;   
   for (i = 0; i < a.size(); i++)
      cout << a[i] << " ";
   cout << "\n";
}

//demo of using mergesort
void main()
{
   /*
	sorting integers generated by random number generator
   */
   int seed = static_cast<int>(time(0));
   srand(seed);
   vector<int> v(20);
   time_t  time_before, time_after;	//to time the sorting time
   for ( int i = 0; i < v.size(); i++)
      v[i] = rand() % 100;
   print( v );
   time_before = time ( ( time_t * ) 0 );//get time and date in seconds
   sort_int( v );
   time_after = time ( ( time_t * ) 0 );//get time and date in seconds
   print(v);
   cout << "Time to sort " << v.size() << " integers is: "
	<< time_after - time_before << " seconds" << endl; 

  /*
	Sort strings
	Use text file "mergesort.cpp" as source of input strings
  */
  static char buffer[100];
  vector<string> vs;		//vector to hold strings	
  FILE *fp;
  if ( ( fp = fopen ( "mergesort.cpp", "rt" )) == NULL  ){
    cout << "Error opening file mergesort.cpp. " << endl;
    return 1;
  }
  while ( fscanf( fp,  "%s", buffer ) != EOF )
    vs.push_back( string ( buffer ) );  //push word read into vector
  sort_string( vs );
  cout << "Sorted text: *************" << endl;
  print ( vs );
}

      Complexity ~ O( nlog(n) )


      Sorting algorithms with complexity O( nlog n )

    3. Vector Operations Summary 

      #include <vector>

vector <int> v1(10);
vector <int> v2(5, 2);	//5 elements, initial value 2
vector <int> v3;		//no element in vector
vector <int> v4(v2);		//copy of vector v2

v4[2] = 16;
v4.front();			//first element in vector
v4.back();			//last

v4.push_back( 6 );		//push element onto back of vector
  

      vector<int>::iterator itr;
for ( itr = v4.begin(); itr != v4.end();  ++itr )
{
  cout << *itr << ", " << endl;
}

itr = v4.begin();
itr += 3;

v4.insert( itr, 9 );
cout << v4[3];		//9
itr = v4.begin();
v4.erase( itr );
v4.erase( itr+1, itr+3 );

      Size, capacity, use with function objects. 

      #include <vector>
#include <algorithm>
#include <iostream>

//function object class
class ClargerInt {
  public:
    bool operator () ( int a, int b ) { return a > b; }
};
void print( vector <int> &a )
{
  for ( int i = 0; i < a.size(); i++ )
    cout << a[i] << ", ";
  cout << endl;
}

int main()
{
  vector<int> v(10);
  v.push_back( 8 );
  cout << "size: " << v.size() << endl;         //11
  cout << "capacity: " << v.capacity() << endl; //20
  v.push_back( 8 );
  cout << "size: " << v.size() << endl;         //12
  cout << "capacity: " << v.capacity() << endl; //20

  int seed = static_cast<int> ( time(0) );
  srand ( seed );
  for ( int i = 0; i < v.size(); i++ )
    v[i] = rand() % 100;
  print( v );
  sort ( v.begin(), v.end(), ClargerInt() );
  print( v );
}