Question

Project 2

Sorting, CPU Time, and Big O Analysis

Note: you will be using Microsoft Visual Studios 2019 as the compiler.

This is an individual assignment. You will have lab time to work on this assignment as well as homework time.

Each person will analyze two sorts. The first sort will be either bubble sort or insertion sort. The second sort will be either quick sort or merge sort. Create two projects, one for each sort in the given choices.

In this assignment, we will be learning about, describing, coding, and empirically looking at the work involved in each sorting algorithm. Use 4 data set sizes. Results will be based on execution time for each sort. The size should have a regular increment. For example, using a regular increment of 10,000, you might have sizes of 10,000, 20,000, 30,000, and 40,000. Choose your data size based upon the ability to obtain meaning results.

Submit:

1. A Word document named SortDescriptionsLastName.docx. The Word document should be modeled after the selection sort description under Course Content. The Word document should have:
   1. A few useful web resources for the sort.
   2. A detailed explanation (in your own words) of the sort.
   3. A clear visual representation of the sort (cite source if found on web, book …).
   4. Two screen shots of your program displaying the sorted array for each sort. The display of each value should include the index and value of each element in the array. These screen shots of course will not show your entire array but only a part.
2. An Excel document that shows the empirical results of running each sort. The name of the file should be SortEmpiricalAnalysesLastName.xlsx.
3. Code for the algorithm in a working program (similar to SelectionSort.cpp).
   1. Code should be well-documented.
   2. Code should use meaningful identifiers (do not use abbreviated variable names such as r for right).
   3. Code should be well-structured and easy to read.
   4. You should be able to understand every aspect of the code that you are using.
   5. The code for each sort should be organized in its own project folder – a compressed zipped folder for each project. Use only .zip folders (not .rar folder).

Grading

For the two sorts:       Code is well documented       Code uses meaningful identifiers       Code is well-structured and easy to read.       In Word document:       Useful web resources for each sort       Detailed explanation (in your own words) of each sort       A clear visual representation of each sort (cite source if found on web, book …)       One screen shot of your program displaying the sorted arrays An Excel spreadsheet that shows the empirical results of running each sort. Code for each sort should be organized in its own project folder – a compressed zipped folder (for each project). Use only .zip folders (not .rar folder).

10 points 10 points 10 points 10 points 20 points 10 points 10 points 10 points 10 points Total 100

Answer 1

Answer:-

The main function takes as input the size of the array and calls the corresponding sort function and measure the time taken by the algorithm to sort.

In this I am giving you the code for all the sorting techniques mentioned above as well as the main function. Change the sorting function as you like in the main() function to get the result.

You can then compare time taken by different algorithms to sort large sized arrays.

#include <bits/stdc++.h>

using namespace std;

//-----------------------bubble sort-----------------------

// swap function for bubble sort and quick sort algorithms

void swapElements(int &a, int &b) {

int temp = a;

a = b;

b = temp;

}

void bubbleSort(int a[], int n) {

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

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

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

swapElements(a[j], a[j + 1]);

}

}

}

}

//----------------------Insertion sort-------------------------

int insertionSort(int a[], int n) {

int key;

for(int i = 1; i < n; ++i) {

key = a[i];

int j = i - 1;

while(j >= 0 && a[j] > key) {

a[j + 1] = a[j];

j--;

}

a[j + 1] = key;

}

}

//-------------------------Merge sort------------------------------

void mergeArrays(int a[], int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

int l[n1], r[n2];

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

l[i] = a[left + i];

}

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

r[i] = a[mid + 1 + i];

}

int i = 0, j = 0, k = left;

while(i < n1 && j < n2) {

if(l[i] <= r[j]) {

a[k++] = l[i++];

}

else {

a[k++] = r[j++];

}

}

while(i < n1) {

a[k++] = l[i++];

}

while(j < n2) {

a[k++] = r[j++];

}

}

void mergeSort(int a[], int left, int right) {

if(left < right) {

int mid = (left + right) / 2;

mergeSort(a, left, mid);

mergeSort(a, mid + 1, right);

mergeArrays(a, left, mid, right);

}

}

//--------------Quick Sort-----------------

int partitionArray(int a[], int low, int high) {

int pivot = a[high];

int i = low - 1;

for(int j = low; j < high; j++) {

if(a[j] <= pivot) {

i++;

swapElements(a[i], a[j]);

}

}

swapElements(a[i + 1], a[high]);

return i + 1;

}

void quickSort(int a[], int low, int high) {

if(low < high) {

int pi = partitionArray(a, low, high);

quickSort(a, low, pi - 1);

quickSort(a, pi + 1, high);

}

}

void sortFunctionForQuickSort(int a[], int n) {

quickSort(a, 0, n - 1);

}

int main() {

// seed for rand() functon

srand(time(0));

// Taking the size as input

int n;

cout << "Enter The Size of Array:\t";

cin >> n;

// Generating and printing size n array

int A[n];

// cout << "Unsorted Array:" << endl;

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

A[i] = (rand() % 10000) + 1;

// cout << A[i] << " ";

}

// Running Sort Algorithm and calculating Time

auto start = chrono::high_resolution_clock::now();

bubbleSort(A, n); // change the sorting algorithm as you wish

// Use auto keyword to avoid typing long

// type definitions to get the timepoint

// at this instant use function now()

auto stop = chrono::high_resolution_clock::now();

// Subtract stop and start timepoints and

// cast it to required unit. Predefined units

// are nanoseconds, microseconds, milliseconds,

// seconds, minutes, hours. Use duration_cast()

// function.

// You can change the values of time here to display in seconds or even minutes.

auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);

// To get the value of duration use the count()

// member function on the duration object

cout << endl << "Duration:\t";

cout << duration.count() << " microseconds" << endl;

return 0;

}

Hope this answer is helpful to you.