////////////////////////////////////////////////////
// File: BubbleSort.cpp - Demonstrate bubble sort //
////////////////////////////////////////////////////

#include <iostream>

using namespace std;

void Display(char* title, const int numbers[], const int length);
int BubbleSort(int numbers[], const int length);


int main()
{
    int numbers[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9 };
    const int LENGTH = sizeof numbers / sizeof numbers[0];

    cout << "\nDemonstrate BubbleSort\n\n";
    Display("before: ", numbers, LENGTH);
    int numPasses = BubbleSort(numbers, LENGTH);
    Display("after:  ", numbers, LENGTH);
    cout << endl << numPasses << " passes were required" << endl;

    cout << endl << endl;
    return 0;
}

//////////////////////////////////////////
// Display the contents of an int array //
//////////////////////////////////////////

void Display(char* title, const int numbers[], const int length)
{
    cout << "\n" << title;
    for (int i = 0; i < length; i++)
        cout << " " << numbers[i];
    cout << endl;
}


///////////////////////////////////////////////////////
// Sort an int array using the bubble sort algorithm //
// Returns the number of passes used                 //
///////////////////////////////////////////////////////

int BubbleSort(int numbers[], const int length)
{
    int index  = 0;
    int lth    = length - 1;
    bool bDone = false;

    while (! bDone)
    {
        bDone = true;
        for (int scan = 0; scan < lth; scan++) {
            if (numbers[scan] > numbers[scan+1]) {
                // Swap the values
                int temp = numbers[scan];
                numbers[scan] = numbers[scan+1];
                numbers[scan+1] = temp;
                bDone = false;
            }
        }
        --lth;
    }

    return length - lth - 1;
}

/* ========== Runtime Output ==========

Demonstrate BubbleSort


before:  3 1 4 1 5 9 2 6 5 3 5 8 9 7 9

after:   1 1 2 3 3 4 5 5 5 6 7 8 9 9 9

6 passes were required

========== End Output ========== */