Question

Analyze two sorts in C++, the first being a bubble sort and the second being a quick sort. Create a project for each sort. 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.

Need: 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. The output must also display the runtime.

Answer 1

Part 1

#include <iostream>

#include <ctime>

#include <cstdlib>

using namespace std;

void swap(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}

void bubbleSort(int arr[], int n)

{

int i, j;

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

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

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

swap(&arr[j], &arr[j+1]);

}

void printArray(int arr[], int size)

{

int i;

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

cout << i << ": " << arr[i] << endl;

cout << endl;

}

void generateRandomArray(int *arr, int size) {

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

arr[i] = rand() % 100;

}

}

int main() {

srand(time(0));

for (int i = 10000; i<=40000; i += 10000) {

int arr[i];

generateRandomArray(arr, i);

clock_t tStart = clock();

bubbleSort(arr, i);

clock_t tEnd = clock();

cout << "The sorted array is: " << endl;

printArray(arr, i);

cout << "Sorting took " << (double)(clock() - tStart)/CLOCKS_PER_SEC << " seconds" << endl;

}

}

Part 2

#include <iostream>

#include <ctime>

#include <cstdlib>

using namespace std;

void swap(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}

int partition (int arr[], int low, int high)

{

int pivot = arr[high];

int i = (low - 1);

for (int j = low; j <= high - 1; j++)

{

if (arr[j] < pivot)

{

i++;

swap(&arr[i], &arr[j]);

}

}

swap(&arr[i + 1], &arr[high]);

return (i + 1);

}

void quickSort(int arr[], int low, int high)

{

if (low < high)

{

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

}

}

void printArray(int arr[], int size)

{

int i;

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

cout << i << ": " << arr[i] << endl;

cout << endl;

}

void generateRandomArray(int *arr, int size) {

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

arr[i] = rand() % 100;

}

}

int main() {

srand(time(0));

for (int i = 10000; i<=40000; i += 10000) {

int arr[i];

generateRandomArray(arr, i);

clock_t tStart = clock();

quickSort(arr, 0, i-1);

clock_t tEnd = clock();

cout << "The sorted array is: " << endl;

printArray(arr, i);

cout << "Sorting took " << (double)(clock() - tStart)/CLOCKS_PER_SEC << " seconds" << endl;

}

}