Stable and Unstable Sort Algorithms

A stable sort algorithm is one that preserves the relative order of equal elements. In other words, when a stable sort is applied to an array, if a and b have equal sort keys and a appears before b in the unsorted array, then a will appear before b after sorting is complete. If, on the other hand, there is the possibility that b appears before a after the sort is complete, the sort algorithm is considered to be unstable.

The code supplied with this assignment includes the sort algorithms presented in class along with two test programs: sorttest3 which sorts an array of integers and sorttest4 which sorts an array of mixed-case strings.

Program sorttest3 performs a sort on integers using the right-most digit as the sort key. Thus when sorted, 681 (for example) will appear before 328 in the sorted array because 1 is less than 8.

Program sorttest4 generates an array of randomized mixed-case strings. You will note that, by default, all uppercase characters sort before the lowercase characters due to their underlying ASCII codes.

For this assignment, modify program sorttest4 such that it sorts according to a case-blind comparison of only the first character of each string. In the sorted array, "car" should come before "Bus". Further, "dog" and "Duck" should be considered equal since they both with the same letter, ignoring case.

You will need to modify sorttest4 (make a backup copy of the original in case you need to go back to it). Add a sort comparison function, as was done in sorttest3. Then, modify the call to the sort function (line 58) to pass your function as the third parameter.

Once you completed your modifications to sorttest4 you can run tests on the various sort algorithms included in this project. By observation, you should be able to gain some sense of whether each sort algorithm implementation is stable or unstable.

Written Part / Analysis

For the following sort algorithms, state whether the implementation included here is stable or unstable:

Insertion Sort

Heap Sort

Selection Sort

In addition, state why it is stable or unstable. If you determine that it is unstable, a sample run of the program (copy/paste) is sufficient to show it is unstable. However, if the sort is stable, provide a convincing argument as to why you believe it is stable (sample runs may suggest it is stable, but you need to examine the code to be sure).

For example, the Bubble Sort implementation is stable. It is stable because...

Suppose a and b have equal sort keys and a appears before b in the original array. The sort code (bubble.h) only ever exchanges adjacent elements at line 21. In order for b to come before a they will need to be swapped at line 21. However, if a and b have equal keys, the cmp function return false, thus the swap of these values will never happen.

Provide your anwers for the three sorts mentioned above in file README.md.

sorttest3

// srttest3.cpp - Sort test program #3 // // Performs a sort on an array of random integers using a custom comparison // function.

#include #include #include #include using namespace std;

// Include the sort code. The file used here must define a function called // "sort" that takes two parameters: an array of integers (or template type) // and an integer size. #include "bubble.h"

// Custom comparison function. This function will cause the sort altorithm // to sort integers according to the rightmost digit. When the rightmost // digit of two integers is the same, they are to be considered equal. inline bool cmp_mod_10 (int a, int b) { return abs(a) % 10 < abs(b) % 10; }

int checksum1(int a[], int n); int checksum2(int a[], int n); void print(int a[], int n); bool is_sorted(int a[], int n);

