Quick Sort in Ascending 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 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.

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