First, let "26" be the standard number (pivot). Items larger than "26" to Left Set something smaller than "26" to Right. Because it can be divided into left and right The same processing is performed for each separated list. Left[32, 65, 76, 43, 87, 59] Right[13, 22, 14]
Next, Left is sorted, but the pivot is the first "32". By repeating this, the result below will be obtained.
QuickSort.py
data = [26,13,32,65,76,22,43,87,14,59]
def QuickSort(data):
if len(data) <= 1: #If there is less than one data, the value is returned as it is
return data
#Use the first value in the list as the reference data (pivot)
pivot = data[0]
left, right, same = [], [], 0 #Initialization (list, list, 0)
for ii in data:
if ii > pivot:
left.append(ii) #If larger than the pivot, set to the left
elif ii < pivot:
right.append(ii) #If smaller than the pivot, set to the right
else:
same += 1 #Do not move the same value, count only the number
left = QuickSort(left) #Sort on the left
right = QuickSort(right) #Sort on the right
#Return sorted data and pivot together
return left + [pivot] * same + right
print(QuickSort(data))
#result
# [87, 76, 65, 59, 43, 32, 26, 22, 14, 13]
There seems to be a way of saying "divide and conquer", but the process is recursively repeated by repeating the division into smaller units. Depending on how you choose the pivot, it seems that there are various things that can be processed faster.