Chapter 三 Stacks and Queues - 3.6

Chapter 3 Stacks and Queues - 3.6
Problem 3.6: Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

The most intuitive solution is popping all elements into an array, sorting the array and pushing all elements back to the stack.
from stack import *def sort_stack(s): s2 = stack() while not s.isEmpty(): tmp = s.pop() while (not s2.isEmpty()) and (s2.peek() <= tmp): s.push(s2.pop()) s2.push(tmp) while not s2.isEmpty(): s.push(s2.pop())
Although the solution above cannot beat mine on running time, it is an innovative method.

Here I want to summarize the mistakes that I prone to make when I am implementing quicksort:
1) The ending condition of recursion is "if start >= end", not "if start == end"
2) The initial position of pivot is array[start], not array[0]
3) The initial position of working pointer is (start + 1), not start
4) In quick_sort() (or partition()), never use array[0] and array[len(array)]. You should use array[start] and array[end].