Homework 15

Questions 8.2 from the course text.

Solution

InsertionSort ( Stack Input )
begin
  Stack Temp                  # temporary stack
  int anInteger               # new integer to be inserted
  boolean Done                # flag to check when integer is inserted

  for i = 1 to Input.Size     # go through all elements
    for j = 2 to i            # shift sorted list
       Temp.Push (Input.Pop) 

    anInteger = Input.Pop     # get new element
    Done = False              # init flag

    while !Temp.isEmpty       # while there are still ints on temp stack
       if (!Done) and (anInteger > Temp.Top)   # if we find position for new element
          Input.Push (anInteger)   # push it onto original stack
          Done = True              # and indicate we are done
       else
          Input.Push (Temp.Pop)    # otherwise, shift one element back onto original stack

    if (!Done)                # check for new smallest element
       Input.Push (anInteger) # and add to stack if necessary
end