//Ryan Shahriyarpour   CS1A  Chapter 8   Question 6
/*****************************************************************************
 * 
 * String Selection Sort
 * 
 *********************
 * 
 * This program uses a selection sort, changed to work on strings instead
 * of ints, to put a list of 20 names in alphabetical order. The names are
 * displayed before and after the sort.
 * 
 * *******************
 * Selection sort: for each position in the array, find the smallest value
 * in the part of the array that has not been sorted yet and swap it into
 * that position. Strings are compared with < which orders them
 * alphabetically.
 * 
 * INPUT
 *  None (the names are stored in the program)
 * 
 * OUTPUT    
 *  The list of names before sorting and again after sorting
 * 
 ****************************************************************************/
 
#include <iostream>
#include <string>
using namespace std;
 
// Constant for the number of names
const int NUM_NAMES = 20;
 
// Function prototype
void selectionSort(string array[], int size);
 
int main()
{
    // data dictionary
    string names[NUM_NAMES] = {     // Names to be sorted
        "Collins, Bill", "Smith, Bart", "Allen, Jim", "Griffin, Jim",
        "Stamey, Marty", "Rose, Geri", "Taylor, Terri", "Johnson, Jill",
        "Allison, Jeff", "Looney, Joe", "Wolfe, Bill", "James, Jean",
        "Weaver, Jim", "Pore, Bob", "Rutherford, Greg", "Javens, Renee",
        "Harrison, Rose", "Setzer, Cathy", "Pike, Gordon", "Holland, Beth"
    };
    int index;                      // Loop counter for displaying the names
 
    // Display the names before sorting
    cout << "Names before sorting:" << endl;
    for (index = 0; index < NUM_NAMES; index++)
        cout << "  " << names[index] << endl;
 
    // Sort the names
    selectionSort(names, NUM_NAMES);
 
    // Display the names after sorting
    cout << "\nNames after sorting:" << endl;
    for (index = 0; index < NUM_NAMES; index++)
        cout << "  " << names[index] << endl;
 
    return 0;
}
 
// Sorts an array of strings into alphabetical order
void selectionSort(string array[], int size)
{
    // data dictionary
    int startScan;                  // Position being filled on this pass
    int index;                      // Loop counter that scans for the smallest
    int minIndex;                   // Index of the smallest string found
    string minValue;                // The smallest string found
 
    for (startScan = 0; startScan < size - 1; startScan++)
    {
        minIndex = startScan;
        minValue = array[startScan];
        for (index = startScan + 1; index < size; index++)
        {
            if (array[index] < minValue)
            {
                minValue = array[index];
                minIndex = index;
            }
        }
        array[minIndex] = array[startScan];
        array[startScan] = minValue;
    }
}

