CS201 – Spring 2001
Prof. Hartman
Homework #7
Due Monday March 26th
by 4:00 pm
Recommended Self-Review problems: Well, there are no self-review problems for searching and sorting, so just make sure you understand selection sort, insertion sort, and bubble sort, along with sequential (linear) search, and binary search. You could search the web for other explanations or neat pages. Let me know if you find anything good.
Homework to be turned in: (remember that all programs must follow the guidelines from handout #3.)
Written
problem:
Modify all 4 sorts in the Example Sorting Code handout (bubble sort, insertion sort, selection sort, quicksort) to count the number of comparisons and swaps that the sort performs. Initialize an array with 10 random integers. Sort this array with each sort and output the number of comparisons and swaps the sort function took to complete the sorting job. Perform this operation again with arrays of 100, 1,000, and 10,000 random integers. Include the output from one of your sample runs and fill out the table below. Which sort do you think is best, based on your data? If you consider the fact that swaps are far more expensive in terms of memory and time than comparisons, do you think any of the sorting procedures are better than the rest?
Comparisons Swaps
Sorts 10 100 1000 10000 10 100 1000 10000
Bubble
Insertion
Selection
Quicksort
Programming problems:
2.
(10 pts) Sorting
Arrays
Write a function called sort that will take in an array of integers along with an integer indicating the size of the array and will sort the array. Use this function in a program that creates an array of 50 random integers, prints out the unsorted array, sorts the array, and then prints out the sorted array to the screen. You may use the example sorting code if you wish. This is a very easy problem.
3.
(10 pts) Binary
Search
Write a function that uses binary search (you may start with the code from the text or write your own) to determine whether or not a given value is in a given an array of integers. The parameters for your function should be the array, an integer specifying the size of the array, and an integer to search for in the array. If the element is in the array, it should return the subscript that the element is located at. If the element is not in the array, the function should return -1.
Use the function in a program that takes in an already sorted array (you do not need to sort it) and a number to search for. The program then outputs either the array subscript where the element is located or a message that the element is not in the array.
Write a function that will output the element at the 25th percentile in an array and the 75th percentile in the same array. One can find the 25th percentile by finding the first element that is at least 25% of the way into a sorted array. For example, in a sorted array of 100 elements it would be the 25th element. In a 99 element array it would still be the 25th element (99 * 0.25 = 24.75, and so you go to the first whole element after the 25th percentile, i.e., the 25th one). Similarly, the 75th percentile of a 50 element would be the 38th element (50 * 0.75 = 37.5, and so you go up to the next whole number, 38). Note that you cannot assume that the array is already sorted. You must sort it (you can use any sort you would like; the sort you created in problem 2 will work just fine). Test this function on 3 different 1000-element arrays of random integers.
Hint: There is a function in the cmath library that might be really useful for finding the next whole integer after a fractional value.