Quicksort computer science c++

/** * @description Assignment 05 Quick Sort */ #include <iostream> #include <sstream> #include <cassert> #include <cstring> #include "QuickSort.hpp" using namespace std; /** list to string * Represent array as a string time, useful for output. * * @param list[] The list, an array of integers, to be converted to * a string. * @param length The length of the list. * * @returns string Returns a string with a representation of the list * state and it contents. */ string tostring(int list[], int length) { ostringstream out; out << "List length: " << length << " ["; // output first value, so we can remove , at end if (length >= 1) { out << list[0]; } // output each follow with a preceeding comma, // which allows us to end list without trailing , for (int index = 1; index < length; index++) { out << ", " << list[index]; } out << "]"; return out.str(); } /** compare lists equal * This function compares if the two lists (arrays of integers) * given as parameters are equal or not. Result is boolean true * if lists all have the same values, false otherwise. * * @param a[], b[] The lists, both of int and both the same size, * that are to be compared. * @param length The length of both of the lists. * * @returns bool Returns true if the lists are equal (have all the * same values at all the same positions) and false otherwise. */ bool listsAreEqual(int a[], int b[], int length) { // compare each item in a and b for (int index = 0; index < length; index++) { // as soon as we find 1 value that differs, the answer is false, // the lists are not equal if (a[index] != b[index]) { return false; } } // at this point we compared every value and they were all the // same, thus the lists must be equal return true; } /** main * The main entry point for this program. Execution of this program * will begin with this main function. * * @param argc The command line argument count which is the number of * command line arguments provided by user when they started * the program. * @param argv The command line arguments, an array of character * arrays. * * @returns An int value indicating program exit status. Usually 0 * is returned to indicate normal exit and a non-zero value * is returned to indicate an error condition. */ int main(int argc, char** argv) { // variables used for the function/unit tests int length; // test of swap function ------------------------------------------------ cout << "Test swapListValues() ------------------------------------------" << endl; // basic test length = 2; int testvals1[] = {5, 10}; int expected1[] = {10, 5}; // swapListValues(testval1, 0, 1); // cout << "swapListValues() test 1, swap 2 values" << endl // << " expected: " << tostring(expected1, length) << endl // << " actual : " << tostring(testvals1, length) << endl // << endl; // assert(listsAreEqual(testvals1, expected1, length)); // test if indexes are equal, important, should not cause any change length= 2; int testvals2[] = {8, 6}; int expected2[] = {8, 6}; // swapListValues(testvals2, 1, 1); // cout << "swapListValues() test 2, same index" << endl // << " expected: " << tostring(expected2, length) << endl // << " actual : " << tostring(testvals2, length) << endl // << endl; // assert(listsAreEqual(testvals2, expected2, length)); // more general tests, swap values in middle of list length = 12; int testvals3[] = {2, 7, 9, 3, 8, 4, 2, 9, 5, 8, 6, 1}; int expected3[] = {2, 7, 6, 3, 8, 4, 2, 9, 5, 8, 9, 1}; // swapListValues(testvals3, 2, 10); // cout << "swapListValues() test 3, swap 2 values from inside of list" << endl // << " expected: " << tostring(expected3, length) << endl // << " actual : " << tostring(testvals3, length) << endl // << endl; // assert(listsAreEqual(testvals3, expected3, length)); // swap back, reverse indexes in function call // continuing to use testvals after previous test here length = 12; int expected4[] = {2, 7, 9, 3, 8, 4, 2, 9, 5, 8, 6, 1}; // swapListValues(testvals3, 10, 2); // cout << "swapListValues() test 4, reverse the previous swap" << endl // << " expected: " << tostring(expected4, length) << endl // << " actual : " << tostring(testvals3, length) << endl // << endl; // assert(listsAreEqual(testvals3, expected4, length)); // swap with index 0 on a bigger list // still using previous testvals length = 12; int expected5[] = {4, 7, 9, 3, 8, 2, 2, 9, 5, 8, 6, 1}; // swapListValues(testvals3, 5, 0); // cout << "swapListValues() test 5, swap with index 0" << endl // << " expected: " << tostring(expected5, length) << endl // << " actual : " << tostring(testvals3, length) << endl // << endl; // assert(listsAreEqual(testvals3, expected5, length)); // swap with last index on a bigger list // still using previous testvals length = 12; int expected6[] = {4, 7, 9, 3, 8, 2, 1, 9, 5, 8, 6, 2}; // swapListValues(testvals3, 6, 11); // cout << "swapListValues() test 6, swap with last index" << endl // << " expected: " << tostring(expected6, length) << endl // << " actual : " << tostring(testvals3, length) << endl // << endl; // assert(listsAreEqual(testvals3, expected6, length)); // test of findAndSwapPivot function ------------------------------------ cout << endl; cout << "Test findAndSwapPivot() ----------------------------------------" << endl; int expectedPivotValue; int actualPivotValue; // basic test on a small list length = 3; int testvals7[] = {5, 3, 8}; int expected7[] = {5, 8, 3}; expectedPivotValue = 3; // actualPivotValue = findAndSwapPivot(testvals7, 0, length-1); // cout << "findAndSwapPivot() test 1, basic test" << endl // << " expected: " << tostring(expected7, length) << endl // << " expected pivot: " << expectedPivotValue << endl // << " actual: " << tostring(testvals7, length) << endl // << " actual pivot: " << actualPivotValue << endl // << endl; // assert(listsAreEqual(testvals7, expected7, length)); // assert(actualPivotValue == expectedPivotValue); // test on list of length 1, should work nothing will be done length = 1; int testvals8[] = {5}; int expected8[] = {5}; expectedPivotValue = 5; // actualPivotValue = findAndSwapPivot(testvals8, 0, length-1); // cout << "findAndSwapPivot() test 2, test list size 1" << endl // << " expected: " << tostring(expected8, length) << endl // << " expected pivot: " << expectedPivotValue << endl // << " actual: " << tostring(testvals8, length) << endl // << " actual pivot: " << actualPivotValue << endl // << endl; // assert(listsAreEqual(testvals8, expected8, length)); // assert(actualPivotValue == expectedPivotValue); // general test on a bigger list, even number of values length = 10; int testvals9[] = {5, 2, 8, 7, 3, 9, 1, 4, 5, 8}; int expected9[] = {5, 2, 8, 7, 8, 9, 1, 4, 5, 3}; expectedPivotValue = 3; // actualPivotValue = findAndSwapPivot(testvals9, 0, length-1); // cout << "findAndSwapPivot() test 3, bigger list with even number of values" << endl // << " expected: " << tostring(expected9, length) << endl // << " expected pivot: " << expectedPivotValue << endl // << " actual: " << tostring(testvals9, length) << endl // << " actual pivot: " << actualPivotValue << endl // << endl; // assert(listsAreEqual(testvals9, expected9, length)); // assert(actualPivotValue == expectedPivotValue); // general test on a bigger list, odd number of values length = 15; int testvals10[] = {5, 2, 8, 7, 3, 9, 1, 42, 5, 8, 10, 11, 15, 22, 18}; int expected10[] = {5, 2, 8, 7, 3, 9, 1, 18, 5, 8, 10, 11, 15, 22, 42}; expectedPivotValue = 42; // actualPivotValue = findAndSwapPivot(testvals10, 0, length-1); // cout << "findAndSwapPivot() test 4, bigger list with odd number of values" << endl // << " expected: " << tostring(expected10, length) << endl // << " expected pivot: " << expectedPivotValue << endl // << " actual: " << tostring(testvals10, length) << endl // << " actual pivot: " << actualPivotValue << endl // << endl; // assert(listsAreEqual(testvals10, expected10, length)); // assert(actualPivotValue == expectedPivotValue); // test of partitionList function --------------------------------------- cout << endl; cout << "Test partitionList() -------------------------------------------" << endl; int expectedPivotIndex; int actualPivotIndex; // work from general to more specific stress tests. // most general test, partition list approximately in middle. // note that pivot needs to be on the end of list, and for a list of size n // the valid indexes are from 0 to n-1, but the partition values is at index // n-1, so we call partitionList from indexes 0 to n-2 length = 10; int testvals11[] = {8, 3, 7, 6, 9, 2, 4, 8, 1, 5}; int expected11[] = {1, 3, 4, 2, 9, 6, 7, 8, 8, 5}; expectedPivotIndex = 4; // actualPivotIndex = partitionList(testvals11, 0, length-2, testvals11[length-1]); // cout << "partitionList() test 1, basic test" << endl // << " expected: " << tostring(expected11, length) << endl // << " expected pivot: " << expectedPivotIndex <<endl // << " actual: " << tostring(testvals11, length) << endl // << " actual pivot: " << actualPivotIndex << endl // << endl; // assert(listsAreEqual(testvals11, expected11, length)); // assert(actualPivotIndex == expectedPivotIndex); // another general test, also this tests that all values == pivot end // up being moved to the right length = 15; int testvals12[] = {12, 7, 10, 19, 6, 18, 12, 15, 6, 10, 4, 13, 11, 17, 10}; int expected12[] = {4, 7, 6, 6, 19, 18, 12, 15, 10, 10, 12, 13, 11, 17, 10}; expectedPivotIndex = 4; // actualPivotIndex = partitionList(testvals12, 0, length-2, testvals12[length-1]); // cout << "partitionList() test 2, bigger test and some duplicates of the pivot" << endl // << " expected: " << tostring(expected12, length) << endl // << " expected pivot: " << expectedPivotIndex <<endl // << " actual: " << tostring(testvals12, length) << endl // << " actual pivot: " << actualPivotIndex << endl // << endl; // assert(listsAreEqual(testvals12, expected12, length)); // assert(actualPivotIndex == expectedPivotIndex); // test everything is to left of pivot is working length = 6; int testvals13[] = {4, 3, 7, 6, 5, 10}; int expected13[] = {4, 3, 7, 6, 5, 10}; expectedPivotIndex = 5; // actualPivotIndex = partitionList(testvals13, 0, length-2, testvals13[length-1]); // cout << "partitionList() test 3, everything is smaller than pivot value" << endl // << " expected: " << tostring(expected13, length) << endl // << " expected pivot: " << expectedPivotIndex <<endl // << " actual: " << tostring(testvals13, length) << endl // << " actual pivot: " << actualPivotIndex << endl // << endl; // assert(listsAreEqual(testvals13, expected13, length)); // assert(actualPivotIndex == expectedPivotIndex); // test everything is to right of pivot is working length = 6; int testvals14[] = {4, 3, 7, 6, 5, 2}; int expected14[] = {4, 3, 7, 6, 5, 2}; expectedPivotIndex = 0; // actualPivotIndex = partitionList(testvals14, 0, length-2, testvals14[length-1]); // cout << "partitionList() test 4, everything is bigger than pivot value" << endl // << " expected: " << tostring(expected14, length) << endl // << " expected pivot: " << expectedPivotIndex <<endl // << " actual: " << tostring(testvals14, length) << endl // << " actual pivot: " << actualPivotIndex << endl // << endl; // assert(listsAreEqual(testvals14, expected14, length)); // assert(actualPivotIndex == expectedPivotIndex); // test small list that needs to be swapped length = 3; int testvals15[] = {8, 2, 4}; int expected15[] = {2, 8, 4}; expectedPivotIndex = 1; // actualPivotIndex = partitionList(testvals15, 0, length-2, testvals15[length-1]); // cout << "partitionList() test 5, small list that needs a swap" << endl // << " expected: " << tostring(expected15, length) << endl // << " expected pivot: " << expectedPivotIndex <<endl // << " actual: " << tostring(testvals15, length) << endl // << " actual pivot: " << actualPivotIndex << endl // << endl; // assert(listsAreEqual(testvals15, expected15, length)); // assert(actualPivotIndex == expectedPivotIndex); // list of only 1 item (besides pivot value), still needs to work length = 2; int testvals16[] = {8, 4}; int expected16[] = {8, 4}; expectedPivotIndex = 0; // actualPivotIndex = partitionList(testvals16, 0, length-2, testvals16[length-1]); // cout << "partitionList() test 6, list of size 1 (and pivot value)" << endl // << " expected: " << tostring(expected16, length) << endl // << " expected pivot: " << expectedPivotIndex <<endl // << " actual: " << tostring(testvals16, length) << endl // << " actual pivot: " << actualPivotIndex << endl // << endl; // assert(listsAreEqual(testvals16, expected16, length)); // assert(actualPivotIndex == expectedPivotIndex); // list of only 1 item, but the pivot is bigger length = 2; int testvals17[] = {8, 12}; int expected17[] = {8, 12}; expectedPivotIndex = 1; // actualPivotIndex = partitionList(testvals17, 0, length-2, testvals17[length-1]); // cout << "partitionList() test 7, list of size 1, pivot value is larger" << endl // << " expected: " << tostring(expected17, length) << endl // << " expected pivot: " << expectedPivotIndex <<endl // << " actual: " << tostring(testvals17, length) << endl // << " actual pivot: " << actualPivotIndex << endl // << endl; // assert(listsAreEqual(testvals17, expected17, length)); // assert(actualPivotIndex == expectedPivotIndex); // sort by hand using partitionList() length = 5; int testvals18[] = {7, 8, 3, 5, 6}; // actualPivotIndex = partitionList(testvals18, 0, length-2, testvals18[length-1]); // swapListValues(testvals18, length-1, actualPivotIndex); // cout << "partitionList() test 8 (sort by hand)" << endl; // cout << " after first partition: " << tostring(testvals18, length) << endl; // partition left // actualPivotIndex = partitionList(testvals18, 0, 0, testvals18[1]); // swapListValues(testvals18, 1, actualPivotIndex); // cout << " after second partition (left): " << tostring(testvals18, length) << endl; // partition right // actualPivotIndex = partitionList(testvals18, 3, 3, testvals18[4]); // swapListValues(testvals18, 4, actualPivotIndex); // cout << " after third partition (right): " << tostring(testvals18, length) << endl; int expected18[] = {3, 5, 6, 7, 8}; // cout << " expected: " << tostring(expected18, length) << endl // << " actual: " << tostring(testvals18, length) << endl // << endl; // assert(listsAreEqual(testvals18, expected18, length)); // test of quickSort function ------------------------------------------- cout << endl; cout << "Test quickSort() -----------------------------------------------" << endl; // sort a list of size 1 length = 1; int testvals19[] = {8}; int expected19[] = {8}; // quickSort(testvals19, 0, length-1); // cout << "quickSort() test 1, sort list of size 1" << endl // << " expected: " << tostring(expected19, length) << endl // << " actual: " << tostring(testvals19, length) << endl // << endl; // assert(listsAreEqual(testvals19, expected19, length)); // sort a list of size 2, already in order length = 2; int testvals20[] = {3, 9}; int expected20[] = {3, 9}; // quickSort(testvals20, 0, length-1); // cout << "quickSort() test 2, sort list of size 2 already ordered" << endl // << " expected: " << tostring(expected20, length) << endl // << " actual: " << tostring(testvals20, length) << endl // << endl; // assert(listsAreEqual(testvals20, expected20, length)); // sort a list of size 2, not in order length = 2; int testvals21[] = {9, 3}; int expected21[] = {3, 9}; // quickSort(testvals21, 0, length-1); // cout << "quickSort() test 3, sort list of size 2 out of order" << endl // << " expected: " << tostring(expected21, length) << endl // << " actual: " << tostring(testvals21, length) << endl // << endl; // assert(listsAreEqual(testvals21, expected21, length)); // sort an odd sized list length = 9; int testvals22[] = {9, 3, 2, 7, 5, 8, 6, 5, 4}; int expected22[] = {2, 3, 4, 5, 5, 6, 7, 8, 9}; // quickSort(testvals22, 0, length-1); // cout << "quickSort() test 4, sort odd sized list" << endl // << " expected: " << tostring(expected22, length) << endl // << " actual: " << tostring(testvals22, length) << endl // << endl; // assert(listsAreEqual(testvals22, expected22, length)); // sort an even sized list length = 14; int testvals23[] = {9, 3, 2, 7, 5, 8, 6, 5, 4, 2, 10, 8, 11, 5}; int expected23[] = {2, 2, 3, 4, 5, 5, 5, 6, 7, 8, 8, 9, 10, 11}; // quickSort(testvals23, 0, length-1); // cout << "quickSort() test 5, sort even sized list" << endl // << " expected: " << tostring(expected23, length) << endl // << " actual: " << tostring(testvals23, length) << endl // << endl; // assert(listsAreEqual(testvals23, expected23, length))1; // sort an already sorted list length = 17; int testvals24[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}; int expected24[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}; // quickSort(testvals24, 0, length-1); // cout << "quickSort() test 6, sort already sorted list" << endl // << " expected: " << tostring(expected24, length) << endl // << " actual: " << tostring(testvals24, length) << endl // << endl; // assert(listsAreEqual(testvals24, expected24, length)); // sort a reversed list length = 17; int testvals25[] = {17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; int expected25[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}; // quickSort(testvals25, 0, length-1); // cout << "quickSort() test 7, sort a reversed list" << endl // << " expected: " << tostring(expected25, length) << endl // << " actual: " << tostring(testvals25, length) << endl // << endl; // assert(listsAreEqual(testvals25, expected25, length)); // sort a list with lots of duplicates length = 14; int testvals26[] = {4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8}; int expected26[] = {4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8}; // quickSort(testvals26, 0, length-1); // cout << "quickSort() test 7, sort a reversed list" << endl // << " expected: " << tostring(expected26, length) << endl // << " actual: " << tostring(testvals26, length) << endl // << endl; // assert(listsAreEqual(testvals26, expected26, length)); // return 0 to indicate successful completion return 0; }