Ly9SeWFuIFNoYWhyaXlhcnBvdXIgICBDUzFBICBDaGFwdGVyIDggICBRdWVzdGlvbiA2Ci8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKgogKiAKICogU3RyaW5nIFNlbGVjdGlvbiBTb3J0CiAqIAogKioqKioqKioqKioqKioqKioqKioqCiAqIAogKiBUaGlzIHByb2dyYW0gdXNlcyBhIHNlbGVjdGlvbiBzb3J0LCBjaGFuZ2VkIHRvIHdvcmsgb24gc3RyaW5ncyBpbnN0ZWFkCiAqIG9mIGludHMsIHRvIHB1dCBhIGxpc3Qgb2YgMjAgbmFtZXMgaW4gYWxwaGFiZXRpY2FsIG9yZGVyLiBUaGUgbmFtZXMgYXJlCiAqIGRpc3BsYXllZCBiZWZvcmUgYW5kIGFmdGVyIHRoZSBzb3J0LgogKiAKICogKioqKioqKioqKioqKioqKioqKgogKiBTZWxlY3Rpb24gc29ydDogZm9yIGVhY2ggcG9zaXRpb24gaW4gdGhlIGFycmF5LCBmaW5kIHRoZSBzbWFsbGVzdCB2YWx1ZQogKiBpbiB0aGUgcGFydCBvZiB0aGUgYXJyYXkgdGhhdCBoYXMgbm90IGJlZW4gc29ydGVkIHlldCBhbmQgc3dhcCBpdCBpbnRvCiAqIHRoYXQgcG9zaXRpb24uIFN0cmluZ3MgYXJlIGNvbXBhcmVkIHdpdGggPCB3aGljaCBvcmRlcnMgdGhlbQogKiBhbHBoYWJldGljYWxseS4KICogCiAqIElOUFVUCiAqICBOb25lICh0aGUgbmFtZXMgYXJlIHN0b3JlZCBpbiB0aGUgcHJvZ3JhbSkKICogCiAqIE9VVFBVVCAgICAKICogIFRoZSBsaXN0IG9mIG5hbWVzIGJlZm9yZSBzb3J0aW5nIGFuZCBhZ2FpbiBhZnRlciBzb3J0aW5nCiAqIAogKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KIAojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxzdHJpbmc+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKLy8gQ29uc3RhbnQgZm9yIHRoZSBudW1iZXIgb2YgbmFtZXMKY29uc3QgaW50IE5VTV9OQU1FUyA9IDIwOwogCi8vIEZ1bmN0aW9uIHByb3RvdHlwZQp2b2lkIHNlbGVjdGlvblNvcnQoc3RyaW5nIGFycmF5W10sIGludCBzaXplKTsKIAppbnQgbWFpbigpCnsKICAgIC8vIGRhdGEgZGljdGlvbmFyeQogICAgc3RyaW5nIG5hbWVzW05VTV9OQU1FU10gPSB7ICAgICAvLyBOYW1lcyB0byBiZSBzb3J0ZWQKICAgICAgICAiQ29sbGlucywgQmlsbCIsICJTbWl0aCwgQmFydCIsICJBbGxlbiwgSmltIiwgIkdyaWZmaW4sIEppbSIsCiAgICAgICAgIlN0YW1leSwgTWFydHkiLCAiUm9zZSwgR2VyaSIsICJUYXlsb3IsIFRlcnJpIiwgIkpvaG5zb24sIEppbGwiLAogICAgICAgICJBbGxpc29uLCBKZWZmIiwgIkxvb25leSwgSm9lIiwgIldvbGZlLCBCaWxsIiwgIkphbWVzLCBKZWFuIiwKICAgICAgICAiV2VhdmVyLCBKaW0iLCAiUG9yZSwgQm9iIiwgIlJ1dGhlcmZvcmQsIEdyZWciLCAiSmF2ZW5zLCBSZW5lZSIsCiAgICAgICAgIkhhcnJpc29uLCBSb3NlIiwgIlNldHplciwgQ2F0aHkiLCAiUGlrZSwgR29yZG9uIiwgIkhvbGxhbmQsIEJldGgiCiAgICB9OwogICAgaW50IGluZGV4OyAgICAgICAgICAgICAgICAgICAgICAvLyBMb29wIGNvdW50ZXIgZm9yIGRpc3BsYXlpbmcgdGhlIG5hbWVzCiAKICAgIC8vIERpc3BsYXkgdGhlIG5hbWVzIGJlZm9yZSBzb3J0aW5nCiAgICBjb3V0IDw8ICJOYW1lcyBiZWZvcmUgc29ydGluZzoiIDw8IGVuZGw7CiAgICBmb3IgKGluZGV4ID0gMDsgaW5kZXggPCBOVU1fTkFNRVM7IGluZGV4KyspCiAgICAgICAgY291dCA8PCAiICAiIDw8IG5hbWVzW2luZGV4XSA8PCBlbmRsOwogCiAgICAvLyBTb3J0IHRoZSBuYW1lcwogICAgc2VsZWN0aW9uU29ydChuYW1lcywgTlVNX05BTUVTKTsKIAogICAgLy8gRGlzcGxheSB0aGUgbmFtZXMgYWZ0ZXIgc29ydGluZwogICAgY291dCA8PCAiXG5OYW1lcyBhZnRlciBzb3J0aW5nOiIgPDwgZW5kbDsKICAgIGZvciAoaW5kZXggPSAwOyBpbmRleCA8IE5VTV9OQU1FUzsgaW5kZXgrKykKICAgICAgICBjb3V0IDw8ICIgICIgPDwgbmFtZXNbaW5kZXhdIDw8IGVuZGw7CiAKICAgIHJldHVybiAwOwp9CiAKLy8gU29ydHMgYW4gYXJyYXkgb2Ygc3RyaW5ncyBpbnRvIGFscGhhYmV0aWNhbCBvcmRlcgp2b2lkIHNlbGVjdGlvblNvcnQoc3RyaW5nIGFycmF5W10sIGludCBzaXplKQp7CiAgICAvLyBkYXRhIGRpY3Rpb25hcnkKICAgIGludCBzdGFydFNjYW47ICAgICAgICAgICAgICAgICAgLy8gUG9zaXRpb24gYmVpbmcgZmlsbGVkIG9uIHRoaXMgcGFzcwogICAgaW50IGluZGV4OyAgICAgICAgICAgICAgICAgICAgICAvLyBMb29wIGNvdW50ZXIgdGhhdCBzY2FucyBmb3IgdGhlIHNtYWxsZXN0CiAgICBpbnQgbWluSW5kZXg7ICAgICAgICAgICAgICAgICAgIC8vIEluZGV4IG9mIHRoZSBzbWFsbGVzdCBzdHJpbmcgZm91bmQKICAgIHN0cmluZyBtaW5WYWx1ZTsgICAgICAgICAgICAgICAgLy8gVGhlIHNtYWxsZXN0IHN0cmluZyBmb3VuZAogCiAgICBmb3IgKHN0YXJ0U2NhbiA9IDA7IHN0YXJ0U2NhbiA8IHNpemUgLSAxOyBzdGFydFNjYW4rKykKICAgIHsKICAgICAgICBtaW5JbmRleCA9IHN0YXJ0U2NhbjsKICAgICAgICBtaW5WYWx1ZSA9IGFycmF5W3N0YXJ0U2Nhbl07CiAgICAgICAgZm9yIChpbmRleCA9IHN0YXJ0U2NhbiArIDE7IGluZGV4IDwgc2l6ZTsgaW5kZXgrKykKICAgICAgICB7CiAgICAgICAgICAgIGlmIChhcnJheVtpbmRleF0gPCBtaW5WYWx1ZSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbWluVmFsdWUgPSBhcnJheVtpbmRleF07CiAgICAgICAgICAgICAgICBtaW5JbmRleCA9IGluZGV4OwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGFycmF5W21pbkluZGV4XSA9IGFycmF5W3N0YXJ0U2Nhbl07CiAgICAgICAgYXJyYXlbc3RhcnRTY2FuXSA9IG1pblZhbHVlOwogICAgfQp9