CareerCup

public Stack<Integer> sort(Stack<Integer>stack){
		Stack<Integer>temp=new Stack<Integer>();
		if(stack.isEmpty())
			return stack;
		temp.push(stack.pop());
		while(!stack.isEmpty()){
			int val=stack.pop();
			while(!temp.isEmpty()){
				if(temp.peek()<val)
					stack.push(temp.pop());
				else
					break;
			}
			temp.push(val);
		}
		return temp;
	}

Just off the top of my head I would say you need an additional variable or two where you can store one value.
Assuming your data starts in one stack
Pop a value into your register
Then pop another value into another register
Push the smaller of the registers onto the other stack
Refill the empty register from the first stack
Repeat till one stack is empty
Swap the stacks and repeat n times
It is essentially a bubble sort so you should be able to eliminate half of the comparisons and you don’t need to empty out the stacks all the way as you progress.

def stacksort(stack):
    if not stack or stack == []: 
        return
    element = stack.pop()
    stacksort(stack)
    sorted_insert(element, stack)

def sorted_insert(element, sorted_stack):
    ge_stack = pop_greater(element, sorted_stack)
    sorted_stack.append(element)
    while ge_stack:
        sorted_stack.append(ge_stack.pop())

def pop_greater(element, stack):
    ge_stack = []
    while stack:
        top = stack.pop()
        if top >= element:
            ge_stack.append(top)
            continue
        stack.append(top)
        return ge_stack
    return ge_stack

Just off the top of my head I would say you need an additional variable or two where you can store one value.
Assuming your data starts in one stack
Pop a value into your register
Then pop another value into another register
Push the smaller of the registers onto the other stack
Refill the empty register from the first stack
Repeat till one stack is empty
Swap the stacks and repeat n times
It is essentially a bubble sort so you should be able to eliminate half of the comparisons and you don’t need to empty out the stacks all the way as you progress.

/**
	 * Algorithm
	 * Build up the original stack in sorted order slowly and process only unsorted items
	 * in each loop in the stack and you copy back all the elements from
	 * additional Stack to the originalStack in each loop.
	 * One extra method that was used to process was the peek()
	 * but this can easily replaced if this is not allowed
	 * @param stackToIterate
	 * TODO There is a room for improvement in this algorithm in terms of time complexity
	 */
	public static void sort(Stack<Integer> originalStack) {
		//Only allowed one more additional stack
		Stack<Integer> additionalStack = new Stack<Integer>();
		boolean notSorted = true;
		int sortedElements = -1;
		while(notSorted) {
			int currentInt = originalStack.pop();
			sortedElements++;
			notSorted = false;

			while(!originalStack.isEmpty() && originalStack.size() -sortedElements >0 ) {
				int nextInt = originalStack.pop();
	
				if(nextInt > currentInt) {
					if(!additionalStack.isEmpty() && additionalStack.peek() > currentInt) notSorted = true;
					additionalStack.push(currentInt);
					currentInt = nextInt;
				}
				else {
					if(!additionalStack.isEmpty() && additionalStack.peek() > nextInt) notSorted = true;
					additionalStack.push(nextInt);
				}
			}
			originalStack.push(currentInt);
			while(!additionalStack.isEmpty()) {
				originalStack.push(additionalStack.pop());
			}
		}

	}
	public static void main(String [] args) {
		Stack<Integer> inputStack = new Stack<>();
		inputStack.push(10);
		inputStack.push(11);
		inputStack.push(23);
		inputStack.push(90);
		inputStack.push(1);
		inputStack.push(2);
		inputStack.push(3);
		inputStack.push(4);
		sort(inputStack);
		System.out.println(inputStack);
	}

1. Copy stack to a auxiliary stack.
2. Pop top most from the stack1 and push it in stack2.
3. Pop next element from stack1 , if (element> Top element) in stack 2 , replace , else continue popping from first until it is empty.
4. Copy back original stack and continue until memory of second stack is full.
5. Pop the elements from stack2.

Example :

7 - - - 1
2 - - - 2
5 -> - -> - -> 4 ................. 4
4 - 5 5 5
1 7 7 7 7

1,2,4,5,7 which is the solution.

Solution:

public class StackSorter {
	public static <T extends Comparable<T>> void sort(Stack<T> items) {
		Stack<T> other = new Stack<>();
		
		while(!items.isEmpty()) {
			T current = items.pop();
			while(!other.isEmpty() && other.peek().compareTo(current) < 0) {
				items.push(other.pop());
			}
			other.push(current);
		}
		
		while(!other.isEmpty()) {
			items.push(other.pop());
		}
	}
}

And to test:

public class StackSorterTester {
	@Test
	public void test() {
		Random rand = new Random(System.currentTimeMillis());
		Stack<Integer> stack = new Stack<>();

		for (int i = 0; i < 10000; i++) {
			int value = rand.nextInt(10000);
			stack.push(value);
		}

		StackSorter.sort(stack);

		for (int i = 1; i < stack.size(); i++) {
			int lower = stack.get(i - 1);
			int upper = stack.get(i);
			Assert.assertTrue(String.format(
					"Value %d at index %d is greater than %d at index %d",
					lower, i - 1, upper, i), lower <= upper);
		}
	}
}

