Question

Using C++, Python, or Java, write a program that: In this programming exercise you will perform...

Using C++, Python, or Java, write a program that:

In this programming exercise you will perform an empirical analysis of the QuickSort algorithm to study the actual average case behavior and compare it to the mathematically predicted behavior. That is, you will write a program that counts the number of comparisons performed by QuickSort on an array of a given size. You will run the program on a large number of arrays of a certain size and determine the average number of comparisons performed. You will do this for several different sizes and compare the observed results with what is expected.

Using C++, Python, or Java, write a program that:

prompts the user to enter the number n, of arrays to be processed and the size m, of each array

creates an array, of the given size, containing the integers between 1 and m

for the given number of arrays

randomly unsorts the array

sorts the array using the version of QuickSort developed in your text and in class

counts the number of comparisons performed during the partitioning subroutine of the sort

calculates the average number of comparisons performed in processing all the arrays

You will need to use the versions of QuickSort and Partition given in your text since that was what was used to derive the predicted average complexity you will be comparing your results with.

The program should output the number of arrays processed, the size of the arrays processed and the average number of comparisons per array.

For example, if the user enters 50 and 100 the output would be similar to:

# of arrays processed: 50

# of items in each array: 100

average number of comparisons: 926.02 (Your results may be different!)

The following algorithm can be used to unsort an array A, of size m.

1) FOR i := 1 to m

2)    Generate a random number r, between 1 and m

3)    Swap A[i] and A[r]

Use your program to determine the average number of comparisons performed in sorting 1000 arrays for each of the array sizes, 10, 50, 100, 500, 1000, 5000, 10,000, 50,000 and 100,000. Compare the observed average with the average predicted by the derivation of the average-case time complexity in section 2.4 of your text. Display your results in a table comparing the predicted average with the observed average. You will want to look at the percent difference between the predicted and observed values. Write a paragraph discussing your conclusions about any differences you notice and what they tell you about the actual asymptotic behavior of the quick sort.

Incremental Development

It is usually not a good idea to try to code a complicated algorithm from beginning to end. Taking a few extra minutes to create your program incrementally can save you HOURS of debugging. In developing this program, I would suggest the following approach:

Write functions that implement QuickSort and Partition as given in your text.

Write a “main” function that creates the array of exercise 19 on p. 91 and sorts it using your QuickSort function.

Add code to count the number of comparisons performed during the sort. This will require an additional parameter to both QuickSort and Partition.

Check that the number of comparisons used to sort the array of exercise 19 on p. 91 is what it should be.

Write your “unsort” function and test it thoroughly.

Change “main” so that it prompts the user for the size m, of the array, creates an array of size m that contains the integers 1 to m, unsorts it, then uses QuickSort to sort it and counts the comparisons.

Finally, change “main” so that it prompts the user for the number of arrays n, to test and prints the average number of comparisons done.

Homework Answers

Answer #1

Here is the code for quick sort and counting comparisons and average after taking user inout

other part of assignment you have to do by running code with different values and comparing with what is told in class (as these are not shared in question)

I used last element as pivot in partition which is common among most textbooks

#include <iostream>
#include <stdlib.h>
using namespace std;

// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high, int *comparisons)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
*comparisons = *comparisons+1;
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high, int *comparisons)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high, comparisons);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1, comparisons);
quickSort(arr, pi + 1, high, comparisons);
}
}

void unsort(int arr[], int n)
{
int r = 0;
for(int i = 0; i < n; i++)
{
r = rand()%n;
swap(&arr[i], &arr[r]);
}
}

