VietMX Staff asked 3 years ago
Problem
Note we can’t use another stack or queue.
The idea of the solution is to hold all values in system stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one in sorted order.
Complexity Analysis
Implementation
void sort(stack s) {
if (!IsEmpty(s)) {
int x = Pop(s);
sort(s);
insert(s, x);
}
}
void insert(stack s, int x) {
if (!IsEmpty(s)) {
int y = Top(s);
if (x < y) {
Pop(s);
insert(s, x);
Push(s, y);
} else {
Push(s, x);
}
} else {
Push(s, x);
}
}