Python Data Structures and Algorithms

Partition step

The partition step is exactly like we had in the quick sort algorithm. There are a couple of things worthy of note:

    def partition(unsorted_array, first_index, last_index):         if first_index == last_index:             return first_index         pivot = unsorted_array[first_index]         pivot_index = first_index         index_of_last_element = last_index         less_than_pivot_index = index_of_last_element         greater_than_pivot_index = first_index + 1         while True:             while unsorted_array[greater_than_pivot_index] < pivot and                    greater_than_pivot_index < last_index:                   greater_than_pivot_index += 1             while unsorted_array[less_than_pivot_index] > pivot and                   less_than_pivot_index >= first_index:                   less_than_pivot_index -= 1  if greater_than_pivot_index < less_than_pivot_index: ...