Application of Divide & Conquer in Quick Sort
QuickSort is a sorting algorithm based on the Divide and Conquer algorithm that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array.
The key process in quickSort is a partition(). The target of partitions is to place the pivot (any element can be chosen to be a pivot) at its correct position in the sorted array and put all smaller elements to the left of the pivot, and all greater elements to the right of the pivot.
Partition is done recursively on each side of the pivot after the pivot is placed in its correct position and this finally sorts the array.
Choice of Pivot:
There are many different choices for picking pivots.
- Always pick the first element as a pivot.
- Always pick the last element as a pivot
- Pick a random element as a pivot.
- Pick the middle as the pivot.
Time Complexity:
- Worst Case: O(n^2), occurs when the pivot selection consistently results in unbalanced partitions.
- Best Case: O(n log n), occurs when the pivot selection consistently results in balanced partitions.
- Average Case: O(n log n)
Space Complexity: O(log n), for the recursive call stack.
Divide and Conquer Notes for GATE Exam [2024]
Those preparing for the GATE (Graduate Aptitude Test in Engineering) exam in 2024 face many algorithmic challenges. Among the various algorithmic paradigms, “Divide and Conquer” stands out as a powerful approach to problem-solving. In this comprehensive guide for the GATE Exam, Divide and Conquer, and its applications will be explored through a range of important topics. These notes aim to provide a solid foundation for mastering these concepts in preparation for the upcoming GATE exam.
Table of Content
- Introduction to Divide and Conquer
- Application of Divide & Conquer in Binary Search
- Application of Divide & Conquer in Merge Sort
- Application of Divide & Conquer in Quick Sort
- Standard Problems that uses Divide and Conquer Algorithm
- Advantages of Divide and Conquer Algorithm
- Disadvantages of Divide and Conquer Algorithm
- Previously Asked GATE Questions on Divide and Conquer
Contact Us