Learn how to implement an algorithm to sort an array using two stacks and bubble sort paradigm in javascript.
Example
Input: 10 2 45 22 -1 0 Output: -1 0 2 10 22 45
Implementation to bubble sort an array with two stacks.
- First push all the elements of the array in one stack.
- Then loop all the elements of the array and alternatively swap the elements using both the stacks.
- To swap keep on pushing elements in one stack till the top of the other stack is smaller than the element being pushed from first stack.
- If the element being pushed is smaller than top of other stack then swap them (as in bubble sort).
- And in the end (tricky step) get the top element from the stack and place it in the array at its position.
- Keep doing this alternatively for both the stacks
let bubbleSortWithStack = (arr, n = arr.length) => { //First stack let stack1 = new Stack(); //Copy all the elements of //array in the stack for(let elm of arr){ stack1.push(elm); } //Second stack let stack2 = new Stack(); for(let i = 0; i < n; i++){ if(i % 2 == 0){ //Loop till stack1 has elements while(!stack1.isEmpty()){ //Get the top element from the stack1 let t = stack1.pop(); //If stack2 is empty then add the //Element to the stack2 if(stack2.isEmpty()){ stack2.push(t); }else{ //Else compare the top elements of stack1 and stack2 //And swap them based on the sorting order if(stack2.peek() > t){ let temp = stack2.pop(); stack2.push(t); stack2.push(temp); }else{ stack2.push(t); } } } // Tricky step arr[n-1-i] = stack2.pop(); }else{ //Loop till stack2 has elements while(!stack2.isEmpty()){ //Get the top element from stack2 let t = stack2.pop(); //If stack1 is empty then //Then add the element in the stack2 if(stack1.isEmpty()){ stack1.push(t); }else{ //Else compare the stack1 and stack2 top elements //And swap them based on the sorting order if(stack1.peek() > t){ let temp = stack1.pop(); stack1.push(t); stack1.push(temp); }else{ stack1.push(t); } } } //Tricky step arr[n-1-i] = stack1.pop(); } } }
Input: let arr = [10, 2, 45, 22, -1, 0]; bubbleSortWithStack(arr); console.log(arr); Output: [-1, 0, 2, 10, 22, 45]
Time complexity: O(n ^ 2).
Space complexity: O(n).