Use pseudocode to describe a sorting algorithm using one stack, one queue, and a constant number of variables. The integers to sort are initially stored in unsorted order on the stack; once the algorithm terminates, they should appear in sorted order on the stack, with the largest element at the bottom. Your pseudocode can use the following data items:
- A stack S that can store elements of type int, and supports the operations push, pop, peek, and isEmpty;
- a queue Q that can store elements of type int, and supports the operations add, remove, element, and isEmpty;
- a constant number of variables of type int.
No other data structures can be used by your algorithm.
Your algorithm should satisfy the following pre- and postconditions:
Precondition: The stack S contains n distinct integers a1, . . . , an and the queue Q is empty.
Postcondition: The stack S contains n distinct integers b1,...,bn in the order from bottom to top, such that b1 > b2 > ··· > bn and {a1,...,an} = {b1,...,bn}.
Ideally, your algorithm has a worst-case running time of O(n2), assuming each stack and queue operation takes only constant time. You will get partial marks for an implementation that does not achieve this running time.
Argue informally why your algorithm is correct and state its running time.