Quick sort using Python

Quick sort is a commonly used sorting algorithm with a time complexity of O(nlogn). In practical applications, quick sort is usually much faster than other sorting algorithms. Python provides many built-in sorting functions, but it's still important to understand and implement quicksort. In this article, we will implement the quick sort algorithm through Python.

The working principle of quick sort is to select a pivot value (pivot), then put all elements in the list that are smaller than the pivot value in a sublist, and put all elements that are greater than the pivot value in another sublist List. The two sublists are then quickly sorted recursively. Eventually, all sublists will be recursively sorted and then merged into a single sorted list.

The following is the code to implement quick sort in Python:

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

In the above code, we first check the length of the list. If the list length is less than 2, we return the original list. Otherwise, we select the first element of the list as the pivot value. We then use list comprehensions to put elements less than or equal to the pivot value into one list, and elements greater than the pivot value into another list. Next, we recursively sort the smaller and larger lists and concatenate the sorted lists together, with the pivot value placed in the middle of the concatenated lists.

This algorithm needs to choose a suitable benchmark number. If the chosen pivot number happens to be the largest (or smallest) value in the list, then the recursively sorted sublist size is reduced by only 1. In this case, the time complexity of the quicksort algorithm may degenerate to O(n2). To avoid this situation, we can use the method of randomly selecting the base value. This method guarantees the size of the recursively sorted sublists on average in cases where the base value is not the largest (or smallest) value in the list.

The following is the Python code for randomly selecting a benchmark value:

import random

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot_index = random.randint(0, len(arr) - 1)
        pivot = arr[pivot_index]
        less = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i <= pivot]
        greater = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

In the above code, we first randomly select a benchmark value using the random.randint() function. Then, we put the elements that are less than or equal to the baseline value into one list, and the elements that are greater than the baseline value into another list, which is similar to the previous implementation.

To summarize, we implemented the quick sort algorithm through Python and used the method of randomly selecting the benchmark value to avoid the imbalance of the size of the recursively sorted sublist. This algorithm is based on the idea of ​​​​Divide and Conquer, which can quickly sort the list with a time complexity of O(nlogn) under average circumstances.

The above is the detailed content of Quick sort using Python. For more information, please follow other related articles on the PHP Chinese website!