Quick Sort

Logic: Create a pivot element & arrange elements with two partitions, If the elements are lesser than pivot add it to left partition & if elements bigger than the pivot arrange it to right side of partition & make call recursively with the subarray found with same approach.
Time Complexity: Avg O(n^2) .. Best: O(n log (n))
Space Complexity: O(n)

Worst case Time complexity of QuickSort is O(n^2) Let say we have sorted array & we applied Quick sort so the recursion will go as — n , n-1, n-2, n-3….. Which is sum of arithmetic number which is n(n+1)/2 = O(n^2)

//Approach #1 create pivot element & sort elements which are lesser than the pivot to right & bigger on left.
// Here we are taking pivot as last element...
func quickSort(_ arr: inout [Int], _ lowerBound: Int, _ upperBound: Int) {
    if lowerBound < upperBound {
        let pivot = partition(&arr, lowerBound, upperBound)
       // print("pivot is-->", pivot)
        quickSort(&arr, lowerBound, pivot-1)
        quickSort(&arr, pivot+1, upperBound)

func partition(_ arr: inout [Int], _ lowerBound: Int, _ upperBound: Int) -> Int {
   // print("part-- lower, upper---->", lowerBound, upperBound)
    let pivot = arr[upperBound] // pivot
    var i = (lowerBound - 1) // Index of smaller element and indicates the right position of pivot found so far
    for j in lowerBound..<upperBound {
        // If current element is smaller than the pivot
        if arr[j] < pivot {
            i+=1 // increment index of smaller element
            arr.swapAt(i, j)
    arr.swapAt(i,upperBound)// Placing the  pivot at right position so xx(lesser elements) Pivot xx(larger elements)
    return i
var arr = [8, 7, 6, 5]
quickSort(&arr, 0, arr.count - 1)
print("Quick Sort-->", arr)

Leave a Comment

Your email address will not be published. Required fields are marked *