How to implement quicksort using recursion?

Member

by ryleigh , in category: Third Party Scripts , 3 months ago

How to implement quicksort using recursion?

Facebook Twitter LinkedIn Telegram Whatsapp

1 answer

by arnoldo.moen , 3 months ago

@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.

Related Threads:

How to correctly implement recursion for quicksort in java?
How to implement quicksort using iterator format?
How to use recursion in quicksort algorithm in c?
How to implement locks in when using transactions in codeigniter?
How to implement caching using etag in angular?
How to implement a service layer using ember.js?