Reference no: EM13336442

Sorting & Searching

The purpose of sorting is to put a sequence of data records in ascending or descending order based on a sorting key. For example, to sort student records based on last name, or sort football player records based on batting average. The problem of sorting data has been around a long, long time. The purpose of this assignment is to evaluate the performance of two well known sorting algorithms: bubble sort and selection sort. We will do this by calculating the CPU times to sort different types of input data (unsorted, semi-sorted, and sorted). There are two ways to generate unsorted data for sorting experiments. The first way is to use a random number generator and create N values within a range [L..H]. This is like rolling dice over and over again. The second method starts with sorted data and randomly shuffles data around to create unsorted data. This is essentially what we do when we shuffle a deck of cards. Once the sorted data re produced, a specified value (the input "key") within the sorted data can be found by employing different searching techniques.

Program Specification

You are required to design, implement and test a program in C++ to generate N values within a certain range [L..H]. The well known sorting algorithms, bubble sort and selection sort are then applied to the unsorted set of data. The performances of these methods are measured by calculation the CPU running time of each. Given an input key, a specified data can then be searched within the sorted data. The developed program should perform the following operations :

1. Random Generation of Unsorted Values

Using a number generator, the program is to create N values within a range [L..H]. You will need to define a function for generating random numbers. The function will then be called within the main program.

Example input/output might be: ( the output is in italic)

Enter the number of values to be generated: 6

Enter the range : 50

The unsorted generated sequence is :

34 12 6 47 22 19

2. Sorting

You will need to add two functions to your program to sort the list generated in part (a), using bubble sort and selection sort algorithms. Since the output of both algorithms will be the same (sorted list), you will need to only display the result for one of them.

Example input/output might be:

The sorted list is now:
6 12 19 22 34 47

3. Measuring the running-time

The performance of two sorting algorithms should be compared by calculating the CPU time of each algorithm for the same set of data. Calculate the run times for N=1000. If the times are too small to measure, increase N as needed until you can get a CPU time greater than a few seconds. Stop your program if it uses more than a minute of CPU time and decrease N accordingly.

Example input/output might be:

Enter the number of values to be generated: 5000

Enter the range: 100

The unsorted generated sequence is:

34 88 61 47 22 19 77 12 93.............

The sorted list is now:

12 19 22 34 47 61 77 88 93.....

The bubble sort-algorithm sorted the 5000 values in 2.34 second
The selection sort-algorithm sorted the 5000 values in 2.05 second

4. Shuffle the Sorted List

You will need to add a function named, Shuffle to your program, to allow for shuffling the sorted list in part (b). By shuffling the sorted list, we create a semi-sorted list. Shuffling data values inside data array is done by swapping random pairs of values. For example, shuffling three times, will swap 3 random pairs of values. Try a few different values of the "shuffles" parameter to create data that looks semi-sorted (some sequences of values are in the correct order, but others are out of order. Try a few different values of the "shuffles" parameter to choose a value that creates data that looks semi-sorted (some sequences of values are in the correct order, but others are out of order).

Example input/output might be:

How many times would you like to shuffle the sorted list?

The semi-sorted list is now:

6 12 19 22 34 47

6 19 12 22 47 34

5. Searching for a Specific value

You will need to add a function named, Search to your program to allow searching for a specific vale in the sorted list. You are recommended to use the Binary Search algorithm because of its efficiency. Once the function is called within the main program, specifying the key value, the function should return the first occurrence of the value in the list. Your program should also calculate the time for finding the key value.

Example input/output might be:

The sorted list is now:
6 12 19 22 34 47

Enter the key value to be searched: 22

The first occurrence of 22 is at position 4
It took 0.0 4 second s to find the value.

Assignment's Tasks

Task 1: Algorithm Design

You are required to produce a top-level design for your program using pseudocode or flowcharts. In addition to your design, a Function Table should also be provided.

Task 2: Program Development

You are required to implement your designs in C++ Programming Language. Your program should be properly laid out and should be modular, making sure that software engineering aspects of modularity and reusability are fully considered.

Task 3: Program Testing & Documentation

• Devise a test plan carefully, making sure that the purpose of the particular test is clearly stated, the data for each test is specified (that is, any inputs expected from the user or the programmer), and a description of the expected result from the test are also provided.

• Use the test plan to test your program and document your findings. You should provide a hard copy of the actual output from your program, in the same order as your test plan and cross-referenced to it.

• You may like to test some functions separately. Any aspects of your program which you do not test will be assumed not to work.

• Your program must handle incorrect input data. Your testing should then include incorrect input data.

• You are required to provide an annotated code listing in addition to your proof of testing.

Task 4: Program Evaluation

You should evaluate your program, carefully identifying its strengths, weaknesses, and possible areas of improvement. You should also comment on the extent to which your solution correctly satisfies the specification.