class Quicksort: def __init__(self): self._data = None def sort(self, data): """ Quicksort a list of data. """ self._data = data self._sort(0, len(data) - 1) self._verify_sorted() def _sort(self, left, right): """ Recursively sort a sublist. @param left the leftmost index of the sublist. @param right the rightmost index of the sublist. """ size = right - left + 1 # Size > 2: Partition and recursively # sort the sublists. if size > 2: pivot_index = self._partition(left, right) # Recursively sort the left sublist. if left != pivot_index: self._sort(left, pivot_index - 1) # Recursively sort the right sublist. if right != pivot_index: self._sort(pivot_index + 1, right) # Size == 2: Swap if necessary. elif (size == 2) and (self._data[left] > self._data[right]): self._data[left], self._data[right] = \ self._data[right], self._data[left] def _partition(self, left, right): """ Partition the part of list data bounded by indexes left and right. @param left the leftmost index of the sublist. @param right the rightmost index of the sublist. @return the final index of the pivot value. """ # Pick the pivot value. middle = (left + right)//2 pivot_value = self._data[middle] # Swap the pivot value with the rightmost value. self._data[middle], self._data[right] = \ self._data[right], self._data[middle] i = left - 1 j = right # As long as i and j don't cross ... while i < j: # Move i to the right. i += 1 while (i < right) and (self._data[i] <= pivot_value): i += 1 # Move j to the left. j -= 1 while (j > left) and (self._data[j] > pivot_value): j -= 1 # Swap after i and j have stopped moving. if (i < j) and (self._data[i] != self._data[j]): self._data[i], self._data[j] = \ self._data[j], self._data[i] # Swap the pivot value from the right end # to its correct position. if self._data[i] != self._data[right]: self._data[i], self._data[right] = \ self._data[right], self._data[i] return i def _verify_sorted(self): """ Verify that the data list has been successfully sorted. """ for k in range(1, len(self._data)): value = self._data[k] prev = self._data[k - 1] if value < prev: raise Exception('Sort error: ' f'{value} < {prev} at {k}')