Quicksort Algorithm

Quicksort is an efficient sorting algorithm that follows the divide and conquer strategy. It works by selecting a pivot element and partitioning the array so that all elements smaller than the pivot come before it, and all elements greater come after. This process is repeated for the left and right subarrays until the entire list is sorted.

        Working of Quick sort

1. Pick a Pivot: Choose one number from the list. This is called the pivot.
2. Divide the List: Rearrange the list so that:
   • All numbers smaller than the pivot go to its left.
   • All numbers greater than the pivot go to its right.
3. Repeat:
   • Now take the left and right sides (subarrays) and do the same steps again—choose a pivot, divide into smaller and greater parts.
4. Keep Splitting until each part has only one number.
5. Once everything is divided like this, the list becomes automatically sorted!

Example:

Sort the array:
[7, 2, 1, 6, 8, 5, 3, 4]

Step 1: Choose a Pivot

Let’s take the last element as pivot, i.e., 4.

Now rearrange so that:

• Elements less than 4 come before
• Elements greater than 4 come after

After rearranging:
[2, 1, 3, 4, 8, 5, 6, 7]
Now 4 is in its correct place.

 Step 2: Now apply Quicksort to left [2, 1, 3] and right [8, 5, 6, 7] parts.

 Sorting Left Part [2, 1, 3]

• Pivot = 3
• Rearranged = [2, 1, 3]
• Now 3 is in correct position.
• Sort [2, 1]
• Pivot = 1 → [1, 2]
• Left part sorted: [1, 2, 3]
•  

▶ Sorting Right Part [8, 5, 6, 7]

• Pivot = 7
• Rearranged = [5, 6, 7, 8]
• Now sort [5, 6] → Already sorted.
• Right part sorted: [5, 6, 7, 8]

Final Sorted Array:

[1, 2, 3, 4, 5, 6, 7, 8]

Quicksort Python code:

function quicksort(arr, low, high):

    if low < high:

        pivot Index = partition(arr, low, high)

        quickSort(arr, low, pivotIndex – 1)

        quickSort(arr, pivotIndex + 1, high)

function partition(arr, low, high):

    pivot = arr[high]

    i = low – 1

    for j = low to high – 1:

        if arr[j] < pivot:

            i = i + 1

            swap(arr[i], arr[j])

    swap(arr[i + 1], arr[high])

    return i + 1

Time Complexity