Free Sample Solution on Introduction To Algorithms- My Assignment Help

Question: Discuss ? Use the Library and other resources to research divide-and-conquer sorting algorithms and how they compare to standard sorting algorithms? Answer: Introduction Two selected sorting algorithms based on divide and conquer technique are, quick sort and merge sort. Another sorting algorithm based on standard technique is bubble sort. In the following sections there will be discussions on three of these algorithms along with comparison between the algorithms based on divide and conquer technique and the algorithm based on standard technique. The comparison will reveal the differences between the performances of the algorithm, if there is any. Quick Sort Quick sort is a divide and conquer based sorting algorithm that is widely used. For an array of n elements, quick sort algorithm will work in the following way, It will pick the pivot element p from the array. Based on the selection of the pivot element the array will be divided into three sub arrays, The pivot element p itself. All elements that are less than p are in sub array 1. All elements that are larger than p are in sub array 2. Then the above steps will be repeated recursively for both of the sub arrays. In this way, in each iteration the selected pivot element will get its right place in the sorted array. Selection of the pivot element is very important for the time complexity of the quicksort algorithm. This is an in place sorting algorithm. As, the algorithm does three basic operation in each iteration, one partitioning and two recursive calls. Partitioning step has time complexity, (n). Hence, for an array with n elements, the time complexity will be, (Cormen, Leiserson, Rivest, Stein, 2011) T(n) = (n) + T(i) + T(n 1- i) here, i is the size of the sub array 1 after partitioning. For initial conditions, T(0) = T(1) = 1. Now, the time complexities for best, average and worst cases are, Best Case Average Case Worst Case The median element is selected as the pivot element in each case. Hence, for an array with n elements, T(n) = (n) + 2T(n/2) = (nlogn) On average the time complexity of quick sort is also (nlogn).(MIT, 2015) The smallest or the largest element of the array has been selected as pivot element in each iteration. Hence, each time there will be one empty sub array and another sub array with one element less from the parent array. Hence, T(n) = (n) + T(n-1) = (n2) Merge Sort Merge sort is another divide and conquer based sorting algorithm that works in the following way, Given an unsorted list or array of n elements, the algorithm divides it recursively into n number of sub lists or sub array. In each iteration a sub list is broken down into halves. Then, the algorithm merges the sub lists repeatedly into sorted sub lists until there is only a single sorted sub list of n elements. The time complexity is, T(n) = 2T(n/2) + (n). Here, (n) is for merging of the n sub lists. Now, Best Case Average Case Worst Case This is (nlogn) Average case running time of merge sort is (nlogn) (Sedgewick Wayne, 2011) When two of the largest values are in two different sub lists. The worst case running time of merge sort is (nlogn). Bubble Sort In bubble sort, given an array of n elements, each element is compared with adjacent element to decide whether it is greater than, less than or same. Then two elements can be swapped based on the comparison. In each iteration, the largest element of the array will be pushed towards the end. The time complexity will be O(n2) as each element can be compared against rest of the elements. Best Case Average Case Worst Case In this case, the array is already sorted. Hence, only one comparison in each step will be needed. Hence, the time complexity is O(n). In average case, the time complexity is O(n2). (Kleinberg Tardos, 2013) In this case, the given array is reversely sorted. Hence the number of comparisons in each iteration will be, (n-1) + (n-2)+ + 2+1 = n(n-1)/2 = O(n2) Comparison of Time Complexities From the time complexity analysis of the algorithms, (McAllister, 2010) Algorithm Best Case Average Case Worst Case Quick sort (nlogn) (nlogn) (n2) Merge sort (nlogn) (nlogn) (nlogn) Bubble Sort O(n) O(n2) O(n2) As, asymptotically O(n2) is bigger than (nlogn), hence, the algorithms based on divide and conquer technique, reduce time for sorting. How Divide and Conquer helps in reduction of time complexity in sorting Divide and conquer use recursion to reduce the time complexity of sorting algorithm. It breaks the problem into smaller sub problem then solves those recursively rather than doing the same thing again and again for the entire problem. Reduction of the problem size helps in reducing the time for solving the problem. Thus time is saved. (Cormen, Leiserson, Rivest, Stein, 2011). References Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2011). Introduction to Algorithms. MIT Press. Kleinberg, J., Tardos, . (2013). Algorithm Design. Pearson. McAllister, W. (2010). Data Structures and Algorithms Using Java. Jones Bartlett Publishers. MIT. (2015). Introduction to Algorithms (SMA 5503). Retrieved from MIT OpenCourseWare: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/ Sedgewick, R., Wayne, K. (2011). Algorithms . Addison-Wesley Professional.