/*
 **************************************************************************
 * Program name : 040_Bubble_sort (Version 1.00)                          *
 * Author       : Duck Wong                                               *
 * Language     : C / C++                                                 *
 * Compiler     : Boodshed Dec-C++ compiler Ver 3.95                      *
 * Computer     : PII350                                                  *
 * O/S          : Windows 98                                              *
 **************************************************************************
 * Version 1.00 : 2000/06/15 - first version                              *
 **************************************************************************
 * Description  : (a) Input a list of numbers                             *
 *                (b) Sort the list by bubble sort                        *
 *                (c) Try again ?                                         *
 **************************************************************************
*/
#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>

void bubblesort(int [], const int);

int main()
{
 // part 1 : declaration
 int   Index;                        // loop counter
 const int Arraysize=15;             // Maximum no. of element 15
 int   Number[Arraysize];            // Define the array Number
 char  Again;                        // Try again ?

 do {
     // part 2 : Input 15 real numbers
     cout << "\n\t\tBubble Sort (Version 1.00)\n";
     cout << "\nPlease input 15 integer numbers (1 - 99), then this program"
          << "\nwill printed the list in both unsorted and sorted orders.\n\n";
     for (Index=1; Index<=Arraysize; Index++)
       do
         {
          cout << "The #" << Index << " number is : ";
          cin  >> Number[Index-1];
         } while ((Number[Index-1]<1) || (Number[Index-1]>99));

     // part 3 : List in unsorted order
     cout << "\n\nThe unsorted list is : \n";
     for (Index=1; Index<=Arraysize; Index++)
       {
        cout << Number[Index-1];
        if (Index<Arraysize) cout << ", ";
       }

     // part 4 : List in sorted order
     cout << "\n\nThe sorted list is : \n";
     bubblesort(Number, Arraysize);
     for (Index=1; Index<=Arraysize; Index++)
       {
        cout << Number[Index-1];
        if (Index<Arraysize) cout << ", ";
       }

     // part 5 : try another number ?
     cout << "\n\n\t\aTry another set of numbers (Y/N) : ";
     cin  >> Again;
     cout << "\n";
    }while (Again=='Y' || Again=='y');
 cout << "\n" << endl;

 system("PAUSE");
 return 0;
}


void bubblesort(int Number[], int Arraysize)                         // Note (1)
{
 int Index_1, Index_2, tempint;
 char swap;

 for (Index_1=1; Index_1<Arraysize; Index_1++)
   {
    swap = 'N';
    for (Index_2=0; Index_2<Arraysize-Index_1; Index_2++)
      if (Number[Index_2]>Number[Index_2+1])
        {
         tempint = Number[Index_2];
         Number[Index_2] = Number[Index_2+1];
         Number[Index_2+1] = tempint;
         swap = 'Y';
        }
    if (swap=='N') break;                                            // Note (2)
   }
}

/* Notes
   (1) The technique I use is "Bubble sort". Every pass, the largest number
       in the unsorted list to moved to the begining of the sorted list.

       Example :

       Pass             |  Unsorted Numbers     | Sorted elements
       -----------------|-----------------------|------------------------
       Before sorting   |  25, 12, 34, 64, 20   |
       1st pass         |  12, 25, 34, 20       |                 64
       2nd pass         |  12, 25, 20           |             34, 64
       3rd pass         |  12, 20               |         25, 34, 64
       4th pass         |  12                   |     20, 25, 34, 64
       End of sorting   |                       | 12, 20, 25, 34, 64
       -----------------|-----------------------|------------------------
       No. of pass is equal to no. of item less one.

   (2) The data in the array may already be in the proper order or near-proper
       order, so the program should terminate if swap has not been made during
       any pass.
*/