Solution 04
[ Home ] [ Up ]

//Project04_pizza04.cpp
//Authors: AOU
//Date 04/07/2002

// Includes solution to project #4

//Project #4
//Write pure recursive version of sortSelection1
//Due 4/3/2002

/////////////////////////////////////////////////////////////////
// include files
/////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <time.h>
#include <stdlib.h>


/////////////////////////////////////////////////////////////////
// constants
/////////////////////////////////////////////////////////////////
const int MAX_COUNT = 20;


/////////////////////////////////////////////////////////////////
// prototypes
/////////////////////////////////////////////////////////////////
void sortBubble(int array[], int low, int high);
void displayArray1(int array[], int low, int high);
void displayArray2(int array[], int low, int high);
int min1(int array[], int low, int high);
int min2(int array[], int low, int high);
void sortSelection1(int array[], int low, int high);
void buildArray(int array[], int &low, int &high);
bool isSorted(int array[], int low, int high);
void sortSelection2(int array[], int low, int high);


/////////////////////////////////////////////////////////////////
// main
/////////////////////////////////////////////////////////////////
void main(void)
  {
  srand(time(NULL));
  int a[MAX_COUNT], low, high;

  for (int i=1; i<=10; i++)
    {
    int k;
    buildArray(a, low, high);

    displayArray1(a, low, high);
    k = min1(a, low, high);
    cout << "minimum is at " << k << ": " << a[k] << endl;

    if (isSorted(a, low, high))
        cout << "array is sorted\n";
      else
        cout << "array is NOT sorted\n";

    sortSelection2(a, low, high); 

    k = min2(a, low, high);
    cout << "minimum is at " << k << ": " << a[k] << endl;

    cout << "After sort\n";
    displayArray2(a, low, high);

    if (isSorted(a, low, high))
        cout << "array is sorted\n";
      else
        cout << "array is NOT sorted\n";
    cout << "=================================\n";

    }
  }


/////////////////////////////////////////////////////////////////
// sortSelection2
/////////////////////////////////////////////////////////////////
void sortSelection2(int array[], int low, int high)
  {
  if (low == high)
      return;
    else
      {
      //find the index of minimum from i to high in k
      int k = min2(array, low, high);
      //swap values at k and low
      int tValue = array[low];
      array[low] = array[k];
      array[k] = tValue;
      //call sortSelection2 recursively ignoring the value at low
      sortSelection2(array, low+1, high);
      }
  }


/////////////////////////////////////////////////////////////////
// buildArray
/////////////////////////////////////////////////////////////////
void buildArray(int array[], int &low, int &high)
  {
  low = 0;
  high = rand()%MAX_COUNT;
  for (int i=0; i<=high; i++)
    array[i] = 10 + rand()%90;
  }


/////////////////////////////////////////////////////////////////
// isSorted
/////////////////////////////////////////////////////////////////
bool isSorted(int array[], int low, int high)
  {
  for (int i=low; i<high; i++)
    if (array[i] > array[i+1]) 
      return false;

  return true;
  }


/////////////////////////////////////////////////////////////////
// sortSelection1
/////////////////////////////////////////////////////////////////
/*Example:
  {3, 2, 1, 6, 4}
  1, {2, 3, 6, 4}
  1, 2, {3, 6, 4}
  1, 2, 3, {6, 4}
  1, 2, 3, 4, {6}

  Plan:
    Find the position of the minimum value
    swap it with the fist value
    ignore the first value
    do the same thing with the remaining values

    do the following for i=low to high-1
      find the index of minimum from i to high in k
      swap values at k and i
      end do
*/
void sortSelection1(int array[], int low, int high)
  {
  for (int i=low; i<=high-1; i++)
    {
    //find the index of minimum from i to high in k
    int k = min1(array, i, high);
    //swap values at k and i
    int tValue = array[k];
    array[k] = array[i];
    array[i] = tValue;
    }
  }


/////////////////////////////////////////////////////////////////
// min1 to return the index of minimum value (non-recursive)
/////////////////////////////////////////////////////////////////
int min1(int array[], int low, int high)
  {
  /*
  index of the minimum value?
  minYet = low
  compare value at minYet with every value in the list 
    if a value is < value at minYet then
       copy index of that value to minYet

  return minYet
  */
  /*
  minYet = low
  for i= low to high
    if array[i] < array[minYet]
       minYest = i

  return minYet
  */
  int minYet = low;
  for (int i= low; i<=high; i++)
    if (array[i] < array[minYet])
       minYet = i;

  return minYet;
  }


/////////////////////////////////////////////////////////////////
// min2 to return the index of minimum value (non-recursive)
/////////////////////////////////////////////////////////////////
int min2(int array[], int low, int high)
  {
  if (low == high)
      return low;
  
  int minYet1 = low;
  int minYet2 = min2(array, low+1, high);

  if (array[minYet1] < array[minYet2])
      return minYet1;
    else
      return minYet2;
  }


/////////////////////////////////////////////////////////////////
// displayArray1 to display array elements (non-recursive)
/////////////////////////////////////////////////////////////////
void displayArray1(int array[], int low, int high)
  {
  for (int i=low; i<= high; i++)
    cout << array[i] << ' ';

  cout << endl;
  }


/////////////////////////////////////////////////////////////////
// displayArray2 to display array elements (recursive)
/////////////////////////////////////////////////////////////////
void displayArray2(int array[], int low, int high)
  {
  /*
  if only one element to be printed then
      print that element
    else
      print the fist element
      display the rest

  -----------------------
  if low and high are the same
      print element at low
    else
      print element at low
      display (array, low+1, high)

  */
  if (low == high)
      cout << array[low] << endl;
    else
      {
      cout << array[low] << ' ';
      displayArray2(array, low+1, high);
      }
  }


/////////////////////////////////////////////////////////////////
// sortBubble to sort array elements (non-recursive)
/////////////////////////////////////////////////////////////////
void sortBubble(int array[], int low, int high)
  {
  bool sorted;
  do
    {
    sorted = true;
    for (int i=low; i<high; i++)
      {
      if (array[i] > array[i+1])
        {
        int temp = array[i];
        array[i] = array[i+1];
        array[i+1] = temp;
        sorted = false;
        }
      }
    }
    while (!sorted);
  }