HSC SDD - Planning and designing software solutions

An ascending selection sort successively looks for the largest value in the array and swaps it with the last element.

To achieve this we need to logically divide the array into two parts – an unsorted part and a sorted part. Each pass through the unsorted part finds the largest value and places it at the start of the sorted part. Initially the sorted part is empty. The size of the sorted part of the array increases by 1 with each pass.

Here is a video walk-through of the logic.

The following algorithm sorts an array of names into ascending order.

BEGIN SelectionSort
  Let EndUnsorted = number of names in the array
  WHILE EndUnsorted > 1
    Let i = 1
    Let Max = Name (i)
    Let PosMax = i
    WHILE i <= EndUnsorted
      Increment i
      IF Name (i) > Max THEN
        Let Max = Name (i)
        Let PosMax = i
      ENDIF
    ENDWHILE
    Swap (Name (PosMax), Name (EndUnsorted))
    Decrement EndUnsorted
  ENDWHILE
END SelectionSort

When SelectionSort calls the subroutine Swap, the parameters passed are Name (PosMax) and Name (EndUnsorted). In the subroutine Swap, general names (A and B) are used for the parameters. This allows this swap routine to be used for swapping any two variables.

BEGIN Swap (A, B)
  Let Temp = A
  Let A = B
  Let B = Temp
END Swap

If you need further information view http://courses.cs.vt.edu/csonline/Algorithms/Lessons/SelectionCardSort/index.html

ACTIVITY 4

View this document and research the most efficient sorting algorithm for the data. Then complete the algorithm and coding activity. Submit your answers here.