////////////////////////////////////////////////////////////////////////////////

// Author: Julie Petrusa (991339)                                             //

// Due date: February 26, 2002                                                //

// This program addresses a very common problem in processing arrays: sorting //

// an array to rearrange the elements in sequence. It first implements a very //

// intuitive but not very efficient sorting algorithm called selection sort.  //

// This algorithm is implemented both iteratively and recursively. It then    //

// implements the fastest known sorting algorithm called quick-sort.          //

// Known bugs: none                                                           //

////////////////////////////////////////////////////////////////////////////////

#include <iostream.h>      // needed in order to do I/O

#include <stdlib.h>        // for system("PAUSE")





class Sort

   {

   //---------------------------------------------------------------------------

   // fields

         private: int array[100];         // array of numbers

         private: int size;               // size of array

         private: int front;              // index of first element in array

         private: int rear;               // index of last element in array

   //---------------------------------------------------------------------------

   // constructor

         public: Sort()

            {

            }

   //---------------------------------------------------------------------------

   // function getNumbers

   // -gets the array of numbers from the console

         public: int getNumbers()

            {

            cout << "\nHow many numbers do you want to sort?: ";

            cin >> size;

            front = 0;

            rear = size-1;

            if (size > 100)

               cout << "\n\tMaximum size is 100!\n\n";

            for (int i=front; i<size; i++)

               {

               cout << "Enter number #" << (i+1) << " : ";

               cin >> array[i];

               }

            return rear;

            }

   //---------------------------------------------------------------------------

   // function iSelection

   // -iterative selection sort

   // -to perform a selection sort on an array of n elements, it locates the

   //  smallest element in the array and then exchanges this element with the

   //  first element (element with subscript 0)

   // -it then locates the smallest element in the remainder of the array (the

   //  sub-array with subscripts from 1 through n-1) and exchanges it with the

   //  first element of this sub-array

   // -this processing is continued until all the array elements are sorted in

   //  ascending order

   // -the computational complexity of this sorting algorithm is of order O(n2)

   // -it uses the strategy of locating smallest elements

         public: void iSelection()

            {

            int min;

            int b;

            for (int a=0; a<size-1; a++)

               {

               b = a;

               min = array[b];               // get the current value

               for (int j=a+1; j<size; j++)

                  {

                  if (array[j] < min)

                     {

                     b = j;

                     min = array[b];         // if yes, then get it

                     }

                  }

               array[b] = array[a];

               array[a] = min;

               }

            }

   //---------------------------------------------------------------------------

   // function rSelection

   // -recursive selection sort

   // -the computational complexity of this sorting algorithm is of order O(n2)

   // -it uses the strategy of locating the largest element for each sub-array

         public: void rSelection()

            {

            int temp;

            int maxIndex;

            if (front <= rear)

               {

               maxIndex = findmax();

               temp = array[maxIndex];         // largest into last

               array[maxIndex] = array[rear];

               array[rear] = temp;

               rear--;

               rSelection();

               }

            }

   //---------------------------------------------------------------------------

   // function findmax

   // -used by the recursive selection sort function to locate the largest

   //  element for each sub-array

         public: int findmax()

            {

            int maxIndex = rear;

            int max = array[rear];

            for (int i=rear-1; i>=front; i--)

               if (array[i] > max)

                  {

	               max = array[i];

	               maxIndex = i;

                  }

            return maxIndex;

            }

   //---------------------------------------------------------------------------

   // function quick

   // -quick sort (recursive)

   // -the basic Quicksort(S) algorithm consists of the following four steps:

   //    1. If the number of elements in S is 0 or 1, then return.

   //    2. Pick any element P in S. This is called the pivot.

   //    3. Partition S-{P} (the remaining elements in S) into two disjoint

   //       groups: L = {x e S-{P} | x <= P} and R = {x e S-{P} | x >= P}.

   //    4. Return the result of Quicksort(L) followed by P followed by

   //       Quicksort(R).

   // -the computational complexity of this sorting algorithm is of order

   //  O(nlogn)

         public: void quick(int front, int rear)

            {

            int pos;            // position of pivot

            if (front < rear)   // only sort if more than 1 element in list

               {

               split(front, rear, pos);    // split list into two sublists

               quick(front, pos-1);        // sort left sublist

               quick(pos+1, rear);         // sort right sublist

               }

            }

   //---------------------------------------------------------------------------

   // function split

   // -sorts all the sublists that quicksort creates

         public: void split(int front, int rear, int &pos)

            {

            int left;

            int temp;

            int pivot = array[front];  // pivot element

            int right = rear;          // index for right search

            left = front;              // index for left search

            while (left < right)

               {

               while (array[right] > pivot)

                  right--;             // search from right for element <= pivot

               while ((left < right) && (array[left] <= pivot))

                  left++;              // search from left for element > pivot

               if (left < right)       // interchange elements if searches

                  {                    // have not met

                  temp = array[left];

                  array[left] = array[right];

                  array[right] = temp;

                  }

               }

            pos = right;     // end of searches, place pivot in correct position

            array[front] = array[pos];

            array[pos] = pivot;

            }

   //---------------------------------------------------------------------------

   // function display

   // -displays the sorted array for selection sort

         public: void display()

            {

            cout << "\n\tResult: ";

            for (int i=0; i<size; i++)

               cout << array[i] << " ";

            }

   //---------------------------------------------------------------------------

   };  // end Sort





int main()

   {

   cout << "\nAuthor: Julie Petrusa (991339).";  // display banner

   cout << "\nDue date: February 26, 2002.";

   cout << "\nThis program addresses a very common problem in processing ";

   cout << "arrays: sorting an\narray to rearrange the elements in sequence. ";

   cout << "It first implements a very\nintuitive but not very efficient ";

   cout << "sorting algorithm called selection sort. This\nalgorithm is ";

   cout << "implemented both iteratively and recursively. It then implements";

   cout << "\nthe fastest known sorting algorithm called quick-sort.";

   bool value = true;  // initialize for do-while loop

   do

      {

      cout << "\n\nChoose one of the following options:";  // display options

      cout << "\n   1 --> Iterative Selection Sort";

      cout << "\n   2 --> Recursive Selection Sort";

      cout << "\n   3 --> Recursive Quick Sort";

      cout << "\n   4 --> Exit the program";

      cout << "\nAnswer: ";

      int answer;

      cin >> answer;

      Sort isSort;    // create objects

      Sort rsSort;

      Sort qSort;

      switch (answer)

         {

         case 1:                     // iterative selection sort

            isSort.getNumbers();     // get array of numbers

            isSort.iSelection();     // sort array

            isSort.display();        // display array

            break;

         case 2:                     // recursive selection sort

            rsSort.getNumbers();     // get array of numbers

            rsSort.rSelection();     // sort array

            rsSort.display();        // display array

            break;

         case 3:                                 // quick sort (recursive)

            qSort.quick(0, qSort.getNumbers());  // get array of numbers, sort

            qSort.display();                     // display array

            break;

         case 4:

            value = false;  // to end do-while loop

            break;

         default:  // invalid answer, display error message

            cout << "\n\tInvalid answer!";

            break;

         }

      } while (value != false);

   cout << "\n";

   system("pause");  // to view console

   return 0;         // end main

   }                 // end SortingArrays