Sort a list of integers using a sorting algorithm of your choice in Python

Write a function to sort a list of integers using a sorting algorithm of your choice e.g., bubble sort, quicksort in Python?

Let's implement a sorting function using the quicksort algorithm in Python. Quicksort is a widely used sorting algorithm known for its efficiency and average-case time complexity of $O(n \log n)$.

Here's the implementation:

def quicksort(arr):

    if len(arr) <= 1:

        return arr

    else:

        pivot = arr[0]

        left = [x for x in arr[1:] if x <= pivot]

        right = [x for x in arr[1:] if x > pivot]

        return quicksort(left) + [pivot] + quicksort(right)

# Example usage:

if __name__ == '__main__':

    # Example list to be sorted

    my_list = [3, 6, 8, 10, 1, 2, 1]

    # Sorting the list using quicksort

    sorted_list = quicksort(my_list)

    # Print the sorted list

    print("Sorted list:", sorted_list)

Explanation:

1. Quicksort Function (quicksort):

   • Takes a list arr as input.
   • If the list has 1 or fewer elements (len(arr) <= 1), it returns the list as it is already sorted.
   • Otherwise, it selects the first element (pivot) as the pivot.
   • It partitions the list into two sublists: left (containing elements less than or equal to pivot) and right (containing elements greater than pivot).
   • Recursively applies quicksort to both left and right sublists, and concatenates them along with the pivot element to produce the sorted list.

2. Example Usage:

   • Demonstrates how to use the quicksort function to sort a list of integers (my_list).
   • Prints the sorted list after sorting.

This implementation of quicksort is simple and recursive, using list comprehensions to partition the list around the pivot element. It sorts the list in place and has an average-case time complexity of $O(n \log n)$.