A taste of Python quick sort

A taste of Python quick sort

wiki

What is quick sort?

The definition of Wikipedia is: quick sort, also known as partition exchange sort , abbreviated as fast sort , a sorting algorithm . Under average conditions, sort n items

Comparisons. In the worst case

Comparisons, but this situation is not common. In fact, quicksort is usually significantly faster than other algorithms because its inner loop can be achieved very efficiently on most architectures.

step

Quick sort steps

Quicksort uses a divide-and-conquer strategy to divide a list into two sub-lists.

  • Pick an element from the sequence and call it a "pivot",
  • Reorder the sequence, all elements smaller than the reference value are placed in front of the reference, and all elements larger than the reference value are placed behind the reference (the same number can go to either side). After this partition is over, the benchmark is in the middle of the sequence. This is called a partition operation.
  • Recursively sort the sub-sequences of elements smaller than the reference value and the sub-sequences of elements greater than the reference value.

For example?

For example, there is an array

96 69 1314 520 666

1. Selecting a base number is the privot mentioned earlier, a number with a relatively large size.

Generally, the last number is taken. Here we take 666 as the base number. Compare the numbers in the array with 666 in turn. Put the numbers smaller than 666 on the left, and put those larger than 666 on the right. This has the following results:

96 69 520 666 1314

2. Determine the number of intervals. After the first step, there is only one number in the right interval, and there is no number to compare with it, so there is no need to repeat the operation. The left interval also has:

96 69 520

3. Repeat step 1, select 520 as the benchmark number, and get the comparison result:

96 69 520

4. Repeat step 1, select 69 as the benchmark number, and get the comparison result:

69 96

5. In this way, there is only one number on the left and right intervals, which marks the completion of the sorting. Finally, all the intervals are combined to get the sorting result:

69 96 520 666 1314

Code

Code!

def quick_sort(lst):
    _less = [] # Store the value less than the base number
    _greater = [] # Store the value greater than the base number
   # Recursive functions must have exit conditions
    if len(lst) <= 1:
        return lst
    # Base number, directly get the last one of src
    _pivot = lst.pop()
    for _item in lst:
        if _item <= _pivot: 
            _less.append(_item)
        else: 
            _greater.append(_item)
    # The python list used here is a feature that can be added directly
   # Recursive thinking is very important, to deal with more than 1 in the list
    return quick_sort(_less) + [_pivot] + quick_sort(_greater)

The code uses a recursive approach, and there are some optimizations, such as using a generator to optimize the value acquisition of the list.

l = [69, 96, 520, 666, 1314]
print(quick_sort(l))
[69, 96, 520, 666, 1314]

If you are still interested in today's content, why not like it before leaving?

If you are interested enough to appreciate me, don’t hesitate~

Reference: https://cloud.tencent.com/developer/article/1153744 A taste of Python quick sort-Cloud + Community-Tencent Cloud