One of my close friend asked me an interesting puzzle (Not sure who asked him :))
Puzzle goes something like this:
“2 stacks are given, one with full of numbers (in random order) and other is empty. Using just one integer variable, order the numbers (ascending or descending) with space and time constraints”.
Please try without seeing my solution. You might solve it in a better way.
It started with bubble sort however we will not be able to solve completely using bubble sort as the data structure is stack. The algorithm went several changes and final result was something different to bubble sort :). This will be of O(n2) space is O(1):
import java.util.Random;
import java.util.Stack;
public class Main {
static Random rg = new Random();
static int temp, size;
public static void main(String[] args) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
for(int i=0; i < 16; i++)
s1.push(rg.nextInt(100));
System.out.println("Unsorted : " + s1.toString());
size = s1.size()-1;
while(size > 0) {
temp = s1.pop();
for(int j=0; j < size; j++) {
if(temp >= s1.peek()) {
s2.push(temp);
temp=s1.pop();
} else {
s2.push(s1.pop());
}
}
s1.push(temp);
for(int k = size; k > 0 ; k--)
s1.push(s2.pop());
size= size-1;
}
System.out.println("Sorted :"+ s1);
}
}
S1 is in decending order moving to S2 will be ascending.
The above algorithm is finding the higest element in stack and moving the same to bottom of S1 and repeating the process upto complete stack is sorted.
Puzzle goes something like this:
“2 stacks are given, one with full of numbers (in random order) and other is empty. Using just one integer variable, order the numbers (ascending or descending) with space and time constraints”.
Please try without seeing my solution. You might solve it in a better way.
It started with bubble sort however we will not be able to solve completely using bubble sort as the data structure is stack. The algorithm went several changes and final result was something different to bubble sort :). This will be of O(n2) space is O(1):
import java.util.Random;
import java.util.Stack;
public class Main {
static Random rg = new Random();
static int temp, size;
public static void main(String[] args) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
for(int i=0; i < 16; i++)
s1.push(rg.nextInt(100));
System.out.println("Unsorted : " + s1.toString());
size = s1.size()-1;
while(size > 0) {
temp = s1.pop();
for(int j=0; j < size; j++) {
if(temp >= s1.peek()) {
s2.push(temp);
temp=s1.pop();
} else {
s2.push(s1.pop());
}
}
s1.push(temp);
for(int k = size; k > 0 ; k--)
s1.push(s2.pop());
size= size-1;
}
System.out.println("Sorted :"+ s1);
}
}
S1 is in decending order moving to S2 will be ascending.
The above algorithm is finding the higest element in stack and moving the same to bottom of S1 and repeating the process upto complete stack is sorted.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment