How to implement quicksort in Python?

General Discussions
,
1

How do I implement quicksort Python?

I am totally new to Python and I am trying to implement quicksort in it. Could someone please help me complete my code?

I do not know how to concatenate the three arrays and print them.

def sort(array=[12,4,5,6,7,3,1,15]): less = [] equal = [] greater = []

if len(array) > 1:
    pivot = array[0]
    for x in array:
        if x < pivot:
            less.append(x)
        if x == pivot:
            equal.append(x)
        if x > pivot:
            greater.append(x)
        sort(less)
        sort(pivot)
        sort(greater)

Can someone guide me on how to correctly complete this quicksort python function?

2

Hi @Asheenaraghununan

To address the issue with recursion and array concatenation in the original code, the problem lies in not properly capturing and returning the results from the recursive calls. Here’s a simple fix to make it work:

def quicksort(array=[12,4,5,6,7,3,1,15]):
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    less = [x for x in array[1:] if x < pivot]
    equal = [x for x in array if x == pivot]
    greater = [x for x in array[1:] if x > pivot]
    
    return quicksort(less) + equal + quicksort(greater)

# Example usage
print(quicksort([12,4,5,6,7,3,1,15]))

Explanation:

In this solution, we correctly recurse on the less and greater arrays and concatenate the results with the equal array. The quicksort function now returns the sorted array as expected.

Thank you!

3

In-Place Quicksort Another way to implement quicksort python is to sort the list in-place, without needing extra space for less, equal, and greater arrays.

def quicksort(arr): if len(arr) <= 1: return arr pivot = arr[0] left = [] right = []

for x in arr[1:]:
    if x < pivot:
        left.append(x)
    else:
        right.append(x)

return quicksort(left) + [pivot] + quicksort(right)

Example usage

print(quicksort([12,4,5,6,7,3,1,15]))

Explanation: Here, the code uses a similar logic but returns the sorted list using the left and right sublists, and the pivot is inserted in the middle.

4

Hey EveryOne!

Wishing you all the best!

To understand Python’s built-in sorting better, let’s look at how you can implement a quicksort function that behaves similarly. The goal is to sort an array by dividing it into smaller parts and sorting those parts, which Python’s built-in sort() function does internally.

Here’s a simple way to do it with Python:

def quicksort(arr):
    if len(arr) <= 1:  # Base case: If the array is empty or has one element, it’s already sorted
        return arr
    pivot = arr[0]  # Take the first element as the pivot
    less = [x for x in arr[1:] if x < pivot]  # Elements smaller than the pivot
    greater = [x for x in arr[1:] if x >= pivot]  # Elements greater than or equal to the pivot
    
    # Recursively sort the 'less' and 'greater' parts and combine them with the pivot
    return quicksort(less) + [pivot] + quicksort(greater)

# Example usage
arr = [12, 4, 5, 6, 7, 3, 1, 15]
sorted_arr = quicksort(arr)
print(sorted_arr)

Explanation: This quicksort function works by selecting a “pivot” element (in this case, the first element of the array). It then divides the other elements into two groups: those smaller than the pivot (less) and those greater than or equal to it (greater). The function recursively sorts these two groups, finally combining the results.

This method is similar to how Python’s built-in sort() function works, but with more manual steps involved.

Thank you!