Quick Sort
Quick Sort is an efficient, divide and conquer sorting algorithm that works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays: elements less than the pivot and elements greater than the pivot. The sub-arrays are then recursively sorted. Quick Sort is one of the most widely used sorting algorithms due to its efficient average-case performance.
How it Works:
Pick a Pivot: Select an element from the array as the pivot. There are various strategies for selecting the pivot, including picking the first element, the last element, a random element, or the median.
Partitioning: Rearrange the elements in the array such that:
1.All elements less than the pivot are on the left side.
2.All elements greater than the pivot are on the right side.
Recursion: Recursively apply the same procedure to the sub-arrays (left and right of the pivot).
Time Complexity:best case O(nlog(n)) and in worst case O(n2)
Space Complexity:O(log(n))