# 1. Introduction

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

Quick Sort is a highly efficient sorting algorithm that works by selecting a 'pivot' element and partitioning the array such that all elements less than the pivot come before it, while all elements greater come after it. The process is then recursively applied to the smaller arrays. This guide covers the implementation of Quick Sort in Python for sorting in ascending order.

# 2. Program Overview

1. quick_sort(): The main function that implements the Quick Sort algorithm.

2. partition(): A utility function to handle the partitioning of the array around the pivot.

3. A sample list to test the sorting process.

# 3. Code Program

``````def quick_sort(arr, low, high):
if low < high:
# Find 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):
# Choose the rightmost element as pivot
pivot = arr[high]

# Pointer for greater element
i = low - 1

# Traverse through all elements
for j in range(low, high):
if arr[j] <= pivot:
# Increment the pointer if element smaller than pivot is found
i = i + 1

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

# Swap the pivot element with the greater element specified by i
arr[i + 1], arr[high] = arr[high], arr[i + 1]

# Return the position from where partition is done
return i + 1

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

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

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

print("\nSorted list in ascending order is:")
print_list(arr)
``````

### Output:

```Original list is:
64 34 25 12 22 11 90

Sorted list in ascending order is:
11 12 22 25 34 64 90
```

# 4. Step By Step Explanation

1. quick_sort(): The primary function that recursively divides the list and sorts it.

2. partition(): The crux of the algorithm. This function decides the position of the pivot element, places all lesser elements to the left of the pivot, and greater ones to its right.

3. print_list(): A helper function to print the elements of the list.

4. Driver code: Demonstrates the functionality of Quick Sort using a sample list.

Quick Sort is one of the fastest sorting algorithms with an average time complexity of O(n log n). However, its worst-case performance is O(n^2), which can be observed when sorting an already sorted list.