Which of the following sorting algorithms has the lowest worst-case co...
Worst case complexities for the above sorting algorithms are as follows: Merge Sort — nLogn Bubble Sort — n^2 Quick Sort — n^2 Selection Sort — n^2
View all questions of this test
Which of the following sorting algorithms has the lowest worst-case co...
Explanation:
Merge Sort:
- Merge sort is a divide and conquer algorithm that divides the array into two halves, recursively sorts them, and then merges the two sorted halves.
- The worst-case time complexity of merge sort is O(n log n), where n is the number of elements in the array.
- In the worst case, merge sort will always divide the array into two halves until the individual elements are reached, and then merge them back together. This process requires log n levels of recursion, and at each level, all n elements need to be merged.
- Therefore, the worst-case time complexity of merge sort is O(n log n).
Bubble Sort:
- Bubble sort is a simple comparison-based sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order.
- The worst-case time complexity of bubble sort is O(n^2), where n is the number of elements in the array.
- In the worst case, when the array is in reverse order, bubble sort needs to perform n-1 passes to sort the array. In each pass, it compares and swaps adjacent elements, resulting in n-1 comparisons for the first pass, n-2 for the second pass, and so on.
- Therefore, the worst-case time complexity of bubble sort is O(n^2).
Quick Sort:
- Quick sort is another divide and conquer algorithm that selects a pivot element, partitions the array into two sub-arrays based on the pivot, and recursively sorts the sub-arrays.
- The average-case time complexity of quick sort is O(n log n), but the worst-case time complexity is O(n^2).
- The worst-case scenario occurs when the pivot is always chosen as the smallest or largest element in the array. In such cases, quick sort degrades into a partition with only one element at each level of recursion, resulting in n levels of recursion.
- Therefore, the worst-case time complexity of quick sort is O(n^2).
Selection Sort:
- Selection sort is a simple comparison-based sorting algorithm that repeatedly selects the minimum element from the unsorted portion of the array and swaps it with the first unsorted element.
- The worst-case time complexity of selection sort is O(n^2), where n is the number of elements in the array.
- In the worst case, selection sort needs to find the minimum element n-1 times. In each iteration, it compares the current element with the remaining unsorted portion of the array to find the minimum.
- Therefore, the worst-case time complexity of selection sort is O(n^2).
Conclusion:
- Among the given sorting algorithms, merge sort has the lowest worst-case time complexity of O(n log n).
- Bubble sort, quick sort, and selection sort have worst-case time complexities of O(n^2), which are higher than merge sort.
- Therefore, option 'A' (Merge Sort) is the correct answer.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).