Quicksort Implementation in Python

By

In this tutorial, we will share quicksort implementation in Python. Quicksort is a sorting algorithm that divides and conquers an input list.

It works by selecting a pivot element from the list and partitioning the other elements into two sublists based on whether they are less than or greater than the pivot.

The pivot element is then placed in its final position in the sorted list, and the sublists are recursively sorted using the same process.

Also Read: How To Create a Python Web Server

How does the Quicksort algorithm work?

Here is a more detailed example of how the quicksort algorithm works:

  • Select a pivot element from the list. This element will be used to partition the list into two sublists.
  • Divide the list into two sublists: a left sublist containing elements less than the pivot and a right sublist containing elements greater than the pivot.
  • Recursively sort the left and right sublists using the same process.
  • Concatenate the sorted left sublist, the pivot element, and the sorted right sublist to obtain the final sorted list.

Quicksort is a fast, in-place sorting algorithm with a time complexity of O(n*log(n)), making it well-suited for sorting large lists.

However, it has a worst-case time complexity of O(n^2), which can occur if the pivot element is not chosen wisely or the input list is already partially sorted.

Also Read: 15 Most Common Python Array Programs

quicksort implementaion in python

Also Read: How to Create Python Empty Set

Quicksort Pseudo Code

Quicksort is a popular and effective sorting algorithm widely used in practice due to its simplicity and efficiency.

procedure quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1)
        quicksort(A, p + 1, hi)

procedure partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi - 1 do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

This pseudo-code implementation of quicksort works by first defining a quicksort function that takes in an array A and two indices, lo and hi, representing the lower and upper bounds of the subarray to be sorted.

The quicksort function first checks if lo is less than hi, and if so, calls the partition function to partition the array around a pivot element. It then recursively calls itself on the left and right sublists obtained from the partitioning.

Also Read: How To Automate Google Search With Python

The partition function selects the last element of the array as the pivot element. It uses a loop to divide the array into two sublists: a left sublist containing elements less than the pivot and a right sublist containing elements greater than or equal to the pivot.

The pivot element is then placed in its final position in the sorted array, and the partition function returns the index of the pivot element.

This pseudo-code implementation of quicksort can be used as a starting point for implementing the algorithm in a particular programming language.

Also Read: Pattern Programs in Python [Star and Alphabetical Patterns]

Quicksort Implementation in Python

Quicksort is a fast, in-place sorting algorithm that works by partitioning the input list around a pivot element and then recursively sorting the resulting sublists. Here is an example implementation of quicksort in Python:

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

This implementation works by selecting the middle element of the input list as the pivot and then creating three sublists: one for elements that are less than the pivot, one for elements that are equal to the pivot, and one for elements that are greater than the pivot.

Also Read: 10 Best Programming Apps To Learn Python

It then recursively sorts the left and right sublists and returns the concatenation of the sorted left list, the middle list, and the sorted right list.

Here is an example of how to use this function:

arr = [5, 3, 8, 6, 1, 9, 2, 7]
sorted_arr = quicksort(arr)
print(sorted_arr)  # [1, 2, 3, 5, 6, 7, 8, 9]

This will print the sorted version of the input list [5, 3, 8, 6, 1, 9, 2, 7], which is [1, 2, 3, 5, 6, 7, 8, 9].

Also Read: Graph Plotting in Python Using Matplotlib

Quicksort Time Complexities

In the average case, quicksort is a fast, in-place sorting algorithm with a time complexity of O(nlog(n)). This means that the time required to sort a list of n elements using quicksort is proportional to nlog(n).

This makes quicksort well-suited for sorting large lists, as the time complexity grows slowly with the input size.

However, quicksort also has a worst-case time complexity of O(n^2), which can occur if the pivot element is not chosen wisely or if the input list is already partially sorted.

Also Read: How to Convert Binary to Decimal in Python [5 Methods]

In the worst case, quicksort may require a time complexity of O(n^2) to sort the list, which can be slow for significant inputs.

Quicksort is a fast and efficient sorting algorithm in the average case. Still, it is essential to consider the worst-case time complexity when choosing a sorting algorithm for a particular application.

Also Read: Intro to Threading in Python [Understand With Examples]

Quicksort Applications

Quicksort is a popular and effective sorting algorithm with several applications in various fields. Some examples of applications where quicksort is commonly used include:

  • Data processing: Quicksort is often used to sort large datasets in various fields, such as finance, healthcare, and marketing. It is a fast and efficient algorithm that can handle large amounts of data and is well-suited for sorting data in place.
  • Computer science: Quicksort is a fundamental algorithm in computer science and is often taught as a basic sorting algorithm in introductory computer science courses. It is also used in various applications, such as searching and data structure implementation.
  • Software development: Quicksort is often used to sort data in various applications, such as databases, search engines, and data analysis tools. It is a fast and efficient algorithm that is well-suited for sorting large amounts of data.

Quicksort is a widely used and effective sorting algorithm with many applications in various fields.

Other tutorials:

Related Posts

Scroll to Top