We have been discussing the advantages and disadvantages of various sorts and se

Question

We have been discussing the advantages and disadvantages of various sorts and searches in class. In this lab we will be comparing the times of each of three sorts and two searches. Choose between MaxMinSort and SelectionSort for the first sort, EnhancedBubble and Insertion for the second sort, and any faster sort from the internet or another text for the third sort. The two searches will be Sequential and Binary.

The runtimes of the sorting and searching algorithms can be examined using the C++ library time.h and its method clock() which can be used to return the current system time in milliseconds (see sample program below). You will have to include time.h and the diffclock method in your program. In the dispatch method (similar to Lab 9 last semester) just get the system time immediately before and immediately after you call any of the searches or sorts. Then subtract the first from the second, and you have the time required for the operation in milliseconds, which you can print. WARNING: Be sure you are not including any input or output in your timed operations; these are very expensive and will swamp your algorithm times!

Add sort methods to the program and the appropriate calls to clock() in cases 5-of the switch statement. Run it and fill out the tables below. Turn in your source code, the filled out, and your answer to the discussion question below. Note that you will use much larger arrays for the search algorithms than for the sort algorithms; do you see why? Also note that the first couple of times you run a method you might get longer runtimes as it loads the code for that method. Ignore these times and use the "steady-state" times you get on subsequent runs. On a separate sheet, discuss what you found out about the different sort and search algorithms. Explain the times you see in terms of the known complexities of the algorithms. Remember that the most interesting thing is not the absolute time required by the algorithms, but how the time changes as the size of the input doubles and whether the data is already sorted or not.

Run order: read a size for the partial processing of the array, fill it with random numbers. Call first sort, call first sort again, call second sort, call second sort again, call the third sort, and then call the third sort again. Enter times into table. Repeat these steps for each size listed under the sorts. For the searches, read in a size, fill the array with sorted values, call sequential search, and then call binary search. Always use -1 for the target value – the worst case scenario.

#include <stdio.h>
#include <iostream>
#include <time.h>
using namespace std;

// GLOBAL DEFINITIONS

const int NROWS = 1600000;

int list [NROWS];

int size;

clock_t begin, end; // used to hold the times generated by clock()

//------------------------------------------------------------

// Find the difference in times

//-------------------------------------------------------------

double diffclock(clock_t begin, clock_t end)

{

double diffticks = end-begin;

double diffms = (diffticks*1000)/CLOCK_PER_SEC;

return diffms;

}

//------------------------------------------------------------

// randomize -- fills the array with randomly generated integers

// between 1 and 100, inclusive

//------------------------------------------------------------

void randomize(int list [], int size)

{

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

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

}

//------------------------------------------------------------

// fillSorted -- fills the array with sorted values

// NOT REALLY NEEDED FOR SORTS!!!

//------------------------------------------------------------

void fillSorted(int list [], int size)

{

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

list[i] = i + 2;

}

//------------------------------------------------------------

// print -- prints array elements with indices, one per line

// DO NOT USE UNLESS TESTING A SMALL PORTION OF THE ARRAY!!!!

//------------------------------------------------------------

viod print(int list [], int size)

{

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

cout << i << ": " << list[i] << " ";

}

//------------------------------------------------------------

// linearSearch -- takes a target value and returns the index

// of the first occurrence of target in the list. Returns -1

// if target does not appear in the list

//------------------------------------------------------------

int linearSearch(int list [], int size, int target)

{

int location = -1;

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

if (list[i] == target)

location = i;

return location;

}

//------------------------------------------------------------

// sortIncreasingFirst -- uses __________sort

//------------------------------------------------------------

void sortIncreasingFirst(int list [], int size)

{

// fill in code to sort ascending

}

//------------------------------------------------------------

// sortDecreasingSecond -- uses ___________sort

//------------------------------------------------------------

void sortDecreasingSecond(int list [], int size)

{

// fill in code to sort in descending order

// trust me !!!

}

//------------------------------------------------------------

// sortIncreasingThird -- uses ___________sort

//------------------------------------------------------------

void sortIncreasingThird(int list [], int size)

{

// fill in code to sort ascending

}

//------------------------------------------------------

// dispatch -- takes a choice and does what needs doing

//------------------------------------------------------

void dispatch(int choice)

{

int loc;

int val; // target

switch(choice)

{

case 0:

cout << "Good Bye" << endl;

break;

case 1:

print(list);

break;

case 2:

cout << "How big should the list be?"<< endl;

cin >> size;

randomize(list, size);

cout << “You will be using “ << size <<

“ positions of the array."<< endl;

cout << "List is filled with random elements." << endl;

break;

case 3: //only have to use this for the searches

cout << "How big should the list be?"<< endl;

cin >> size;

fillSorted(list, size);

cout << "List is filled with sorted elements."<< endl;

break;

case 4:

cout << "Enter the value to look for: " << endl;

cin >> val;

loc = linearSearch(list, size, val);

if (loc != -1)

cout << "Found at location " << loc << endl;

else

cout << "Not in list"<< endl;

break;

case 5:

cout << "Enter the value to look for: " << endl;

cin >> val;

loc = binarySearch(list, size, val);

if (loc != -1)

cout << "Found at location " << loc << endl;

else

cout << "Not in list" << endl;

break;

case 6:

sortIncreasingFirst(list, size);

cout << "List has been sorted."<< endl;

break;

case 7:

sortDecreasingSecond(list, size);

cout << "List has been sorted."<< endl;

break;

case 8: // add code to call sortIncreasingThird

default:

cout << "Sorry, invalid choice"<< endl;

}

}

//------------------------------------------------------

// printMenu -- prints the user's choices

//------------------------------------------------------

void printMenu()

{

cout << " Menu " << endl;

cout << " ====" << endl;

cout << "0: Quit" << endl;

cout << "1: Print the list" << endl;

cout << "2: Create a new list of a given size and fill with random numbers" << endl;

cout << "3: Fill the list with already sorted elements" << endl;

cout << "4: Use linear search to find an element" << endl;

cout << "5: Use binary search to find an element " <<

"(list must be sorted in increasing order)" << endl;

cout << "6: Use first sort to sort the list into " <<

" increasing order" << endl;

cout << "7: Use second sort to sort the list into " <<

" decreasing order" << endl;

cout << "8: Use the third sort to sort the list into " <<

" increasing order" << endl;

cout << " Enter your choice: " << endl;

}

//------------------------------------------------------

// main -- creates an initial list, then repeatedly prints

// the menu and does what the user asks until they quit

//------------------------------------------------------

int main()

{

int choice;

printMenu();

cin >> choice;

while (choice != 0)

{

dispatch(choice);

printMenu();

cin >> choice;

}

return 0;

}

Explanation / Answer

www.cs.rit.edu/~vcss233/Labs/lab05 -

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.