class Solution(object):
def rainbowSort(self, array):
"""
input: int[] array
return: int[]
"""
# write your solution here
if len(array) == 0 or len(array) == 1:
return array
pivot_index = self.partition(array, 0, len(array)-1)
array[0:pivot_index] = self.rainbowSort(array[0:pivot_index])
array[pivot_index+1:] = self.rainbowSort(array[pivot_index+1:])
return array
def partition(self, array, p, r):
x = array[r] # pivot
i = p-1
for j in range(p, r):
if array[j] <= x:
array[i+1], array[j] = array[j], array[i+1] # put the small element on the i region
i += 1
array[i+1], array[r] = array[r], array[i+1]
return i+1 # index of pivot
Same as quicksort.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.