Write an Insertion Sort algorithm for integer key values. However, there is a ca

Question

Write an Insertion Sort algorithm for integer key values. However, there is a catch. The input is a stack (not an array), and the only variables that your algorithm may use are a constant number of integers and a constant number of stacks. You can’t use arrays or any other data structures. The algorithm should return a stack containing the records in sorted order (with the least value being at the top of the stack). Like regular Insertion Sort, your algorithm’s worst-case running time should be (n^2).

Explanation / Answer

Algorithm for Insertion sort using stack as input

ALGORITHM:

Step1: BEGIN

Step2: Declare an integer temp

Step3: Create a temporary stack, temp_stack

Step4: IF input_stack is not empty then

goto Step5

ELSE

No need of sorting

Return input_stack

          END IF

Step5: WHILE input_stack is not empty

             5.1 POP an integer from input_stack and store it in variable temp.

             5.2 WHILE temp_stack is not empty AND temp>top element of temp_stack

                     5.2.1 POP an element from temp_stack and PUSH it into input_stack

          5.3 END WHILE

          5.4 PUSH temp into temp_stack

Step6: END WHILE

Step7: temp_stack is the sorted stack with least value at the top of temp_stack

Step8: END

---------------------------------------------------------------------------------------------------------------------------

Worst Case Time Complexity of Insertion sort using Stack as input:

Step 5:     Outer WHILE loop runs for number of elements in the input stack (i.e. n).

Step 5.2: Inner WHILE loop runs for (n-1) elements of input stack.

So total Time complexity can be stated as:

T (n) = n*(n-1) ~ O(n2)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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