I found this question on the web.
Given a stack S, write a C program to sort the stack (in the ascending order). We are not allowed to make any assumptions about how the stack is implemented. The only functions to be used are:
Push
Pop
Top
IsEmpty
IsFull
I think we can build heap and sort it. What is optimal solution to this?
Assuming that the only data structure allowed here is the Stack, then you could use 2 Stacks.
Iterate until the original stack is empty and in each iteration, pop an element from the original stack, while the top element in the second stack is bigger than the removed element, pop the second stack and push it to the original stack. Now you can push the element you originally popped off the original stack to the second stack.
The time complexity of this approach is O(N^2).
C code to implement this algorithm would be (excuse my rusty C skills):
void SortStack(struct Stack * orig_stack)
{
struct Stack helper_stack;
while (!IsEmpty(orig_stack))
{
int element = Pop(orig_stack);
while (!IsEmpty(&helper_stack) && Top(&helper_stack) < element)
{
Push(orig_stack, Pop(&helper_stack));
}
Push(&helper_stack, element);
}
while (!IsEmpty(&helper_stack))
{
Push(orig_stack, Pop(&helper_stack));
}
}
Given those stack operations, you could write a recursive insertion sort.
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);
}
}
It can be done recursively using the same stack. O(n^2) I have coded it in C++ but the conversion to C is trivial. I just like templates and you did tag your question as C++
template<typename T>
void Insert(const T& element, Stack<T>& stack)
{
if(element > stack.Top())
{
T top = stack.Pop();
Insert(element, stack);
stack.Push(top);
}
else
{
stack.Push(element);
}
}
template<typename T>
void StackSort(Stack<T>& stack)
{
if(!stack.IsEmpty())
{
T top = stack.Pop();
StackSort(stack);
Insert(top, stack);
}
}
Pancake sort is another interesting way to do this: http://en.wikipedia.org/wiki/Pancake_sorting#cite_note-4.
This should be the fastest way to implement a 3 stack sort. Time complexity is O(n log(n)). The goal is to end up with an ascending sequence as items are popped from a sorted stack. The origin for this method was using polyphase merge sort on old mainframe tape drives that could read backwards (to avoid rewind time), similar to stack due to writing forwards and reading backwards during the sort.
Wiki article for polyphase merge sort (using arrays):
http://en.wikipedia.org/wiki/Polyphase_merge_sort
Example C++ code for 3 stack polyphase sort, using pointers, a pointer as a stack pointer for each stack, and a pointer to the end of each run and the end of each stack. The run size pointer is used to keep track of when the run size increments or decrements mid stack. A descending sequence flag is used to keep track if sequences are descending or ascending as data is transferred between stacks. It is initialized at the start, and then alternates after every pair of runs is merged.
typedef unsigned int uint32_t;
static size_t fibtbl[48] =
{ 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733,1134903170,1836311903,2971215073};
// binary search: return index of largest fib() <= n
size_t flfib(size_t n)
{
size_t lo = 0;
size_t hi = sizeof(fibtbl)/sizeof(fibtbl[0]);
while((hi - lo) > 1){
size_t i = (lo + hi)/2;
if(n < fibtbl[i]){
hi = i;
continue;
}
if(n > fibtbl[i]){
lo = i;
continue;
}
return i;
}
return lo;
}
// poly phase merge sort array using 3 arrays as stacks, a is source
uint32_t * ppmrg3s(uint32_t a[], uint32_t b[], uint32_t c[], size_t n)
{
if(n < 2)
return a;
uint32_t *asp = a; // a stack ptr
uint32_t *aer; // a end run
uint32_t *aes = a + n; // a end
uint32_t *bsp = b + n; // b stack ptr
uint32_t *ber; // b end run
uint32_t *bes = b + n; // b end
uint32_t *csp = c + n; // c stack ptr
uint32_t *ces = c + n; // c end
uint32_t *rsp = 0; // run size change stack ptr
size_t ars = 1; // run sizes
size_t brs = 1;
size_t scv = 0-1; // size change increment / decrement
bool dsf; // == 1 if descending sequence
{ // block for local variable scope
size_t f = flfib(n); // fibtbl[f+1] > n >= fibtbl[f]
dsf = ((f%3) == 0); // init compare flag
if(fibtbl[f] == n){ // if exact fibonacci size, move to b
for(size_t i = 0; i < fibtbl[f-1]; i++)
*(--bsp) = *(asp++);
} else { // else move to b, c
// update compare flag
dsf ^= (n - fibtbl[f]) & 1;
// move excess elements to b
aer = a + n - fibtbl[f];
while (asp < aer)
*(--bsp) = *(asp++);
// move dummy count elements to c
aer = a + fibtbl[f - 1];
while (asp < aer)
*(--csp) = *(asp++);
rsp = csp; // set run size change ptr
}
} // end local variable block
while(1){ // setup to merge pair of runs
if(asp == rsp){ // check for size count change
ars += scv; // (due to dummy run size == 0)
scv = 0-scv;
rsp = csp;
}
if(bsp == rsp){
brs += scv;
scv = 0-scv;
rsp = csp;
}
aer = asp + ars; // init end run ptrs
ber = bsp + brs;
while(1){ // merging pair of runs
if(dsf ^ (*asp <= *bsp)){ // if a <= b
*(--csp) = *(asp++); // move a to c
if(asp != aer) // if not end a run
continue; // continue back to compare
do // else move rest of b run to c
*(--csp) = *(bsp++);
while (bsp < ber);
break; // and break
} else { // else a > b
*(--csp) = *(bsp++); // move b to c
if(bsp != ber) // if not end b run
continue; // continue back to compare
do // else move rest of a run to c
*(--csp) = *(asp++);
while (asp < aer);
break; // and break
}
} // end merging pair of runs
dsf ^= 1; // toggle compare flag
if(bsp == bes){ // if b empty
if(asp == aes) // if a empty, done
break;
std::swap(bsp, csp); // swap b, c
std::swap(bes, ces);
brs += ars; // update run size
} else { // else b not empty
if(asp != aes) // if a not empty
continue; // continue back to setup next merge
std::swap(asp, csp); // swap a, c
std::swap(aes, ces);
ars += brs; // update run size
}
}
return csp; // return ptr to sorted array
}
Example java code for sorting using a custom stack class (xstack) that includes a swap function.
static final int[] FIBTBL =
{ 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733,1134903170,1836311903};
// return index of largest fib() <= n
static int flfib(int n)
{
int lo = 0;
int hi = 47;
while((hi - lo) > 1){
int i = (lo + hi)/2;
if(n < FIBTBL[i]){
hi = i;
continue;
}
if(n > FIBTBL[i]){
lo = i;
continue;
}
return i;
}
return lo;
}
// poly phase merge sort using 3 stacks
static void ppmrg3s(xstack a, xstack b, xstack c)
{
if(a.size() < 2)
return;
int ars = 1; // init run sizes
int brs = 1;
int asc = 0; // no size change
int bsc = 0;
int csc = 0;
int scv = 0-1; // size change value
boolean dsf; // == 1 if descending sequence
{ // block for local variable scope
int f = flfib(a.size()); // FIBTBL[f+1] > size >= FIBTBL[f]
dsf = ((f%3) == 0); // init compare flag
if(FIBTBL[f] == a.size()){ // if exact fibonacci size,
for (int i = 0; i < FIBTBL[f - 1]; i++) { // move to b
b.push(a.pop());
}
} else { // else move to b, c
// update compare flag
dsf ^= 1 == ((a.size() - FIBTBL[f]) & 1);
// i = excess run count
int i = a.size() - FIBTBL[f];
// j = dummy run count
int j = FIBTBL[f + 1] - a.size();
// move excess elements to b
do{
b.push(a.pop());
}while(0 != --i);
// move dummy count elements to c
do{
c.push(a.pop());
}while(0 != --j);
csc = c.size();
}
} // end block
while(true){ // setup to merge pair of runs
if(asc == a.size()){ // check for size count change
ars += scv; // (due to dummy run size == 0)
scv = 0-scv;
asc = 0;
csc = c.size();
}
if(bsc == b.size()){
brs += scv;
scv = 0-scv;
bsc = 0;
csc = c.size();
}
int arc = ars; // init run counters
int brc = brs;
while(true){ // merging pair of runs
if(dsf ^ (a.peek() <= b.peek())){
c.push(a.pop()); // move a to c
if(--arc != 0) // if not end a
continue; // continue back to compare
do{ // else move rest of b run to c
c.push(b.pop());
}while(0 != --brc);
break; // and break
} else {
c.push(b.pop()); // move b to c
if(0 != --brc) // if not end b
continue; // continue back to compare
do{ // else move rest of a run to c
c.push(a.pop());
}while(0 != --arc);
break; // and break
}
} // end merging pair of runs
dsf ^= true; // toggle compare flag
if(b.empty()){ // if end b
if(a.empty()) // if end a, done
break;
b.swap(c); // swap b, c
brs += ars;
if (0 == asc)
bsc = csc;
} else { // else not end b
if(!a.empty()) // if not end a
continue; // continue back to setup next merge
a.swap(c); // swap a, c
ars += brs;
if (0 == bsc)
asc = csc;
}
}
a.swap(c); // return sorted stack in a
}
The java custom stack class:
class xstack{
int []ar; // array
int sz; // size
int sp; // stack pointer
public xstack(int sz){ // constructor with size
this.ar = new int[sz];
this.sz = sz;
this.sp = sz;
}
public void push(int d){
this.ar[--sp] = d;
}
public int pop(){
return this.ar[sp++];
}
public int peek(){
return this.ar[sp];
}
public boolean empty(){
return sp == sz;
}
public int size(){
return sz-sp;
}
public void swap(xstack othr){
int []tempar = othr.ar;
int tempsz = othr.sz;
int tempsp = othr.sp;
othr.ar = this.ar;
othr.sz = this.sz;
othr.sp = this.sp;
this.ar = tempar;
this.sz = tempsz;
this.sp = tempsp;
}
}
Modified code from T33C's answer
(given before Svante corrected the language tag from c++ to c):
stack.top() can only be checked if !stack.empty()
void insert(int element, stack<int> &stack) {
if (!stack.empty() && element > stack.top()) {
int top = stack.top();
stack.pop();
insert(element, stack);
stack.push(top);
}
else {
stack.push(element);
}
}
void sortStack(stack<int> & stack) {
if (!stack.empty()) {
int top = stack.top();
stack.pop();
sortStack(stack);
insert(top, stack);
}
}
Note that Michael J. Barber's answer (see above) is not correct, which forgets to push element back to the stack when it is empty. Correct version is as follows:
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); // !!! must step, otherwise, the stack will eventually be empty after sorting !!!
}
}
Here is the solution in Javascript based on the answer given by @OrenD
var org = [4,67,2,9,5,11,3];
var helper = [];
while(org.length > 0){
var temp = org.pop();
while((helper.length > 0) && (helper[helper.length-1] < temp)){
org.push(helper.pop());
}
helper.push(temp);
}
while(helper.length > 0){
org.push(helper.pop());
}
/* the basic idea is we go on
* popping one element (o) from the original stack (s) and we
* compare it with the new stack (temp)
* if o (the popped element from original stack)
* is < the peek element from new stack temp
* then we push the new stack element to original stack
* and recursively keep calling till temp is not empty
* and then push the element at the right place.
* else we push the element to the new stack temp
* (o >= new temp stack.
*
* Entire logic is recursive.
*/
public void sortstk( Stack s )
{
Stack<Integer> temp = new Stack<Integer>();
while( !s.isEmpty() )
{
int s1 = (int) s.pop();
while( !temp.isEmpty() && (temp.peek() > s1) )
{
s.push( temp.pop() );
}
temp.push( s1 );
}
// Print the entire sorted stack from temp stack
for( int i = 0; i < temp.size(); i++ )
{
System.out.println( temp.elementAt( i ) );
}
}
With three stacks S (source stack, the stack with unsorted elements), A, B you can start playing a game similar to merge sort.
I think it is clear that if you have ordered elements on A and B (in the same direction, both ascending or both descending), that you can use S to merge sort A and B and then move the result to, for example, B.
The fact that you have some elements on A, B or S does not stop you from being able to use A, B or S for merging(, as long as you have the marker of the current size of A, B and S so you would not overshoot). If your procedure brings ordered elements on S, it is no brain to use A and B to remove the sorted portion to A or B in any direction you like: you can place it in reverse order to A or B directly, or, for example, place all elements to A and than reverse once again to B.
Assume that you have 4 sorted elements on A, 16 on B and some unsorted elements on S.
A.push(S.pop) and now create a 2-element sorted merge. Again B.push(S.pop) and create another one 2-element sorted merge. If the merges are not separated and/or not in the same direction, you can manipulate elements any way you like until you reach 4-element sorted merge on B (or even S). Now merge the initial 4-element sorted merge from A and that part on B, until you reach 8-element sorted merge.
You repeat everything until you create another 8-element sorted merge. You place it in right order on B (or S) and merge in order to get 16-element sorted merge. Now you place it on A (or S) and merge with 16-element merge that we've had on B all along.
The optimized implementation is tricky since you need to reduce moving (reverting) sorted merge from one stack to another. However if you fix and decide what for you are going to use A, B and S and force for example: A to contain the smaller and B larger merged portion in descending order then the algorithm is simpler.
The fact that you need to move some top elements from one stack to another is adding a constant factor to complexity, but it is never more than 2. Other than that the complexity is n*log(n) (you reach a 2n-element sorted merge by merging 2 n-element sorted merges, and a merging requires no more than 2n steps.)
Implementation in C# (other similar languages are obvious)
void Stacking(Stack<int> sourceStack, Stack<int> mainStack, Stack<int> childStack, int n)
{
if (n == 0) return;
if (n == 1)
{
mainStack.Push(sourceStack.Pop());
return;
}
int mainSize = n/2;
int childSize = n - n/2;
Stacking(sourceStack, mainStack, childStack, mainSize);
Stacking(sourceStack, childStack, mainStack, childSize);
while (true)
{
while (mainSize > 0 && mainStack.Peek() >= childStack.Peek())
{
sourceStack.Push(mainStack.Pop());
mainSize--;
}
if (mainSize == 0) break;
while (childSize > 0 && childStack.Peek() >= mainStack.Peek())
{
sourceStack.Push(childStack.Pop());
childSize--;
}
if (childSize == 0) break;
}
while (mainSize > 0)
{
sourceStack.Push(mainStack.Pop());
mainSize--;
}
while (childSize > 0)
{
sourceStack.Push(childStack.Pop());
childSize--;
}
for (int i = 0; i < n; i++)
mainStack.Push(sourceStack.Pop());
}
void SortStack(Stack<int> sourceStack)
{
int n = sourceStack.Count();
// possible optimization: if (n < 2) return;
Stack<int> mainStack = new Stack<int>();
Stack<int> childStack = new Stack<int>();
Stacking(sourceStack, mainStack, childStack, n);
for (int i = 0; i < n; i++)
sourceStack.Push(mainStack.Pop());
}
The above procedure could be simplified if you are allowed to use at most log(n) stacks. This number of stacks does not mean that you will ever use an additional space larger than order of n. You simply mark stacks that will be used for merging 1, 2, 4... elements. In this case you do not care about the order since merging parts of 2^n will always be sorted in the same direction. However, this solution is only circumventing the fact that you are limited to use push and pop operation; other than that it is equivalent to merge sort in all aspects. In essence, if the number of stacks is not limited then you can easily emulate quick sort as well.
I think that the bubble sort could work on the stack with recursion.
void sortStack(stack<int>& st){
bool flag = true;
int n = st.size();
for(int i = 1; i <= n - 1 && flag; i++){
flag = false;
bubbleSortStack(st, flag, i);
}
}
void bubbleSortStack(stack<int>& st, bool& flag, int endSize){
if(st.size() == endSize)
return;
int val = st.top();
st.pop();
if(val > st.top()){
flag = true;
int tmp = st.top();
st.push(val);
val = tmp;
}
bubbleSortStack(st, flag);
st.push(val);
}
If you don't have any extra information about the stack contents, then you pretty much are stuck just taking all the data out, sorting it, and putting it back in. Heapsort would be great here, as would quicksort or introsort.
If there is no limitation on using other data structures, I would say the minimum heap. whenever popping a element from stack, put into the heap. When popping is done, taking element from the top of heap (minimum of the rest) and pushing it into the stack. Repeating such process until heap is empty.
For creating a heap, the average time is O(nlogn); for deleting elements from heap and putting elements back in ascending order, the average time is O(nlogn) too.
How does it look?
class Program
{
static void Main(string[] args)
{
Stack<int> stack = new Stack<int>();
stack.Push(8);
stack.Push(5);
stack.Push(3);
stack.Push(4);
stack.Push(7);
stack.Push(9);
stack.Push(5);
stack.Push(6);
Stack<int> tempStack = new Stack<int>();
while (stack.Count > 0)
{
int temp = stack.Pop();
while(tempStack.Count>0 && tempStack.Peek() > temp)
{
stack.Push(tempStack.Pop());
}
tempStack.Push(temp);
}
while (tempStack.Count > 0)
{
Console.Write(tempStack.Pop() + " ");
}
Console.ReadLine();
}
}
Since nothing is said about how many extra stacks can be used, so I am assuming any number of stacks can be used to solve the sorting problem as efficiently as possible.
If you forget about stack constraint for now and assume this was a normal sorting problem. Then how can you solve it? (Hint: Merge sort)
Perform normal merge sort on the stack using auxiliary stacks. Time complexity - N*log(n).
