1. Consider the unsorted array: 92, 81, 73, 44, 35, 56, 89, 68. Imagine that you run a sorting algorithm on the array, and at some moment in time, the array is ordered as: 81, 92, 73, 44, 35, 56, 68, 89. Which of the following sorting algorithms may have been running?
Explain your answer.
2. Consider the following unsorted arrays of numbers: 5, 8, 3, 7, 9. Obtain the numbers in sorted order (descending) by applying the quick sort algorithm. You are required to outline each step of the algorithm (i.e., show the state of the list after each iteration of the algorithm). Assume that the first element is always picked as the "pivot".
3. Is the following tree a binary tree? If so, is it a binary search tree? Explain your answer. see image.
4. Is the following tree a binary search tree? Explain your answer. see image.
5. Linear and Binary Search
Objective: After completion of this lab, you will be able to
Lab Exercise
Assume that you have an array of numbers sorted in ascending order.
(a) Write a function called LinearSearch() which searches the function linearly and determines if a particular element is in the array. The function returns true is the element is in the array, otherwise it returns false. Call the LinearSearch() function from the main.
(b) Write a function called IterBinarySearch() which iteratively performs a binary search and determines if a particular element is in the array. The function returns true is the element is in the array, otherwise it returns false. Call the IterBinarySearch() function from the main.
(c) Write a function called RecursiveBinarySearch() which recursively performs a binary search and determines if a particular element is in the array. The function returns true is the element is in the array, otherwise it returns false. Call the RecursiveBinarySearch() function from the main.
Your code should have the following characteristics:
1. Compile without error.
2. Produce correct output.
3. Good programming structure.
4. Comments. (Title, Abstract, Author, ID, and Date are mandatory.)
5. Meaningful and related variable names.
6. In this assignment you will implement a sorting algorithm, which has not been covered in class. We will call this sorting algorithm CoolSort(). We will take advantage of insertion sort for designing this sorting algorithm. The description of the sorting algorithm is as follows.
We will first choose a decreasing sequence of numbers that ends at 1. For example, let us consider the sequence of step sizes H = 5, 3, 1. You can choose any decreasing sequence. Note that the first element of the sequence is less than the number of elements in the array.
For each H, sort sub-arrays that start at arbitrary element and include every Hth element using insertion sort. For example, consider the following array a = [ 62 83 18 53 07 17 95 86 47 69 25 28].
An example run of CoolSort with gaps 5, 3 and 1 is shown below.
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12
Input 62 83 18 53 07 17 95 86 47 69 25 28
H = 5 17 28 18 47 07 25 83 86 53 69 62 95
H = 3 17 07 18 47 28 25 69 62 53 83 86 95
H = 1 07 17 18 25 28 47 53 62 69 83 86 95
The first pass, 5-sorting, performs insertion sort on separate subarrays (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). For instance, it changes the subarray (a1, a6, a11) from (62, 17, 25) to (17, 25, 62). The next pass, 3-sorting, performs insertion sort on the subarrays (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12). The last pass, 1-sorting, is an ordinary insertion sort of the entire array (a1,..., a12).
As the example illustrates, the subarrays that CoolSort operates on are initially short; later they are longer but almost ordered.
Though unintuitive, it can be shown that the above algorithm has a runtime of O(N^3/2) in comparison to selection sort which has a runtime of O(N^2). That is why this algorithm is cool!
Sample Test Case 1
Input = [2, 5, 6, 4, 10, 9, 8, 1, 10, 5] and H = [5, 3,1]
Output = [1, 2, 4, 5, 5, 6, 8, 9, 10, 10]
Sample Test Case 2
Input = [2, 5, 9, 4, 10, 7, 8, 1, 11, 5] and H = [5, 2,1]
Output = [1, 2, 4, 5, 5, 7, 8, 9, 10, 11]
Your code should have the following characteristics :
1. Compile without error.
2. Produce correct output.
3. Good programming structure.
4. Comments. (Title, Abstract, Author, ID, and Date are mandatory.)
5. Meaningful and related variable names.