a)A potential variation of Insertion Sort is to use Binary Search – rather than

Question

a)A potential variation of Insertion Sort is to use Binary Search – rather than Linear Search – to find the point in which to insert the next element from the unsorted portion into the sorted portion. How many operations are required to find this point for the next unsorted element? How many operations are required to find these points over the entire algorithm, keeping in mind that the size of the sorted portion grows with each iteration?  

b)The “Selection Problem” is to find the ith smallest element among elements. (Note: when i = n/2, this is the problem of finding the median.) Describe how a complete sort can be used as a (naïve) “brute force” approach to solve the Selection Problem. What is its time complexity?

c) Describe how a partial sort can be used to solve the Selection Problem. Which of Bubble Sort, Insertion Sort, and Selection Sort is best suited for this task? What is its time complexity? What might you differently depending on whether i is closer to 1 or n?

Explanation / Answer

1.

The binary search algorithm has a complexity of O(log(n)) where n is the number of element on which it is applied. Hence for sorted part having j number of item complexity will be O(log(j)).

Now for entire sort of n elements it will be O(log(1)) + O(log(2)) + ... + O(log(n)) = O(log(n!))

2.

Consider an sorted array A of n elements to get the ith smallest element we just have to return A[i - 1] assuming indexing of array is from 0. Getting an item from array element is O(1) operation.

Now to sort this array with "brute force" it will require O(n2) time. Hence complexity for problem is O(n2).

3.

If we have to get ith smallest element we don't actually have to sort an array completely. We can sort partially till we get ith smallest element. So each time we iterate an array we find next smallest element and increase the count. For next iteration we search smallest in remaining unsorted array. When count reaches i we return that element. Exactly similar operation is done by selection sort. Therefore Selection Sort is best suited for this task. The worst case complexity of this will be same as Selection Sort O(n2). Worst case occurs when array is sorted in reverse order and last element i.e. nth smallest is required. If "i" is closer to one we sort array in ascending order. If "i" is closer to n we sort array in descending order.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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