Combination of Quick Sort and Insertion Sort Algorithm - Assignment Example

?Algorithm Design, Analysis and Implementation Homework 2 To prove T(n) = O(nk + nlg(n/k for a combination of quick sort and insertion sort algorithm: Solution: From the given problem, it is analysed that Quick sort has sorted all elements except a subarray (fewer than k-elements). Insertion sort is run to sort these unsorted elements out of n elements. Total run time T(n) = T(n) for quick sort + T(n) of insertion sort In a quick sort, the sequence of elements to be sorted is divided into two groups such that the elements in group 1 are less than, or equal to, the elements in group 2. This is done by choosing a comparison element and placing all the elements that are less than the comparison element in the first group and the rest of the elements in the second group. This procedure is repeated recursively until the elements are sorted (a part consist of only one element). T(n) = (n-1) + ?1 ? i ? n ti As 1,2,....k-elements are already sorted, we can say that ti =0, where i = 1,2, 3... k. Then, the contribution of quick sort when early stopping is used can be given by, T(n)=(n+1)( ?k ? i ? n ti + ?(1)) = (n+1)( n lg +?(1)) =2n lg +?(n) Thus, T(n) for quick sort =O(nlg(n/k)). Given that, insertion sort is done on a partially sorted array (unsorted k-elements). In general, running time of insertion sort is O(n2 ), where n is the length of the array (total number of elements). In order to provide a solution to this problem, the total array is divided into subarrays of k-elements each, such that k/2? n ? k, then n = O(k) and the running time of insertion sort is O(k2). The total number of such subarrays (m) would then be n/k ? m ? 2n/k., which implies m = O(n/k). The total time spent on insertion sort would then be O(k2)* O(n/k) = O(nk). T(n) for insertion sort = O(nk). Therefore, the total time for this sorting algorithm is as follows: T(n) = O(nk + nlg(n/k) ). Choosing K: Practically, in order for insertion sort to take advantage over quick sort, the calculated T(n) = O(nk+nlg(n/k) ) should be lesser than the running of quick sort = O(nlgn). In that case, either nk= O(nlgn) or nlg(n/k) = O(nlgn). From these two possibilities, we can identify that the largest asymptotic value of k is lg n. Thus, k can pick any value between 1 and lg n. 2. Average sorting algorithm : 2.1 Give an algorithm that k-sorts an n-element array in O(n log(n/k)) time. Solution: From the above problem (1), we find that quick sort sorts k-elements of an n-element array O(n log(n/k)) time. Quick sort sorts by partitioning the given array A[p...r] into two sub-arrays A[p...q] and A[q+1... r] such that every element in A[p...q] is less than, or equal to, elements in A[q+1... r]. This process is repeated until all the elements are sorted. Algorithm for quick sort is given by: A[P] is the pivot key upon which the comparison is made. P is chosen as the median value of the array at each step. If the element is less than, or equal to, the pivot key value, it is moved left. Otherwise, it is moved right. Assuming the best case scenario where each step produces two equal partitions, then T(n)=T(n/2)+T(n/2)+?(n) =2T(n/2)+ ?(n) By Master’s Theorem case 2, T(n) = O(n lg n) In other words, the depth of recursion is log n and at each level/step, the number of elements to be treated is n. If only k-elements are sorted, then the depth of recursion would be n/k and the number of elements would be n at each level, the time taken by this sorting algorithm is given by T(n) = O(n lg (n/k)). 2.2 Show that we can sort a k-well-sorted array of length n in O(n log k) time. As the array is already sorted for k-elements, the remaining steps required to complete the sort would be k (using the results from 1), then T(n) = O(n lg k). 3. Computing the k-th smallest element in the union of the two lists m and n using O(lg m +lg n) time algorithm: Approach 1: Merge sort can be used in this case. It splits the list into two halves, recursively sorts each half, and then merges the two sorted sub-lists. In the given problem, the lists are already sorted; hence, the Merge function of this algorithm would alone be sufficient. Once the lists are merged, the k-th smallest element can be found directly. The function is shown below (& is used for Concatenation operation). However, merging would increase the space of the array to O (m + n). This would result in a linear running time. Approach 2: Merging an array is an extra burden to the algorithm as we are only interested in finding the k-th smallest element. We can use the concept of pointers to solve this. One pointer is defined for each array which follows the below rules: 1. Both pointers are initialized to point to the head of A and B respectively. 2. The pointer that has the smaller value of the two is incremented one step. After taking k-1 steps, the smaller of the two is the k-th smallest element. The running time for this algorithm would be O(k). Approach 3: As the requirement is similar to finding an element in a sorted list, we can go for binary search. This would be the best choice as it helps in achieving logarithmic complexity. Binary search requires that the search space X having m-elements and Y having n-elements should be halved at every step of the iteration. If X[m/2] is greater than Y[n/2], then the upper half of X will be greater than the lower half of both arrays. This implies that all elements to the left of X[m/2] are above the median of the combined arrays; hence, if we compare the median of the two arrays (m+n)/2 with k, we can eliminate one of these halves of both arrays. In each step, either m or n gets halved. Thus, the worst case behaviour would take logm +log n time before either one of the set reduces down to zero. Therefore, the total running time would be log m + log n. Algorithm: 4. Algorithm to find the k-th smallest element in O(n + k lg n) time. In order to find the k-th smallest element in an array, the best solution would be to sort the given array in ascending order. Then the element at position k will be the k-th smallest element. This sorting can be done using quick sort, and the running time would be O(nlg n). In case of finding the minimum or maximum value, i.e. when k=1 or k=n, the process is much simpler and we can pull out the element more easily in O(n) time rather than doing a quick sort. If k is close to 1 or to n, then we can go for Heap sort algorithm, where we are able to construct a max heap of the given elements in O(n) time, then perform k-deletemin operation in O(klg n) time. This will take a total time of O(n+klg n). Similarly, if k is close to n, then we can perform a max heap, which will also contribute the same running time. Hence, Heapsort would be our choice to get the desired running time: Heap Sort Algorithm: 5. Algorithm to match n-Nuts and n-Bolts: Let N[1....n] be the array of Nuts and B[1...n] be the array of Bolts. We can perform randomized quick sort to perform matching between similar nuts and bolts. We pick up a random nut N[i], compare it with all bolts and partition the array of bolts by finding, into two groups: one with bolts smaller than the nut N[i] and the other with bolts larger than the nut N[i]. Then, using the value of bolt that matches N[i] as the pivot value, we partition the array of nuts. This process is repeated until the element of the sub-array becomes zero (no more nuts/bolts to compare). This pair of partitioning operation can be implemented in O(n) time and this will partition the nuts and bolts in a very effective manner such that the matching nut and the bolt forms the pivot value while the bolts and nuts smaller than the pivot value are on one side and the larger ones are on the other side. By applying the analysis used for quick sort in the above problems, we can conclude that the expected running time of this algorithm is then O(nlg n). 6. The second smallest of n-elements can be found with n + [lg n] -2 comparisons in the worst case. The second smallest element can be found by conducting a tournament-like algorithm such that the least of the two compared elements goes to the next level. The comparison between two elements in each pair of the total array at each level would take n-1 time. After log n steps, the last level would be reached and will have only one element. This element would be the smallest one in the array. The second smallest element can, however, be found from the previous step (lg n-1 comparisons). Hence, the total running time = (n-1)+(lg n-1) = n+[lg n]-2. The figure below shows a pictorial representation of this algorithm. Fig 1. Tournament-like comparison of elements in the array to find the second smallest Read More