From "Cracking the Coding Interview":
Write a program to sort a stack in ascending order (with the largest items at the top). You can use up to one additional stack to hold items, but you can not copy items to another data structure (such as an array). The battery supports
push,pop,is_empty, andpeek
So, the classic solution I found online for this (and the one in the book) looks like this:
Algo # 1 (classic)
def sort_stack(primary):
secondary = ()
while primary:
tmp = primary.pop()
while (secondary and secondary(-1) > tmp):
primary.append(secondary.pop())
secondary.append(tmp)
return secondary
In summary, we will return our secondary / auxiliary battery after sorting via time O (n ^ 2).
However, this is not what my original approach was and I think this approach has some interesting qualities:
Algo # 2 (mine)
def sort_stack(primary):
did_sort = False
secondary = ()
while not did_sort:
# move from primary to secondary, pushing larger elements first when possible
desc_swap(primary, secondary)
# move from secondary back to primary, pushing smaller elements first when possible. Set did_sort = True if we're done and can exit.
did_sort = asc_swap(secondary, primary)
return primary
def asc_swap(full, empty):
temp = None
did_sort = True
yet_max = None
while full:
if not temp:
temp = full.pop()
if full:
if full(-1) < temp:
insert = full.pop()
if insert < yet_max:
did_sort = False
yet_max = insert
empty.append(insert)
else:
empty.append(temp)
temp = None
if temp:
empty.append(temp)
return did_sort
def desc_swap(full, empty):
temp = None
while full:
if not temp:
temp = full.pop()
if full:
if full(-1) > temp:
empty.append(full.pop())
else:
empty.append(temp)
temp = None
if temp:
empty.append(temp)
Now, obviously, it is not as clean or elegant, but it could be with some help functions that dynamically choose our comparator and choose the element to push, etc.
Basically, what he does is this:
# Start with stack in wrong order (worst case)
primary: 4 3 2 1
secondary:
# Swap to secondary, pushing larger elements first (1 is held in temp until the end because it is smaller than the following elements)
primary:
secondary: 2 3 4 1
# Swap back to primary, pushing smaller elements first
primary: 1 3 2 4
secondary:
# back to secondary
primary:
secondary: 4 3 2 1
# Back to primary, finished
primary: 1 2 3 4
secondary:
This strategy has a compromise between the best and the worst case.
Algo # 1 actually performs worst when the stack is already sorted and better when sorted in the wrong order and algo # 2 does the opposite.
Questions
- What are your thoughts? I think it's just an interesting way to sort out what I've never seen before.
- Is there a name for this kind of sorting? I could not find similar algos but I am sure they are there and would like to be able to describe / recognize it better. Thank you!
