Application #6 Part1 Implement the following algorithm (method sort()) that sort

Question

Application #6

Part1

Implement the following algorithm (method sort()) that sorts entries on a stack: original stack contains entries that are not sorted. First create two empty stacks, destination and temp. At any given time, destination stack must hold the entries in sorted order, with the smallest at the top of the stack. Move the top entry of original stack to destination stack. Pop and consider the top entry topO of original stack. Using a while loop pop entries of destination stack and push them onto temp stack until you reach the correct place to put topO. Then push topO onto destination stack. Next using a while loop move all the entries from temp stack to destination stack. Repeat the process for as long as the original stack is not empty.

Part2

Now consider the following revision of the above algorithm (method sortRevised()) : after moving the top entry of original stack to destination stack, compare the new top entry topO of the original stack with the top entry of destination stack. Then either move entries from destination stack to temp stack or from temp stack to destination stack until you locate the correct position for topO. Push topO onto destination stack. Continue until original stack is empty. Finally move any entries remaining in temp stack to destination stack.

Your finished program should produce the following output:

***Calling sort method***

push 02 from original to destination

Moving entries from destination to temp

push 00 to destination

Moving entries from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

push 08 to destination

Moving entries from temp to destination

--> push 02 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

push 07 to destination

Moving entries from temp to destination

--> push 02 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

push 05 to destination

Moving entries from temp to destination

--> push 02 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

--> push 05 from destination to temp

push 06 to destination

Moving entries from temp to destination

--> push 05 from temp to destination

--> push 02 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

push 04 to destination

Moving entries from temp to destination

--> push 02 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

push 01 to destination

Moving entries from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 01 from destination to temp

--> push 02 from destination to temp

--> push 04 from destination to temp

--> push 05 from destination to temp

--> push 06 from destination to temp

--> push 07 from destination to temp

--> push 08 from destination to temp

push 09 to destination

Moving entries from temp to destination

--> push 08 from temp to destination

--> push 07 from temp to destination

--> push 06 from temp to destination

--> push 05 from temp to destination

--> push 04 from temp to destination

--> push 02 from temp to destination

--> push 01 from temp to destination

--> push 00 from temp to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 01 from destination to temp

--> push 02 from destination to temp

push 03 to destination

Moving entries from temp to destination

--> push 02 from temp to destination

--> push 01 from temp to destination

--> push 00 from temp to destination

Stack should be sorted (with sort()) ....

00 01 02 03 04 05 06 07 08 09

===================================

Testing the revised method

Setting the original stack to:

03 09 01 04 06 05 07 08 00 02

***Calling sortRevised method***

--> push 02 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

push 00 from original to destination

Moving entries from destination to temp

--> push 00 from destination to temp

--> push 02 from destination to temp

Moving entries from temp to destination

push 08 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

push 07 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

push 05 from original to destination

Moving entries from destination to temp

--> push 05 from destination to temp

Moving entries from temp to destination

push 06 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

--> push 05 from temp to destination

push 04 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

--> push 02 from temp to destination

push 01 from original to destination

Moving entries from destination to temp

--> push 01 from destination to temp

--> push 02 from destination to temp

--> push 04 from destination to temp

--> push 05 from destination to temp

--> push 06 from destination to temp

--> push 07 from destination to temp

--> push 08 from destination to temp

Moving entries from temp to destination

push 09 from original to destination

Moving entries from destination to temp

Moving entries from temp to destination

--> push 08 from temp to destination

--> push 07 from temp to destination

--> push 06 from temp to destination

--> push 05 from temp to destination

--> push 04 from temp to destination

push 03 from original to destination

Moving any remaining entries from temp to destination

--> push 02 from temp to destination

--> push 01 from temp to destination

--> push 00 from temp to destination

Stack should be sorted (with sortRevised()) ....

00 01 02 03 04 05 06 07 08 09

Explanation / Answer

import java.util.*;

public class SortStack<T extends Comparable<? super T>>

{

private Stack<T> stack;

public SortStack()

{

this.stack = new Stack<>();

}

/**

* Sorts a stack.

*

* @return a sorted stack

*/

public Stack<T> sort()

{

// TODO PROJECT #6 Part1

// this.stack represents the original stack

Stack<T> destination = new Stack<>();

Stack<T> temp = new Stack<>();

  

//Answer stars

while(!stack.isEmpty()) {

T topO = stack.pop();

while(!destination.isEmpty() && topO.compareTo(destination.peek()) > 0) {

temp.push(destination.pop());

}

destination.push(topO);

while(!temp.isEmpty()) {

destination.push(temp.pop());

}

}

//Answer ends

return destination;

}

/**

* Sorts a stack. (revised version)

*

* @return a sorted stack

*/

public Stack<T> sortRevised()

{

// TODO PROJECT #6 Part2

// this.stack represents the original stack

Stack<T> destination = new Stack<>();

Stack<T> temp = new Stack<>();

//Answer stars

while(!stack.isEmpty()) {

T topO = stack.pop();

while(!destination.isEmpty() && topO.compareTo(destination.peek()) > 0) {

temp.push(destination.pop());

}

while(!temp.isEmpty() && temp.peek().compareTo(topO) > 0) {

destination.push(temp.pop());

}

destination.push(topO);

}

while(!temp.isEmpty()) {

destination.push(temp.pop());

}

//Answer ends

return destination;

}

public void setStack(T... elements)

{

this.stack.clear();

System.out.println("Setting the original stack to:");

for (int i = 0; i < elements.length; i++)

{

this.stack.push(elements[i]);

System.out.print(elements[i] + " ");

}

System.out.println();

}

public static void main(String[] args)

{

SortStack sc = new SortStack();

sc.setStack("03", "09", "01", "04", "06", "05", "07", "08", "00", "02");

System.out.println(" ***Calling sort method***");

Stack<String> sortedStack = sc.sort();

System.out.println(" Stack should be sorted (with sort()) ....");

while (!sortedStack.isEmpty())

System.out.print(sortedStack.pop() + " ");

System.out.println();

System.out.println(" ===================================");

System.out.println(" Testing the revised method");

sc.setStack("03", "09", "01", "04", "06", "05", "07", "08", "00", "02");

System.out.println(" ***Calling sortRevised method***");

sortedStack = sc.sortRevised();

System.out.println(" Stack should be sorted (with sortRevised()) ....");

while (!sortedStack.isEmpty())

System.out.print(sortedStack.pop() + " ");

System.out.println();

} // end main

} // end SortStack

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.