selectSortStacks [] = []
selectSortStacks (h:l) = minE : selectSortStacks restOfList
    where 
      (minE, restOfList) = partition h l
      partition m [] = (m, [])
      partition curMin (c:l) = (newMin, larger : rest)
          where 
            (newMin, rest) = partition smaller l
            smaller = min curMin c
            larger = max curMin c

stack_sort(st , 0);

stack_sort(Stack st, num)
{
 temp = pop (st_;
 if (isstackempty(st)) 
       push (st, temp ); 
 else { 
           stack_sort(st,temp);
           while (stacktop(st < temp) 
           { 
                  temp1 = pop(st);
                  push(st1, temp1);  //copy to second stack 
           }
           push(st, temp ); 
         //  copy the second stack after inserting the temp to proper position   
           while (isempty(st1) ) 
           {
                    push(st, pop(st1));
           }
    }     
}

#include <stdio.h>
#define maxSize 10
//defining stack
struct stack{
int arr[maxSize];
int top;
};
//declaring operations on stack
void initStack(struct stack *s);
void push(struct stack *s,int item);
int pop(struct stack *s);
int peek(struct stack *s);
void display(struct stack *s);
int isFull(struct stack *s);
int isEmpty(struct stack *s);
void sortStack(struct stack *st,int data);
int main(int argc, char **argv)
{
int num;
struct stack stack1,stack2;
initStack(&stack1);
initStack(&stack2);
push(&stack1,10);
push(&stack1,1);
push(&stack1,6);
push(&stack1,3);
push(&stack1,9);
display(&stack1);
printf("---------\n");
while(!isEmpty(&stack1)){
sortStack(&stack2,pop(&stack1));
}
display(&stack2);


return 0;
}
void initStack(struct stack *s){
s->top=-1;
}
int isFull(struct stack *s){
if(s->top==(maxSize-1)){
return 1;
}
return 0;
}
int isEmpty(struct stack *s){
if(s->top==-1){
return 1;
}
return 0;
}
void push(struct stack *s,int item){
if(isFull(s)){
printf("Stack Full");
}else{
s->top++;
s->arr[s->top]=item;
}
}
void display(struct stack *s){
if(isEmpty(s)){

}else{
int count=s->top;
while(count>=0){
printf("%d ",s->arr[count]);
printf("\n");
count--;
}
}
}
int pop(struct stack *s){
if(isEmpty(s)){
printf("Stack Empty");
}else{
int item=s->arr[s->top];
s->top--;
return item;
}

}
int peek(struct stack *s){
if(isEmpty(s)){
printf("Stack Empty");
}else{
return s->arr[s->top];
}
}
void sortStack(struct stack *st,int data){
if(isEmpty(st)){
push(st,data);
}else{
int item;
if((item=peek(st))>data){
item=pop(st);
sortStack(st,data);
push(st,item);
}else{
push(st,data);
}
}
}

A recursive solution in Scala

{{
def sort(stack: Stack[Int], sortedStack: Stack[Int]): Stack[Int] = {
if (stack.isEmpty) sortedStack
else {
sortedStack.headOption match {
case Some(head) => if (stack.head > head) sort(stack.pop.push(head).push(stack.head), sortedStack.pop)
else sort(stack.pop, sortedStack.push(stack.head))
case None => sort(stack.pop, sortedStack.push(stack.head))
}
}
}
}}

//showing Runtime error Plz help?????

#include<iostream>
#include<stdio.h>
using namespace std;

struct StackNode
{
int data;
struct StackNode *next;
};

int isEmpty(struct StackNode *root)
{
return (root== NULL);
}

struct StackNode * newNode(int data)
{
struct StackNode *newNode = (struct StackNode *)malloc(sizeof(struct StackNode));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

void push(struct StackNode **root,int data)
{
struct StackNode *stack = newNode(data);
stack->next = *root;
*root = stack;
printf("%d pushed to stack\n",data);
}

int pop(struct StackNode **root)
{
if(isEmpty(*root))
return INT_MIN;
struct StackNode *tmp =*root;
int vl=tmp->data;
*root = (*root)->next; //OR *root = tmp-next;
free(tmp);
return vl;
}

int peek(struct StackNode *root)
{
if(isEmpty(root))
return INT_MIN;
return (root->data);
}

struct StackNode* SortTheStack(struct StackNode *S)
{
struct StackNode *r;
int tmp;
while(!isEmpty(S))
{
tmp = pop(&S);
while(!isEmpty(r) && peek(r)>tmp)
{
push(&S,pop(&r));
}
push(&r,tmp);
}
return r;
}

int main()
{
struct StackNode *S = NULL;
struct StackNode *r = NULL;
push(&S,40);
push(&S,20);
push(&S,10);
push(&S,30);
r = SortTheStack(S);
printf("sorted stack is: ");
while(!isEmpty(r))
{
printf("%d ",pop(&r));
}
return 0;
}