Selection Sort [**]

  1. read n, the length of the sequence
  2. read A1, A2 ,..., An
  3. unsorted <- n
  4. repeat until unsorted < 1
  5.   largest_so_far <- A1
  6.   location <- 1
  7.   i <- 2
  8.   while i < unsorted do
  9.      if Ai > largest_so_far then
  10.        largest_so_far <- Ai
  11.        location <- i // end if
  12.     i <- i + 1 // end while
  13.   Alocation <- Aunsorted
  14.   Aunsorted <- largest_so_far
  15.   unsorted <- unsorted - 1 // end until
  16. write A1, A2 ,..., An
  17. Stop

Note the reuse of the algorithm for finding largest (Steps 5-14).

[**] There are several versions of the selection sort, but they all include the basic operation of exchanging two values and putting them in order. The "bubble sort" is one such variation that restricts the exchanges to adjacent items. Which one is better in terms of complexity?

There is at least one aspect of this algorithm that does not meet the requirements set out previously. What is that?


[Prev][TOC][Next]


CS1104 Main Page
Last Updated 2002/02/01
© L.Heath, 2000, edited by J.A.N. Lee on above date.