Python implementation of the fast sorting algorithm in detail

This article is an example of a quick sort algorithm implemented in Python. Shared for your reference, as follows:

The basic idea of quick sort is: through a sort of data to be sorted into two independent parts, one of the part of all the data are smaller than the other part of all the data, and then according to the method of these two parts of the data are quickly sorted, the entire sorting process can be carried out recursively, so as to achieve the whole data into an ordered sequence.

As in the sequence [6, 8, 1, 4, 3, 9], 6 is chosen as the base number. Scan from right to left for a number smaller than the benchmark number as 3, swap the positions of 6 and 3, [3, 8, 1, 4, 6, 9], then scan from left to right for a number larger than the benchmark number as 8, swap the positions of 6 and 8, [3, 6, 1, 4, 8, 9]. Repeat the process until all the numbers to the left of the benchmark number are smaller and all the numbers to the right are larger. Then perform the above method recursively for the sequences to the left and right of the base number, respectively.

The realization code is as follows:

def parttion(v, left, right):
  key = v[left]
  low = left
  high = right
  while low < high:
    while (low < high) and (v[high] >= key):
      high -= 1
    v[low] = v[high]
    while (low < high) and (v[low] <= key):
      low += 1
    v[high] = v[low]
    v[low] = key
  return low
def quicksort(v, left, right):
  if left < right:
    p = parttion(v, left, right)
    quicksort(v, left, p-1)
    quicksort(v, p+1, right)
  return v
s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
print("before sort:",s)
s1 = quicksort(s, left = 0, right = len(s) - 1)
print("after sort:",s1)

Running results:

before sort: [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
after sort: [1, 2, 2, 3, 4, 4, 5, 6, 6, 8, 9, 11, 15]

Readers interested in more Python related content can check out this site's topic: thePython Data Structures and Algorithms Tutorial》、《Summary of Python function usage tips》、《Summary of Python string manipulation techniques》、《Python introductory and advanced classic tutorialsand theSummary of Python file and directory manipulation techniques》

I hope that what I have said in this article will help you in Python programming.