Sorting Assignment

We have discussed two algorithms for sorting an array in increasing (or decreasing) order: Simple Search and Bubble Search. Both algorithms are of the same order of complexity, O(n²), but the Bubble Sort algorithm forms the basis of another sorting algorithm that can perform better. There are, actually, many sorting algorithms available, and you will study them in more detail in another class.

For this assignment, I have created the necessary functions to perform these searches below. You task is as follows:

	The Sort function below contains a loop that runs from start to end, going up. It calls a utility function findMinIndex to do the actual work. Change whatever necessary so that the for loop in the Sort function goes the "other way", i.e. down from end to start. It still should sort the array in exactly the same order as before.
	The BubbleSort function below contains a loop that runs from end-1 to 1, going down. It calls a utility function bubbleSortPhase to do the actual work. Change whatever necessary so that the for loop in the BubbleSort function goes the "other way", i.e. this time it should go from 1 (or perhaps 0) up to end (or perhaps end - 1).

Here is the source code for the two sort algorithms we discussed (Note that there is a slight mistake somewhere in this code that will result in nor sorting the entire array .... finding and fixing that mistake would be part of the assignment ....):

#include <iostream.h>
#include <limits.h>
#include <stdlib.h>
/* ****************************************************** */
void swap(double A[], int p1, int p2)
/* 
   Utility function to swap two elements in the array A 
*/
{
  double X = A[p1];
  A[p1] = A[p2];
  A[p2] = X;
}
/* ****************************************************** */
int findMinIndex(double A[], int start, int end)
/* 
   Utility function to find the minimum index in an array
   starting at 'start' and ending at 'end'
*/
{
  int min = start;
  for (int i = start; i <= end; i++)
    if (A[i] < A[min])
      min = i;
  return min;
}
/* ****************************************************** */
void Sort(double A[], int start, int end)
/*
   Simple sort function. Will sort array A in increasing
   order
*/
{
   for (int i = start; i <= end; i++)
     {
       int min = findMinIndex(A, i, end);
       swap(A, i, min);
     }
}
/* ****************************************************** */
void bubbleSortPhase(double A[], int last)
/*
   Utility function for bubble sort: goes once through the
   array A and switches adjacent elementsif necessary
*/
{
  for (int pos = 0; pos < last - 1; pos++)
    if (A[pos] > A[pos+1])
      swap(A, pos, pos+1);
}
/* ****************************************************** */
void bubbleSort(double A[], int start, int end)
/*
   Bubble Sort function: will sort the array A in increasing
   order
*/
{
  for (int i = end-1; i > 0; i--)
    bubbleSortPhase(A, i);
}
/* ****************************************************** */
void initArray(double A[], int N)
/*
    Utilit function to create a random double array
*/
{
   randomize();
   for (int i = 0; i < N; i++)
      A[i] = random(100);
}
/* ****************************************************** */
void display(double A[], int size)
{
  for (int i = 0; i < size; i++)
  {
    cout << A[i] << "\t";
    if (((i+1) % 4) == 0)
       cout << "\n";
  }
  cout << "\n\n";
}
/* ****************************************************** */
int main(void)
/* 
   Testing the sort functions
*/
{
  const int SIZE = 40;
  double A[SIZE];
  initArray(A, SIZE);
  cout << "Sorting array with simple sort " << endl;
  Sort(A, 0, SIZE-1);
  display(A, SIZE);
  initArray(A, SIZE);
  cout << "Sorting array with bubble sort " << endl;
  bubbleSort(A, 0, SIZE-1);
  display(A, SIZE);

  return 0;
}