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