Iterative in-place quicksort

Question

I have implemented an iterative in-place quicksort algorithm in Python, which by default selects the pivot as the last element:

def quicksort(array):
 """
 Sorts an array of integers using the quick-sort algorithm.
 :param array: the array to be sorted
 :type array: list<int>
 :return: the sorted array
 :rtype: list<int>
 """
 indexes_stack = list()
 idx = (0, len(array) - 1)
 indexes_stack.append(idx)
 for idx in indexes_stack:
 elem_idx = idx[0]
 pivot_idx = idx[1]
 while pivot_idx > elem_idx:
 pivot = array[pivot_idx]
 elem = array[elem_idx]
 if elem > pivot:
 array[pivot_idx] = elem
 array[elem_idx] = array[pivot_idx - 1]
 array[pivot_idx - 1] = pivot
 pivot_idx -= 1
 else:
 elem_idx += 1
 boundar_low = idx[0]
 boundar_high = idx[1]
 if pivot_idx > 1 and boundar_low < pivot_idx - 1:
 indexes_stack.append((boundar_low, pivot_idx - 1))
 if pivot_idx < len(array) -1 and pivot_idx + 1 < boundar_high:
 indexes_stack.append((pivot_idx + 1, boundar_high))
 return array
# Test the sorting function
counter = 0
while counter < 1000:
 test = [int(100 * random.random()) for i in xrange(15)]
 assert (quicksort(list(test)) == sorted(test)), test
 counter += 1

I've tested it with various inputs and it seems to be correct, but I wonder if it can become more efficient or clean.

• Vasilis: Thanks for catching the bug, I re-written function and the testing code to fix it.

Answer 1

The implied any aspect of the code posted is fair game for feedback and criticism justifies asking on CR even without an(y) explicit question. I'm taken against guessing what any piece of code is there for: Why another python quicksort? doesn't get answered in the code.
While the docstring looks charming, the parameter to quicksort() is over-specified: everything needed is "subscripting" to get&set items and comparable items. (Numeric items could be deemed handy for picking as a pivot the mean value of several.)
The code mentions neither iterative nor in-place:
quicksort() should be specified to return its (ordered) parameter.

clean, like beauty, lies in the eye of the beholder - to mine, both are close regarding code. I like python for its ability to express things with minimum ado.
(I don't quite like elem_idx&pivot_idx - sometimes use up&down.)

In demonstration code, it seems to have grown conventional to factor out partitioning the current sequence from quicksort().

True? The code doesn't use indexes_stack as a stack. As far as in-place means o(n) space (in addition to output is where input used to be), the implementation presented is not in-place.

More efficient? Sure -

• Space: handle the smallest partition first (with impeding out-of-memory, this is a correctness issue)

• Time:

  • choice of pivot is pivotal, using a value from either end of the partition disastrous for pre-ordered input.
  • Hoare partition scheme instead of Lomuto - three-way if lots of repeated values are to be expected
  • don't bother with less than two items, better yet:
    use a different algorithm for small partitions
  • don't push the top-priority partition to immediately pop it

In stead of further ranting (keeping elem, elem_idx & pivot_idx for recognition value):

# non-recursive quicksort - re-inventing the wheel finger exercise 
# docs.python.org tutorial:
# To add an item to the top of the stack, use append()
class stack(list):
 ''' push() to add an item to the top of the stack '''
 push = list.append
# non-recursive quicksort
def quicksort(items):
 """
 Sort a sequence using the quick-sort algorithm.
 :param items: the sequence to be sorted
 :return: items, sorted
 """
 nItems = len(items)
 if nItems < 2:
 return items
 todo = stack([(0, nItems - 1)])
 while todo:
 elem_idx, pivot_idx = low, high = todo.pop()
 elem = items[elem_idx]
 pivot = items[pivot_idx]
 while pivot_idx > elem_idx:
 if elem > pivot:
 items[pivot_idx] = elem
 pivot_idx -= 1
 items[elem_idx] = elem = items[pivot_idx]
 else:
 elem_idx += 1
 elem = items[elem_idx]
 items[pivot_idx] = pivot
 lsize = pivot_idx - low
 hsize = high - pivot_idx
 if lsize <= hsize:
 if 1 < lsize:
 todo.push((pivot_idx + 1, high))
 todo.push((low, pivot_idx - 1))
 else:
 todo.push((low, pivot_idx - 1))
 if 1 < hsize:
 todo.push((pivot_idx + 1, high))
 return items
if __name__ == '__main__':
# run the sorting function
 from random import randint
 for _ in range(99):
 test = [str(randint(0, 100)) for _ in range(randint(15, 99))]
 assert (quicksort(test[:]) == sorted(test)), test