Quicksort Python

Quicksort in python is similar to merge sort. It achieves sorting a dataset using division then sorting the divided data. It uses recursion to accomplish the sorting. It however performs better than merge sort.

# Quicksort Python

items = [45, 29, 343, 21, 42, 37, 90, 54, 22, 4, 7, 88]

def quick_sort(dataset, first, last):
    if first < last:
        #calculate split point
        pivotX = partition(dataset, first, last)

        #sort the two partitions
        quick_sort(dataset, first, pivotX - 1)
        quick_sort(dataset, pivotX + 1, last)

def partition(data_values, first, last):
    #choose first item as pivot value
    pivot_value = data_values[first]
    #find upper and lower index
    lower_index = first + 1
    upper_index = last

    #search for cross point
    done = False
    while not done:
        #advance the lower index
        while lower_index <= upper_index and data_values[lower_index] <= pivot_value:
            lower_index += 1

        #advance the upper index
        while data_values[upper_index] >= pivot_value and upper_index >= lower_index:
            upper_index -= 1

        #if the two cross, this is the split point
        if upper_index < lower_index:
            done = True
        else:
            temp = data_values[lower_index]
            data_values[lower_index] = data_values[upper_index]
            data_values[upper_index] = temp


    #Exchange pivot value when split point is found
    temp = data_values[first]
    data_values[first] = data_values[upper_index]
    data_values[upper_index] = temp

    #return split point index
    return upper_index

#test the quicksort python program
#unsorted items
print(items)
#perform quicksort
quick_sort(items, 0, len(items) - 1)
#quicksorted items
print(items)

-------------------------------------------------------------------------------------------------------
#Output
[45, 29, 343, 21, 42, 37, 90, 54, 22, 4, 7, 88]
[4, 7, 21, 22, 29, 37, 42, 45, 54, 88, 90, 343]