From "Deciphering the coding interview":
Write a program to sort a stack in ascending order (with the largest items at the top). You can use at most one additional stack to contain items, but you cannot copy the items into any other data structure (such as an array). The battery supports
So, the classic solution I found online for this (and the one in the book) is something like this:
Something # 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
The essence of this is that we will return our secondary / auxiliary battery after ordering by time O (n ^ 2).
However, this is not my initial approach, and I think my approach has some interesting qualities:
Something # 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 so clean or elegant, but it could be with some auxiliary functions that dynamically choose our comparator and choose which element to push, etc.
Basically what he is doing 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 best / worst case compromise solution.
Something # 1 really does worst when the battery is already sorted and better when the battery is ordered in the wrong order, and something # 2 does the opposite.
- What are your thoughts? I think it's an interesting way to order that I haven't seen before.
- Is there a name for this type of classification? I couldn't find something similar, but I'm sure they are out there and I would love to describe / recognize it better. Thank you!