Quicksort | Largest order

Implement quicksort

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.

Recommended Posts

Quicksort | Largest order
QuickSort