Question

Sorting Benchmarks
Write a program that generates and sorts an array of a user-specified number (arraySize) of randomly generated numbers. To keep the values to a reasonable range by using the array size as the upper bound for the random numbers (between 1 and arraySize). Your program should call the individual functions that implement the five sorting algorithms discussed in class (see the lecture slides). Each function should keep a count of the number of comparisons/exchanges it makes. Display the pre-sorted array, the sorted array, and the number of comparisons for each algorithm.

Note: In this assignment, you will compare all the five sorting algorithms from the lecture notes (brute force sort, bubble sort, bubble sort++, selection sort, and insertion sort) with each other using the same data for each. Start with getting one to work first. The idea is that once you have one, adding in the other algorithms is relatively simple. Hint: use the algorithms from the slides! Your program MUST include a function for each algorithm and use them appropriately. The main procedural code must first prompt the user for the arraySize = number of elements to store in the array ("How many elements in the array?"). Then, it will generate arraySize random integers between 1 and arraySize (the number they entered--yes, you will use it twice!). Since each function will sort the array, changing the values, you will need to make multiple copies of the generated array to test the same numbers against each algorithm. Each algorithm will return the number of comparisons made. This is when one element is compared to another, regardless of whether or not they get swapped. NO GLOBAL VARIABLES!

You will need to include at least these functions:
void displayArray(int values[], int size);
int bruteForceSort(int values[], int size);
int bubbleSort(int values[], int size);
int bubblePPSort(int values[], int size);
int selectionSort(int values[], int size);
int insertionSort(int values[], int size);

The output should look something like this -- user inputs are in bold blue type:
How many elements in the array? 20
BRUTE FORCE SORT
Before sorting:
10 14 6 7 12 18 9 13 4 17 19 2 17 2 4 10 20 3 9 14
After sorting:
2 2 3 4 4 6 7 9 9 10 10 12 13 14 14 17 17 18 19 20
Number of comparisons: 400

BUBBLE SORT
Before sorting:
10 14 6 7 12 18 9 13 4 17 19 2 17 2 4 10 20 3 9 14
After sorting:
2 2 3 4 4 6 7 9 9 10 10 12 13 14 14 17 17 18 19 20
Number of comparisons: 190

BUBBLE SORT PLUS PLUS
Before sorting:
10 14 6 7 12 18 9 13 4 17 19 2 17 2 4 10 20 3 9 14
After sorting:
2 2 3 4 4 6 7 9 9 10 10 12 13 14 14 17 17 18 19 20
Number of comparisons: 184

SELECTION SORT
Before sorting:
10 14 6 7 12 18 9 13 4 17 19 2 17 2 4 10 20 3 9 14
After sorting:
2 2 3 4 4 6 7 9 9 10 10 12 13 14 14 17 17 18 19 20
Number of comparisons: 206

INSERTION SORT
Before sorting:
10 14 6 7 12 18 9 13 4 17 19 2 17 2 4 10 20 3 9 14
After sorting:
2 2 3 4 4 6 7 9 9 10 10 12 13 14 14 17 17 18 19 20
Number of comparisons: 186

Answer 1

If you have any doubts, please give me comment...

#include <iostream>

#include <cstdlib>

using namespace std;

const int max_size = 50;

void displayArray(int values[], int size);

int bruteForceSort(int values[], int size);

int bubbleSort(int values[], int size);

int bubblePPSort(int values[], int size);

int selectionSort(int values[], int size);

int insertionSort(int values[], int size);

int main()

{

    int values1[max_size], values2[max_size], values3[max_size], values4[max_size], values5[max_size];

    int size;

    cout << "How many elements in the array? ";

    cin >> size;

    for (int i = 0; i < size; i++)

    {

        values1[i] = (rand() % (size - 1)) + 1;

        values2[i] = values1[i];

        values3[i] = values1[i];

        values4[i] = values1[i];

        values5[i] = values1[i];

    }

    cout << "\nBRUTE FORCE SORT" << endl;

    cout << "Before sorting:" << endl;

    displayArray(values1, size);

    int comp = bruteForceSort(values1, size);

    cout << "After sorting:" << endl;

    displayArray(values1, size);

    cout<<"Number of comparisons: "<<comp<<endl;

    cout << "\nBUBBLE SORT" << endl;

    cout << "Before sorting:" << endl;

    displayArray(values2, size);

    comp = bubbleSort(values2, size);

    cout << "After sorting:" << endl;

    displayArray(values2, size);

    cout<<"Number of comparisons: "<<comp<<endl;

    cout << "\nBUBBLE SORT PLUS PLUS" << endl;

    cout << "Before sorting:" << endl;

    displayArray(values3, size);

    comp = bubblePPSort(values3, size);

    cout << "After sorting:" << endl;

    displayArray(values3, size);

    cout<<"Number of comparisons: "<<comp<<endl;

    cout << "\n\nSELECTION SORT" << endl;

    cout << "Before sorting:" << endl;

    displayArray(values4, size);

    comp = selectionSort(values4, size);

    cout << "After sorting:" << endl;

    displayArray(values4, size);

    cout<<"Number of comparisons: "<<comp<<endl;

    cout << "\n\nINSERTION SORT" << endl;

    cout << "Before sorting:" << endl;

    displayArray(values5, size);

    comp = insertionSort(values5, size);

    cout << "After sorting:" << endl;

    displayArray(values5, size);

    cout<<"Number of comparisons: "<<comp<<endl;

    return 0;

}

void displayArray(int values[], int size)

{

    for (int i = 0; i < size; i++)

    {

        cout << values[i] << " ";

    }

    cout << endl;

}

int bruteForceSort(int values[], int size){

    int comparisions = 0;

    for(int i=0; i<size; i++){

        for(int j=0; j<size; j++){

            comparisions++;

            if(values[i]<values[j]){

                int temp = values[i];

                values[i] = values[j];

                values[j] = temp;

            }

        }

    }

    return comparisions;

}

int bubbleSort(int values[], int size){

    int comparisions = 0;

    for(int i=0; i<size; i++){

        for(int j=0; j<size-i-1; j++){

            comparisions++;

            if(values[j]>values[j+1]){

                int temp =values[j];

                values[j] = values[j+1];

                values[j+1] = temp;

            }

        }

    }

    return comparisions;

}

int bubblePPSort(int values[], int size)

{

    int comparisons=0;

    for (int i = 0; i < size; i++)

    {

        int flag = 0;

        for (int j = 0; j < size - i; j++)

        {

            comparisons++;

            if (values[j] > values[j + 1])

            {

                flag = 1;

                int temp = values[j];

                values[j] = values[j + 1];

                values[j + 1] = temp;

            }

        }

        if (flag == 0)

            break;

    }

    return comparisons;

}

int selectionSort(int values[], int size)

{

    int comparisons = 0;

    for (int i = 0; i < size-1; i++)

    {

        for (int j = i+1; j < size; j++)

        {

            comparisons++;

            if (values[i] > values[j])

            {

                int temp = values[i];

                values[i] = values[j];

                values[j] = temp;

            }

        }

    }

    return comparisons;

}

int insertionSort(int values[], int size)

{

    int i, key, j, comparisons = 0;

    for (i = 1; i < size; i++)

    {

        key = values[i];

        j = i - 1;

        while (j >= 0 && values[j] > key)

        {

            comparisons++;

            values[j + 1] = values[j];

            j = j - 1;

        }

        values[j + 1] = key;

    }

    return comparisons;

}