How to implement quicksort using recursion?

@ryleigh 

Quick sort is a divide-and-conquer algorithm that relies on partitioning an array into two sub-arrays and then recursively sorting those sub-arrays.

Here is an example implementation of quicksort using recursion in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)

# Example usage
arr = [7, 2, 1, 6, 8, 5, 3, 4]
quickSort(arr, 0, len(arr)-1)
print("Sorted array:", arr)

In this implementation, the partition function selects a pivot element and rearranges the array so that all elements smaller than the pivot are to the left of it and all elements greater than the pivot are to the right of it. The index of the pivot element is then returned.

The quickSort function is the recursive sorting function that repeatedly calls partition on sub-arrays until the entire array is sorted.

Finally, the example usage demonstrates how to use the quickSort function to sort an array.