// Timothy Price CS1A Ch 8 Challenge 9
/******************************************************************************
* Compare sorting algorithms
*
* This program compares the performance of bubble sort and selection sort
* algorithms by sorting two identical arrays of unsorted integers and tracking
* the number of exchanges each algorithm makes.
*
* Inputs:
* Two identical arrays
* The fixed size of the array (20)
*
* Outputs:
* The original unsorted array displayed on the screen
* Bubble sort result and number of exchanges
* Selection sort result and number of exchanges
*****************************************************************************/
#include <iostream>
using namespace std;
// Function Prototypes
void bubbleSort(int arr[], int size, int& exchanges);
void selectionSort(int arr[], int size, int& exchanges);
void printArray(const int arr[], int size);
const int SIZE = 20; // Size of array
int main() {
// Data dictionary
int array1[SIZE] = {
84, 15, 33, 97, 2, 56, 71, 24, 68, 41,
10, 89, 53, 22, 60, 48, 77, 6, 94, 35
};
int array2[SIZE] = {
84, 15, 33, 97, 2, 56, 71, 24, 68, 41,
10, 89, 53, 22, 60, 48, 77, 6, 94, 35
};
int bubbleExchanges = 0;
int selectionExchanges = 0;
// Call original unsorted array
cout << "Original Array:" << endl;
printArray(array1, SIZE);
cout << "--------------------------------------------------------" << endl;
// Call Bubble Sort
bubbleSort(array1, SIZE, bubbleExchanges);
cout << "Bubble Sorted Array:" << endl;
printArray(array1, SIZE);
cout << "Bubble Sort Total Exchanges: " << bubbleExchanges << endl << endl;
// Call Selection Sort
selectionSort(array2, SIZE, selectionExchanges);
cout << "Selection Sorted Array:" << endl;
printArray(array2, SIZE);
cout << "Selection Sort Total Exchanges: " << selectionExchanges << endl;
return 0;
}
// Function Definitions
// Performs Bubble Sort and counts exchanges
void bubbleSort(int arr[], int size, int& exchanges) {
exchanges = 0;
for (int i = 0; i < size - 1; ++i) {
for (int j = 0; j < size - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
exchanges++;
}
}
}
}
// Performs Selection Sort and counts exchanges
void selectionSort(int arr[], int size, int& exchanges) {
exchanges = 0;
for (int i = 0; i < size - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < size; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap only if the minimum element is not already in place
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
exchanges++;
}
}
}
// Helper function to print the array
void printArray(const int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
Ly8gVGltb3RoeSBQcmljZQkJCQlDUzFBCQkJCUNoIDggQ2hhbGxlbmdlIDkKLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKgogKiBDb21wYXJlIHNvcnRpbmcgYWxnb3JpdGhtcwogKiAKICogVGhpcyBwcm9ncmFtIGNvbXBhcmVzIHRoZSBwZXJmb3JtYW5jZSBvZiBidWJibGUgc29ydCBhbmQgc2VsZWN0aW9uIHNvcnQKICogYWxnb3JpdGhtcyBieSBzb3J0aW5nIHR3byBpZGVudGljYWwgYXJyYXlzIG9mIHVuc29ydGVkIGludGVnZXJzIGFuZCB0cmFja2luZwogKiB0aGUgbnVtYmVyIG9mIGV4Y2hhbmdlcyBlYWNoIGFsZ29yaXRobSBtYWtlcy4KICogCiAqIElucHV0czoKICogIFR3byBpZGVudGljYWwgYXJyYXlzIAogKiAgVGhlIGZpeGVkIHNpemUgb2YgdGhlIGFycmF5ICgyMCkKICogCiAqIE91dHB1dHM6CiAqICBUaGUgb3JpZ2luYWwgdW5zb3J0ZWQgYXJyYXkgZGlzcGxheWVkIG9uIHRoZSBzY3JlZW4KICogIEJ1YmJsZSBzb3J0IHJlc3VsdCBhbmQgbnVtYmVyIG9mIGV4Y2hhbmdlcwogKiAgU2VsZWN0aW9uIHNvcnQgcmVzdWx0IGFuZCBudW1iZXIgb2YgZXhjaGFuZ2VzCiAqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KCiNpbmNsdWRlIDxpb3N0cmVhbT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBGdW5jdGlvbiBQcm90b3R5cGVzCnZvaWQgYnViYmxlU29ydChpbnQgYXJyW10sIGludCBzaXplLCBpbnQmIGV4Y2hhbmdlcyk7CnZvaWQgc2VsZWN0aW9uU29ydChpbnQgYXJyW10sIGludCBzaXplLCBpbnQmIGV4Y2hhbmdlcyk7CnZvaWQgcHJpbnRBcnJheShjb25zdCBpbnQgYXJyW10sIGludCBzaXplKTsKCmNvbnN0IGludCBTSVpFID0gMjA7CQkvLyBTaXplIG9mIGFycmF5CgppbnQgbWFpbigpIHsKCQoJLy8gRGF0YSBkaWN0aW9uYXJ5CiAgICBpbnQgYXJyYXkxW1NJWkVdID0gewogICAgCTg0LCAxNSwgMzMsIDk3LCAyLCA1NiwgNzEsIDI0LCA2OCwgNDEsIAogICAgICAgIDEwLCA4OSwgNTMsIDIyLCA2MCwgNDgsIDc3LCA2LCA5NCwgMzUKICAgIH07CiAgICBpbnQgYXJyYXkyW1NJWkVdID0gewogICAgCTg0LCAxNSwgMzMsIDk3LCAyLCA1NiwgNzEsIDI0LCA2OCwgNDEsIAogICAgICAgIDEwLCA4OSwgNTMsIDIyLCA2MCwgNDgsIDc3LCA2LCA5NCwgMzUKICAgIH07CgogICAgaW50IGJ1YmJsZUV4Y2hhbmdlcyA9IDA7CiAgICBpbnQgc2VsZWN0aW9uRXhjaGFuZ2VzID0gMDsKCQoJLy8gQ2FsbCBvcmlnaW5hbCB1bnNvcnRlZCBhcnJheQogICAgY291dCA8PCAiT3JpZ2luYWwgQXJyYXk6IiA8PCBlbmRsOwogICAgcHJpbnRBcnJheShhcnJheTEsIFNJWkUpOwogICAgY291dCA8PCAiLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0iIDw8IGVuZGw7CgogICAgLy8gQ2FsbCBCdWJibGUgU29ydAogICAgYnViYmxlU29ydChhcnJheTEsIFNJWkUsIGJ1YmJsZUV4Y2hhbmdlcyk7CiAgICBjb3V0IDw8ICJCdWJibGUgU29ydGVkIEFycmF5OiIgPDwgZW5kbDsKICAgIHByaW50QXJyYXkoYXJyYXkxLCBTSVpFKTsKICAgIGNvdXQgPDwgIkJ1YmJsZSBTb3J0IFRvdGFsIEV4Y2hhbmdlczogIiA8PCBidWJibGVFeGNoYW5nZXMgPDwgZW5kbCA8PCBlbmRsOwoKICAgIC8vIENhbGwgU2VsZWN0aW9uIFNvcnQKICAgIHNlbGVjdGlvblNvcnQoYXJyYXkyLCBTSVpFLCBzZWxlY3Rpb25FeGNoYW5nZXMpOwogICAgY291dCA8PCAiU2VsZWN0aW9uIFNvcnRlZCBBcnJheToiIDw8IGVuZGw7CiAgICBwcmludEFycmF5KGFycmF5MiwgU0laRSk7CiAgICBjb3V0IDw8ICJTZWxlY3Rpb24gU29ydCBUb3RhbCBFeGNoYW5nZXM6ICIgPDwgc2VsZWN0aW9uRXhjaGFuZ2VzIDw8IGVuZGw7CgogICAgcmV0dXJuIDA7Cn0KCi8vIEZ1bmN0aW9uIERlZmluaXRpb25zCgovLyBQZXJmb3JtcyBCdWJibGUgU29ydCBhbmQgY291bnRzIGV4Y2hhbmdlcwp2b2lkIGJ1YmJsZVNvcnQoaW50IGFycltdLCBpbnQgc2l6ZSwgaW50JiBleGNoYW5nZXMpIHsKICAgIGV4Y2hhbmdlcyA9IDA7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHNpemUgLSAxOyArK2kpIHsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IHNpemUgLSBpIC0gMTsgKytqKSB7CiAgICAgICAgICAgIGlmIChhcnJbal0gPiBhcnJbaiArIDFdKSB7CiAgICAgICAgICAgICAgICAvLyBTd2FwIGVsZW1lbnRzCiAgICAgICAgICAgICAgICBpbnQgdGVtcCA9IGFycltqXTsKICAgICAgICAgICAgICAgIGFycltqXSA9IGFycltqICsgMV07CiAgICAgICAgICAgICAgICBhcnJbaiArIDFdID0gdGVtcDsKICAgICAgICAgICAgICAgIGV4Y2hhbmdlcysrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CgovLyBQZXJmb3JtcyBTZWxlY3Rpb24gU29ydCBhbmQgY291bnRzIGV4Y2hhbmdlcwp2b2lkIHNlbGVjdGlvblNvcnQoaW50IGFycltdLCBpbnQgc2l6ZSwgaW50JiBleGNoYW5nZXMpIHsKICAgIGV4Y2hhbmdlcyA9IDA7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHNpemUgLSAxOyArK2kpIHsKICAgICAgICBpbnQgbWluSW5kZXggPSBpOwogICAgICAgIGZvciAoaW50IGogPSBpICsgMTsgaiA8IHNpemU7ICsraikgewogICAgICAgICAgICBpZiAoYXJyW2pdIDwgYXJyW21pbkluZGV4XSkgewogICAgICAgICAgICAgICAgbWluSW5kZXggPSBqOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIC8vIFN3YXAgb25seSBpZiB0aGUgbWluaW11bSBlbGVtZW50IGlzIG5vdCBhbHJlYWR5IGluIHBsYWNlCiAgICAgICAgaWYgKG1pbkluZGV4ICE9IGkpIHsKICAgICAgICAgICAgaW50IHRlbXAgPSBhcnJbaV07CiAgICAgICAgICAgIGFycltpXSA9IGFyclttaW5JbmRleF07CiAgICAgICAgICAgIGFyclttaW5JbmRleF0gPSB0ZW1wOwogICAgICAgICAgICBleGNoYW5nZXMrKzsKICAgICAgICB9CiAgICB9Cn0KCi8vIEhlbHBlciBmdW5jdGlvbiB0byBwcmludCB0aGUgYXJyYXkKdm9pZCBwcmludEFycmF5KGNvbnN0IGludCBhcnJbXSwgaW50IHNpemUpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2l6ZTsgKytpKSB7CiAgICAgICAgY291dCA8PCBhcnJbaV0gPDwgIiAiOwogICAgfQogICAgY291dCA8PCBlbmRsOwp9