Quick Sort in Descending Order in Python

1. Introduction

In this blog post, we will learn how to write a Python program to sort an array of integers in a Descending Order using the Quick Sort algorithm.

Quick Sort is a renowned sorting algorithm that operates by selecting a 'pivot' element and partitioning the array in such a manner that all elements greater than the pivot are positioned before it, while all lesser elements come after it. This method is recursively applied to the smaller arrays. This guide will explore the implementation of Quick Sort in Python for sorting in descending order.

2. Program Overview

1. quick_sort(): The central function in the Quick Sort algorithm.

2. partition(): A helper function to perform the partitioning of the array around the pivot.

3. A sample list to showcase the sorting process.

3. Code Program

def quick_sort(arr, low, high):
    if low < high:
        # Determine partition index
        pi = partition(arr, low, high)

        # Recursively sort elements before and after partition
        quick_sort(arr, low, pi-1)
        quick_sort(arr, pi+1, high)

def partition(arr, low, high):
    # Opt for the rightmost element as the pivot
    pivot = arr[high]

    # Pointer for the lesser element
    i = low - 1

    # Traverse all elements
    for j in range(low, high):
        if arr[j] >= pivot:
            # If element greater than pivot is found, increase the pointer
            i = i + 1

            # Swap the two elements
            arr[i], arr[j] = arr[j], arr[i]

    # Exchange the pivot element with the lesser element indicated by i
    arr[i + 1], arr[high] = arr[high], arr[i + 1]

    # Return the partition point
    return i + 1

def print_list(arr):
    for i in arr:
        print(i, end=" ")
    print()

# Driver segment to test the functions
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Unsorted list is:")
    print_list(arr)

    quick_sort(arr, 0, len(arr)-1)

    print("\nList sorted in descending order is:")
    print_list(arr)

Output:

Unsorted list is:
64 34 25 12 22 11 90 

List sorted in descending order is:
90 64 34 25 22 12 11 

4. Step By Step Explanation

1. quick_sort(): The principal function that repeatedly splits and sorts the list.

2. partition(): The heart of the algorithm. It determines the pivot element's position, arranges all greater elements to its left, and places all lesser ones to its right.

3. print_list(): A simple function to print the list's elements.

4. Driver segment: Illustrates the Quick Sort's effectiveness with a sample list.

Quick Sort is recognized for its speed and boasts an average time complexity of O(n log n). Yet, in its worst-case scenario, it has a time complexity of O(n^2), observable when working on an already sorted list, albeit in reverse.

Related Python Programs on Sorting Algorithms

1. Bubble Sort in Ascending Order in Python
2. Bubble Sort in Descending Order in Python
3. Selection Sort in Ascending Order in Python
4. Selection Sort in Descending Order in Python
5. Insertion Sort in Descending Order in Python
6. Insertion Sort in Ascending Order in Python
7. Merge Sort in Ascending Order in Python
8. Merge Sort in Descending Order in Python
9. Quick Sort in Ascending Order in Python
10. Quick Sort in Descending Order in Python
11. Heap Sort in Ascending Order in Python
12. Heap Sort in Descending Order in Python