49 lines
2.5 KiB
Markdown
49 lines
2.5 KiB
Markdown
# 3.5. Sort stack
|
|
|
|
> Sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but no arrays. Only push, pop, peek and isEmpty can be used
|
|
|
|
## First idea
|
|
|
|
Example: [5, 3, 1, 6, 4]
|
|
|
|
I'm going to need another `min` variable in the data structure. The algorithm could go like this: Iterate stack until `node.data == node.min`, stack2.push(node.data). Then update the max, until second stack is full of nodes in right order and initial stack is empty. Then put the numbers back in initial stack.
|
|
|
|
This takes O(n) space and O(n^2) time.
|
|
|
|
## Hints
|
|
|
|
* One way of sorting an array is to iterate through the array and insert each elem into a new array in sorted order, can you do this with a stack?
|
|
* Yes, algorithm before
|
|
* Imagine stack2 is sorted, can you insert elemens into it in a sorted order? If you need extra storage, what could you use for extra storage?
|
|
* I thought I couldn't modify functions. I can change `push` to iterate the stack and push the element in its correct position
|
|
* Keep stack2 sorted, with the biggest elements on top. Use stack1 for additional storage
|
|
|
|
So just iterate stack1 and add each element to stack2 in sorted mode, by having `push` modified. This takes O(nlogn)? time and O(n) space.
|
|
|
|
## Solution
|
|
|
|
s1: [5,10,7] and s2: [12, 8, 3, 1]. We want to insert 5 into s2, sorted. To do that, we `pop` 5 from s1, hold it in a temporary variable, then move 12 and 8 to s1, `pop`ping them from s2 and `push`ing them in s1, and then `push` 5 to s2. Then `pop` 12 and 8 from s1 and `push` them to s2.
|
|
|
|
```java
|
|
void sort(Stack<Integer> s) {
|
|
Stack<Integer> r = new Stack<Integer>();
|
|
while(!s.isEmpty()) {
|
|
/* Insert each element in s in sorted order into r. */
|
|
int tmp = s.pop();
|
|
while(!r.isEmpty() && r.peek() > tmp) {
|
|
s.push(r.pop());
|
|
}
|
|
r.push(tmp);
|
|
}
|
|
/* Copy the elements from r back into s. */
|
|
while (!r.isEmpty()) {
|
|
s.push(r.pop());
|
|
}
|
|
}
|
|
```
|
|
|
|
This is O(n^2) time and O(n) space. If we could use unlimited stacks, we could implement a modified quicksort or mergesort.
|
|
|
|
* Mergesort: create 2 extra stacks and divide stack1 into 2 parts, recursively sort each stack, and then merge them back together in sorted order into stack1. For each level of recursion, this means creating 2 additional stacks.
|
|
* Quicksort: create 2 extra stacks and divide the stack into the 2 stacks based on a pivot element. The 2 stacks would be recursively sorted, and then merged back together into stack1. This also involves creating 2 extra stacks per level of recursion.
|