int main()
{
int n, m;
cout << "Enter number of times to sort array: ";
cin >> n;
  
cout << "Enter size of array to be sorted: ";
cin >> m;
  
int *arr = new int [m];
  
for(int i = 0; i < m; i++)
{
arr[i] = i+1;
}
  
long totalComparisons = 0;
  
for(int i = 0; i < n; i++)
{
unsort(arr, m);
int comparisons = 0;
quickSort(arr, 0, m-1, &comparisons);
totalComparisons += comparisons;
}
  
delete[] arr;
  
double average = ((double) totalComparisons)/n;

cout << "# of arrays processed: " << n << endl;
cout << "# of items in each array: " << m << endl;
cout << "average number of comparisons: " << average << endl;
  
return 0;
}

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Assignment #4 – Student Ranking : In this assignment you are going to write a program...
Assignment #4 – Student Ranking : In this assignment you are going to write a program that ask user number of students in a class and their names. Number of students are limited to 100 maximum. Then, it will ask for 3 test scores of each student. The program will calculate the average of test scores for each student and display with their names. Then, it will sort the averages in descending order and display the sorted list with students’...
Please answer in C++ with the correct files (in bold). Thanks! Write a program that creates...
Please answer in C++ with the correct files (in bold). Thanks! Write a program that creates three identical arrays, list1, list2, and list3, of 5000 elements. The program then sorts list1 using bubble sort, list2 using selection sort, and list3 using insertion sort and outputs the number of comparisons and item assignments made by each sorting algorithm. Please use the file names listed below since your file will have the following components: Ch18_Ex15.cpp searchSortAlgorithms.h
A. Write a Java program that asks the user to enter “bus” or “subway” or “walk”....
A. Write a Java program that asks the user to enter “bus” or “subway” or “walk”. If the user enters “bus” display “$1.00”. If they enter “subway” display “$1.50 and if they enter “walk” display “Free”. B. Write a java program that creates the following two arrays: String[] candidates = {“S Jones”,”Justin Fairfax”,”Clark Duncan”}; int[] votes = {7345,4324,3211}; Write the code that will search the votes array for the candidate with the largest number of votes and prints the name...
Write a C program that prompts the user to enter a line of text on the...
Write a C program that prompts the user to enter a line of text on the keyboard then echoes the entire line. The program should continue echoing each line until the user responds to the prompt by not entering any text and hitting the return key. Your program should have two functions, writeStr and readLn, in addition to the main function. The text string itself should be stored in a char array in main. Both functions should operate on NUL-terminated...
Write a python program that will perform text analysis on an input text using all of...
Write a python program that will perform text analysis on an input text using all of the following steps: 1. Take the name of an input file as a command line argument. For example, your program might be called using python3 freq.py example1 to direct you to process a plain text file called example. More information is given on how to do this below. 2. Read the contents of the file into your program and divide the text into a...
In c++ Write a program that creates a dynamically allocated array to store students’ grades. The...
In c++ Write a program that creates a dynamically allocated array to store students’ grades. The user should be able to decide the size of the array during run time. Write code to fill this array from the keyboard and then print out the values of your array,
Using python, write the program below. Program Specifications: You are to write the source code and...
Using python, write the program below. Program Specifications: You are to write the source code and design tool for the following specification: A student enters an assignment score (as a floating-point value). The assignment score must be between 0 and 100. The program will enforce the domain of an assignment score. Once the score has been validated, the program will display the score followed by the appropriate letter grade (assume a 10-point grading scale). The score will be displayed as...
1. a)Write a program that displays the name and address of your college in C# b)Write...
1. a)Write a program that displays the name and address of your college in C# b)Write a program that prompts the user for his name and average monthly visa bill. The program displays his name and his annual visa bill. You must match the format exactly: Name: Justin Bieber Annual Visa Bill: $12,000.00 Hint: annual bill = monthly bill * 12 c)Write a program that prompts the user for a letter. The program prints the letter and the number equivalent....
IN JAVA PLEASE write code to MERGESORT an array of user inputted OBJECTS you have two...
IN JAVA PLEASE write code to MERGESORT an array of user inputted OBJECTS you have two different classes in the program being made as objects in the main (Bunny class and Dog Class). ask the user "what kind of animal would you like to sort?" user chooses the type of animal (bunny or dog), then you ask the user how big would you like the array of animals to be (maximum array size = 20)? and then you ask what...
In this lab, you complete a partially prewritten C++ program that uses an array. The program...
In this lab, you complete a partially prewritten C++ program that uses an array. The program prompts the user to interactively enter eight batting averages, which the program stores in an array. The program should then find the minimum and maximum batting average stored in the array as well as the average of the eight batting averages. The data file provided for this lab includes the input statement and some variable declarations. Comments are included in the file to help...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT