Python Program to Implement Quicksort

Quicksort is a sorting algorithm in Python that uses the divide-and-conquer approach to sort elements by recursively partitioning the array and placing elements in the correct order based on a pivot element.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

The Quicksort algorithm divides the array based on a pivot element. Elements less than the pivot go to the left subarray, elements equal to the pivot stay in the middle, and elements greater than the pivot go to the right subarray. This process is repeated recursively until the subarrays are sorted, and then they are merged to obtain the final sorted array.

Here is a working example of the Quicksort algorithm in Python to sort the list [5, 2, 8, 10, 3, 0, 4]:

• Step 1: Choose a pivot element (e.g., 4).
• Step 2: Divide the list into two subarrays: Elements less than the pivot: [2, 3, 0] and Elements greater than the pivot: [5, 8, 10]
• Step 3: Recursively apply Quick Sort to both subarrays.
• Step 4: Combine the sorted subarrays with the pivot element: [2, 3, 0, 4, 5, 8, 10].
• The final sorted list is [0, 2, 3, 4, 5, 8, 10].

Write a Python program that implements the quicksort algorithm to sort a given list of elements.

1. Create a function quicksort that takes a list and two variables start and end as arguments.
2. If end – start is not greater than 1, return.
3. Find the index of the pivot, p by calling the function partition with the list and variables start and end as arguments.
4. Call quicksort with the list and the variables start and p as arguments to sort the list from start to p – 1.
5. Call quicksort with the list, the expression p + 1 and end as arguments to sort the list from p + 1 to end – 1.
6. Define the function partition that takes a list and two variables start and end as arguments.
7. The function parititon uses Hoare’s partition scheme to partition the list.

Here is the source code of a Python program to implement quicksort. The program output is shown below.

def quicksort(alist, start, end):
    '''Sorts the list from indexes start to end - 1 inclusive.'''
    if end - start > 1:
        p = partition(alist, start, end)
        quicksort(alist, start, p)
        quicksort(alist, p + 1, end)
 
 
def partition(alist, start, end):
    pivot = alist[start]
    i = start + 1
    j = end - 1
 
    while True:
        while (i <= j and alist[i] <= pivot):
            i = i + 1
        while (i <= j and alist[j] >= pivot):
            j = j - 1
 
        if i <= j:
            alist[i], alist[j] = alist[j], alist[i]
        else:
            alist[start], alist[j] = alist[j], alist[start]
            return j
 
 
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
quicksort(alist, 0, len(alist))
print('Sorted list: ', end='')
print(alist)

1. The program defines a “quicksort” function that takes a list, start index, and end index as arguments.
2. If the sublist has more than one element, it calls the “partition” function to find the pivot index.
3. Recursively calls “quicksort” to sort the left and right sublists.
4. The “partition” function selects a pivot and rearranges elements to its left and right based on their values.
5. The program prompts the user to enter a list of numbers and converts them into integers.
6. It calls the “quicksort” function to sort the list.
7. The sorted list is displayed.

Time Complexity:
The quicksort algorithm has an average and best-case time complexity of O(n log n), making it efficient for large input sizes. However, in the worst case, it can have a time complexity of O(n²).

Space Complexity: O(log n)
The space complexity is O(log n) due to the recursive calls made by the algorithm.

Testcase 1: In this case, the elements are entered in a random order. The elements entered to sort the array using quicksort are “5, 2, 8, 10, 3, 0, 4”.

Enter the list of numbers: 5 2 8 10 3 0 4
Sorted list: [0, 2, 3, 4, 5, 8, 10]

Testcase 2: In this case, the elements are entered in a reverse order. The elements entered to sort the array using quicksort are “7, 4, 3, 2, 1”.

Enter the list of numbers: 7 4 3 2 1
Sorted list: [1, 2, 3, 4, 7]

To practice programs on every topic in Python, please visit “Programming Examples in Python”.