// Marvyn Jesse De La Torre CS1A Chapter 8 #10 pg.489
//
/*************************************************************
* Determine Sorting Orders
*
* This program accepts eight integers using bubble sort
* and selection sort. It displays the array after each pass.
*
* Input:
* Eight integers entered by the user
*
* Output:
* Displays the original array and the results of each pass.
*************************************************************/
#include <iostream>
using namespace std;
void bubble(int arr[], int size);
void selection(int arr[], int size);
void print(int arr[], int size);
void swap(int &a, int &b);
int main()
{
const int SIZE = 8;
int arr[SIZE];
int arr2[SIZE];
cout << "Enter eight numbers: ";
for (int i = 0; i < SIZE; i++)
{
cin >> arr[i];
arr2[i] = arr[i];
}
cout << endl << "Original array: ";
print(arr, SIZE);
cout << endl << endl << "Bubble Sort:" << endl;
bubble(arr, SIZE);
cout << endl << "Selection Sort:" << endl;
selection(arr2, SIZE);
return 0;
}
void bubble(int arr[], int size)
{
for (int i = size - 1; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
}
}
cout << "Pass: ";
print(arr, size);
cout << endl;
}
}
void selection(int arr[], int size)
{
for (int start = 0; start < size - 1; start++)
{
int minIndex = start;
for (int i = start + 1; i < size; i++)
{
if (arr[i] < arr[minIndex])
{
minIndex = i;
}
}
swap(arr[minIndex], arr[start]);
cout << "Pass: ";
print(arr, size);
cout << endl;
}
}
void print(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
}
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
Ly8gTWFydnluIEplc3NlIERlIExhIFRvcnJlICAgICAgICBDUzFBICAgICAgIENoYXB0ZXIgOCAjMTAgcGcuNDg5Ci8vCi8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqCiogRGV0ZXJtaW5lIFNvcnRpbmcgT3JkZXJzCioKKiBUaGlzIHByb2dyYW0gYWNjZXB0cyBlaWdodCBpbnRlZ2VycyB1c2luZyBidWJibGUgc29ydAoqIGFuZCBzZWxlY3Rpb24gc29ydC4gSXQgZGlzcGxheXMgdGhlIGFycmF5IGFmdGVyIGVhY2ggcGFzcy4KKgoqIElucHV0OgoqICAgRWlnaHQgaW50ZWdlcnMgZW50ZXJlZCBieSB0aGUgdXNlcgoqCiogT3V0cHV0OgoqICAgRGlzcGxheXMgdGhlIG9yaWdpbmFsIGFycmF5IGFuZCB0aGUgcmVzdWx0cyBvZiBlYWNoIHBhc3MuCioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCgojaW5jbHVkZSA8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIGJ1YmJsZShpbnQgYXJyW10sIGludCBzaXplKTsKdm9pZCBzZWxlY3Rpb24oaW50IGFycltdLCBpbnQgc2l6ZSk7CnZvaWQgcHJpbnQoaW50IGFycltdLCBpbnQgc2l6ZSk7CnZvaWQgc3dhcChpbnQgJmEsIGludCAmYik7CgppbnQgbWFpbigpCnsKICAgIGNvbnN0IGludCBTSVpFID0gODsKICAgIGludCBhcnJbU0laRV07CiAgICBpbnQgYXJyMltTSVpFXTsKCiAgICBjb3V0IDw8ICJFbnRlciBlaWdodCBudW1iZXJzOiAiOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgU0laRTsgaSsrKQogICAgewogICAgICAgIGNpbiA+PiBhcnJbaV07CiAgICAgICAgYXJyMltpXSA9IGFycltpXTsKICAgIH0KCiAgICBjb3V0IDw8IGVuZGwgPDwgIk9yaWdpbmFsIGFycmF5OiAiOwogICAgcHJpbnQoYXJyLCBTSVpFKTsKCiAgICBjb3V0IDw8IGVuZGwgPDwgZW5kbCA8PCAiQnViYmxlIFNvcnQ6IiA8PCBlbmRsOwogICAgYnViYmxlKGFyciwgU0laRSk7CgogICAgY291dCA8PCBlbmRsIDw8ICJTZWxlY3Rpb24gU29ydDoiIDw8IGVuZGw7CiAgICBzZWxlY3Rpb24oYXJyMiwgU0laRSk7CgogICAgcmV0dXJuIDA7Cn0KCnZvaWQgYnViYmxlKGludCBhcnJbXSwgaW50IHNpemUpCnsKICAgIGZvciAoaW50IGkgPSBzaXplIC0gMTsgaSA+IDA7IGktLSkKICAgIHsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IGk7IGorKykKICAgICAgICB7CiAgICAgICAgICAgIGlmIChhcnJbal0gPiBhcnJbaiArIDFdKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBzd2FwKGFycltqXSwgYXJyW2ogKyAxXSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGNvdXQgPDwgIlBhc3M6ICI7CiAgICAgICAgcHJpbnQoYXJyLCBzaXplKTsKICAgICAgICBjb3V0IDw8IGVuZGw7CiAgICB9Cn0KCnZvaWQgc2VsZWN0aW9uKGludCBhcnJbXSwgaW50IHNpemUpCnsKICAgIGZvciAoaW50IHN0YXJ0ID0gMDsgc3RhcnQgPCBzaXplIC0gMTsgc3RhcnQrKykKICAgIHsKICAgICAgICBpbnQgbWluSW5kZXggPSBzdGFydDsKCiAgICAgICAgZm9yIChpbnQgaSA9IHN0YXJ0ICsgMTsgaSA8IHNpemU7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGlmIChhcnJbaV0gPCBhcnJbbWluSW5kZXhdKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBtaW5JbmRleCA9IGk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHN3YXAoYXJyW21pbkluZGV4XSwgYXJyW3N0YXJ0XSk7CgogICAgICAgIGNvdXQgPDwgIlBhc3M6ICI7CiAgICAgICAgcHJpbnQoYXJyLCBzaXplKTsKICAgICAgICBjb3V0IDw8IGVuZGw7CiAgICB9Cn0KCnZvaWQgcHJpbnQoaW50IGFycltdLCBpbnQgc2l6ZSkKewogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzaXplOyBpKyspCiAgICB7CiAgICAgICAgY291dCA8PCBhcnJbaV0gPDwgIiAiOwogICAgfQp9Cgp2b2lkIHN3YXAoaW50ICZhLCBpbnQgJmIpCnsKICAgIGludCB0ZW1wID0gYTsKICAgIGEgPSBiOwogICAgYiA9IHRlbXA7Cn0=