Quick Sort Time Complexity: Best O(nLogn), Worst O(n^2) class QuickSort: def quick_sort(self, arr): if len(arr) > 0: self.sort(arr, 0, len(arr) - 1) else: print('ERROR: input array is empty!') print(arr) def sort(self, arr, left, right): if left < right: partition_key = self.partition(arr, left, right) self.sort(arr, partition_key + 1, right) self.sort(arr, left, partition_key - 1) # Result: # (smaller values), arr[wall], (bigger values) # Return `wall` as the new partition_key. def partition(self, arr, left, right): pivot = arr[right] wall = left for i in range(left, right): if arr[i] < pivot: self.
Read More