int main(int argc, char* argv[]) {

int* x; // Array of integers, allocated dynamically int size; // Size of array x

// Initialize random number generator srand(time(0));

// Get size of array to be sorted if (!(size = argc > 1 ? atoi(argv[1]) : 0)) { cout << "Enter array size: "; cin >> size; }

// Set verbose mode if <=120 elements. In verbose mode, displays array // before and after sorting, shows the checksums, and generates values // <1000 for readability. bool verbose = size <= 120;

// Allocate array of int's. x = new int[size];

// Fill array with random numbers. for (int i = 0; i < size; i++) x[i] = verbose ? (rand() % 1000) : rand();

// Produce initial checksums. int cksum1a = checksum1(x, size); int cksum2a = checksum2(x, size);

// Show array and checksums, if verbose set. if (verbose) { cout << endl << "Before sort:" << endl; print(x, size); cout << " Checksums: " << cksum1a << " " << cksum2a << endl << endl; }

// Sort the array. cout << "Sorting... "; cout.flush(); clock_t t = clock(); sort(x, size, cmp_mod_10); t = clock() - t;

// Produce checksums. int cksum1b = checksum1(x, size); int cksum2b = checksum2(x, size);

// Show result. cout << (is_sorted(x, size) && cksum1a == cksum1b && cksum2a == cksum2b ? "success." : "FAILED") << endl;

// Show array, if verbose set. if (verbose) { cout << endl << "After sort:" << endl; print(x, size); cout << " Checksums: " << cksum1b << " " << cksum2b << endl << endl; }

// Show run time. cout << "Run time: " << fixed << setprecision(2) << ((double)t) / CLOCKS_PER_SEC << " seconds." << endl;

// Deallocate array. delete[] x;

#ifdef _MSC_VER system("pause"); #endif return 0; }

// checksum1 - A simple checksum to see if an array of integers contains the // same values, but not necessarily in the same order. Returns the sum of // of the values in the array, disregarding overflow. int checksum1(int a[], int n) { int cksum = 0; for (int i = 0; i < n; i++) cksum += a[i]; return cksum; }

// checksum2 - Another simple checksum. Initializes a checksum to zero, then // XOR's all values into the checksum. int checksum2(int a[], int n) { int cksum = 0; for (int i = 0; i < n; i++) cksum ^= a[i]; return cksum; }

// print - Prints all values in an array, formatted for readability. Assumes // each value is fewer than 5 digits. void print(int a[], int n) { for (int i = 0; i < n; i++) { if (i && !(i % 12)) cout << endl; cout << setw(5) << a[i]; } cout << endl; }

// is_sorted - Checks an array to see if the values are sorted. bool is_sorted(int a[], int n) { for (int i = 0; i < n - 1; i++) if (cmp_mod_10(a[i + 1], a[i])) return false; return true; }

sorttest4

// srttest4.cpp - Sort test program #4 // // Performs a sort on an array of random mixed-case strings. Ensures that the // array is, in fact, sorted upon completion of calling the sort function. // Also, reports the CPU time required to sort the array. Note, however, that // this program does not ensure that the values in the sorted array are the // same values as in the original unsorted array.

#include #include #include #include #include using namespace std;

#include "selection.h"

void print(string a[], int n); bool is_sorted(string a[], int n); string rstring();

int main(int argc, char* argv[]) {

string* s; // Array of strings, allocated dynamically int size; // Size of array s

// Initialize random number generator srand(time(0));

// Get size of array to be sorted if (!(size = argc > 1 ? atoi(argv[1]) : 0)) { cout << "Enter array size: "; cin >> size; }

// Set verbose mode if <=96 elements. In verbose mode, displays array // before and after sorting. bool verbose = size <= 96;

// Allocate array of string's. s = new string[size];

// Fill array with random strings. for (int i = 0; i < size; i++) s[i] = rstring();

// Show array, if verbose set. if (verbose) { cout << endl << "Before sort:" << endl; print(s, size); cout << endl; }

// Sort the array. cout << "Sorting... "; cout.flush(); clock_t t = clock(); sort(s, size); t = clock() - t;

// Show result. cout << (is_sorted(s, size) ? "success." : "FAILED") << endl;

// Show array, if verbose set. if (verbose) { cout << endl << "After sort:" << endl; print(s, size); cout << endl; }

// Show run time. cout << "Run time: " << fixed << setprecision(2) << ((double)t) / CLOCKS_PER_SEC << " seconds." << endl;

// Deallocate array. delete[] s;

#ifdef _MSC_VER system("pause"); #endif

return 0; }

// print - Prints all values in an array, 8 strings per line. void print(string a[], int n) { for (int i = 0; i < n; i++) { if (i && !(i % 8)) cout << endl; cout << " " << a[i]; } cout << endl; }

// is_sorted - Checks an array to see if the values are sorted. bool is_sorted(string a[], int n) { for (int i = 0; i < n - 1; i++) if (a[i] > a[i + 1]) return false; return true; }

// rstring - Generate a random 6-character mixed-case string. string rstring() { string s; for (int i = 0; i < 6; i++) s += ((rand() % 2 ? 'A' : 'a') + rand() % 26); return s; }