Python Program For Quick Sort (With Code & Explanation)

In this tutorial, you will learn about the python program for quick sort.

In this article, we will explore the Python program for Quick Sort, a popular sorting algorithm used to arrange elements in a list in ascending or descending order.

Quick Sort is famous for its efficiency and we can use quick sort in various applications.

Quick Sort is a divide-and-conquer sorting algorithm that works by selecting a pivot element from the list and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

Then we recursively sort the sub-arrays.

Python Program for Quick Sort

Here is a Python program for Quick Sort:

def quick_sort(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 quick_sort(left) + middle + quick_sort(right)

# Example usage
my_list = [7, 2, 9, 1, 6, 4, 8, 3, 5]
sorted_list = quick_sort(my_list)
print("My List:", my_list)
print("Sorted:",sorted_list)

You can run this code on our free Online Python Compiler.

Output

In this program, the quick_sort function takes an array as input and returns the sorted array.

It first checks if the length of the array is less than or equal to 1, in which case it returns the array as it is.

Otherwise, it selects a pivot element (in this case, the middle element) and partitions the array into three sub-arrays: left, middle, and right.

It then recursively applies the quick_sort function to the left and right sub-arrays, and finally combines the sorted sub-arrays with the middle array.

The example usage demonstrates how to use the quick_sort function to sort a list of numbers.

To better understand how Quick Sort works, let’s break down the process step by step:

Choosing a pivot

The algorithm selects a pivot element from the list.

The choice of the pivot can affect the performance of the algorithm.

In the given Python program, we choose the pivot as the middle element.

Partitioning the array

The algorithm partitions the array into three sub-arrays: left, middle, and right.

Elements less than the pivot are placed in the left sub-array, elements equal to the pivot are placed in the middle sub-array, and elements greater than the pivot are placed in the right sub-array.

Recursive sorting

The algorithm recursively applies the same process to the left and right sub-arrays until we reach the base case, i.e., when the sub-array has one or zero elements.

In this case, the sub-array is considered sorted.

Combining the sub-arrays

Finally, the sorted left sub-array, middle sub-array, and sorted right sub-array are combined to form the sorted array.

The time complexity of Quick Sort depends on the choice of the pivot and the partitioning of the array.

On average, Quick Sort has a time complexity of O(n log n), where n is the number of elements in the array.

However, in the worst case, where the pivot is always the smallest or largest element, the time complexity can be O(n^2).

Despite this worst-case scenario, we widely use Quick Sort due to its average-case efficiency.

How do you do quick sort in Python?

To implement Quick Sort in Python, you can follow these steps:

1. Define a function quick_sort that takes an array as input.
2. Check if the length of the array is less than or equal to 1. If so, return the array as it is (base case).
3. Select a pivot element from the array. We can don this by choosing the first, middle, or last element, or by using a random element.
4. Partition the array into three sub-arrays: left, middle, and right. Elements less than the pivot go into the left sub-array, elements equal to the pivot go into the middle sub-array, and elements greater than the pivot go into the right sub-array.
5. Recursively apply the quick_sort function to the left and right sub-arrays.
6. Combine the sorted left sub-array, middle sub-array, and sorted right sub-array to form the final sorted array.
7. Return the sorted array.

Here is an example implementation of Quick Sort in Python:

Python Program for Quick Sort

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

How does Python sort a list using Quick Sort?

In Python, the built-in sorted() function uses a variation of the Quick Sort algorithm called Timsort.

Timsort is a hybrid sorting algorithm derived from Merge Sort and Insertion Sort.

When you call sorted() on a list in Python, it internally uses Timsort to sort the elements in ascending order.

Timsort works by dividing the list into smaller sub-arrays, sorting them, and then merging them back together.

Timsort is designed to perform well in a variety of scenarios and takes advantage of already sorted or partially sorted sub-arrays.

It has a time complexity of O(n log n) in the average case and performs efficiently for most datasets.

What is Quick Sort with the first element as the pivot in Python?

In Quick Sort, the choice of the pivot element can affect the efficiency of the algorithm.

One common approach is to use the first element of the array as the pivot.

To implement Quick Sort with the first element as the pivot in Python, you can follow the general Quick Sort algorithm.

However, in the partitioning step, instead of selecting the pivot element from the middle or elsewhere, you would choose the first element as the pivot.

Here’s an example implementation of Quick Sort with the first element as the pivot in Python:

Python Program for Quick Sort

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

What is the recursive program for Quick Sort in Python?

The Quick Sort algorithm is inherently recursive, as it involves partitioning the array and recursively sorting the resulting sub-arrays.

Here’s an example of a recursive program for Quick Sort in Python.

Python Program for Quick Sort

def quick_sort(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 quick_sort(left) + middle + quick_sort(right)

In this program, the quick_sort function recursively calls itself on the left and right sub-arrays until the base case is reached, where the sub-array has one or zero elements.

The sorted sub-arrays are then combined with the middle array to form the final sorted array.

Is Quick Sort suitable for large datasets?

Quick Sort is generally suitable for large datasets due to its average-case time complexity of O(n log n).

Can Quick Sort handle duplicate elements?

Yes, Quick Sort can handle duplicate elements.

How does Quick Sort compare to other sorting algorithms?

Quick Sort is famous for its efficiency and is often faster than other sorting algorithms, especially for large datasets.

However, it is not a stable sorting algorithm, meaning that the relative order of equal elements may change during the sorting process.

In scenarios where stability is important, we prefer other algorithms like Merge Sort or Insertion Sort.

Can I use Quick Sort to sort elements in descending order?

Yes, you can modify Quick Sort to sort elements in descending order.

By simply changing the comparison operator in the partitioning step from < to >, the algorithm will sort the elements in descending order.

Are there any built-in functions in Python for sorting?

Yes, Python provides a built-in function called sorted() that can be used to sort lists, tuples, and other iterable objects.

This function uses the Timsort algorithm, which is a hybrid sorting algorithm derived from Merge Sort and Insertion Sort.

In conclusion, Quick Sort is a powerful sorting algorithm widely used in various applications.

Its divide-and-conquer approach and efficient time complexity make it suitable for sorting large datasets.

Despite its worst-case time complexity, Quick Sort’s average-case performance and simplicity have made it a popular choice among programmers.

By understanding the Python program for Quick Sort and its inner workings, you can leverage this algorithm to efficiently sort your own lists and arrays.

Happy Coding!