Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 283
  • Last Modified:

Could someone explain to me how Selection Sort works?

In my book, I have this example:

  89   45   68   90   29   34   17
  17 | 45   68   90   29   34   89
  17   29 | 68   90   45   34   89
  17   29   34 | 90   45   68   89
  17   29   34   45 | 90   68   89
  17   29   34   45   68 | 90   89
  17   29   34   45   68   89 | 90

for i := 0 to n – 2 do
      min := i
      for  j := i+1 to n-1 do
      if A[j] < A[min] min := j
swap A[i] and A[min]

for some reason, this just doesn't look right.  Could someone go line for line what it's doing?
0
warriorfan808
Asked:
warriorfan808
  • 2
1 Solution
 
sunnycoderCommented:
Hi warriorfan808,

The selection sort works by selecting the smallest unsorted item remaining in the list, and then swapping it with the item in the next position to be filled.

for i := 0 to n – 2 do  --- loop over all elements
     min := i   ---- index of element you will fill with smallest remaining element
      for  j := i+1 to n-1 do   ----- for all elements from this position to end of array
     if A[j] < A[min] min := j   ----- keep track of smallest element encountered so far
swap A[i] and A[min]      ------- swap index min with i .... after this step index min will have the smallest element from i to n-1. Note that we had initialized min to i ... so i now has the smallest element and we can proceed to sort from i+1 to n-1 and that is exactly what next iteration will do.

Cheers!
Sunnycoder
0
 
HonorGodCommented:
Index |  0 |  1 |  2 |  3 |  4 |  5 |  6
       +---------------------------------
 i = 0 | 89   45   68   90   29   34   17
     1 | 17 | 45   68   90   29   34   89
     2 | 17   29 | 68   90   45   34   89
     3 | 17   29   34 | 90   45   68   89
     4 | 17   29   34   45 | 90   68   89
     5 | 17   29   34   45   68 | 90   89
 done  | 17   29   34   45   68   89 | 90


 1 : for i := 0 to n – 2 do
 2 :   min := i
 3 :   for j := i + 1 to n - 1 do
 4 :     if A[ j ] < A[ min ] min := j
 5 :   swap A[ i ] and A[ min ]

The value of 'n' represents the number of items in the array (i.e., 7).
The value of 'i' is used to iterate through the array elements, from
the first element (i.e., A[ 0 ]) to the last to be processed
(i.e., A[ n - 2 ] == A[ 5 ]).  We will see, shortly, why we are able
to "stop" at A[ 5 ].

Within the outer (or 'i') loop, we will locate the index of the smallest
(or minimum) value remaining in the unordered portion of the array
(i.e., A[ i ] .. A[ n - 1]).  At the end of the inner (or 'j' loop),
'min' will contain the index of the element with the smallest value.

When we start the inner loop (line 3, above), the values of i, min, j
and the array A can be represented as follows:

   Index |  0 |  1 |  2 |  3 |  4 |  5 |  6
         +----+----+----+----+----+----+----+
   i = 0 | 89 | 45 | 68 | 90 | 29 | 34 | 17 |
         +----+----+----+----+----+----+----+
            ^    ^
            |    |
 min = 0 ---+    |
   j = 1 --------+

The test (in line 4), checks to see if the element referenced by A[ j ]
happens to be less than the element referenced by A[ min ].  If the
result of the test is true, then we have located a new minimum element.

   Index |  0 |  1 |  2 |  3 |  4 |  5 |  6
         +----+----+----+----+----+----+----+
   i = 0 | 89 | 45 | 68 | 90 | 29 | 34 | 17 |
         +----+----+----+----+----+----+----+
                 ^    ^
                 |    |
 min = 1 --------+    |
   j = 2 -------------+

This is reflected by the fact that the value of 'j' is copied into the
variable 'min'.  'j' is then increamented, and the test is performed
again.

   Index |  0 |  1 |  2 |  3 |  4 |  5 |  6
         +----+----+----+----+----+----+----+
   i = 0 | 89 | 45 | 68 | 90 | 29 | 34 | 17 |
         +----+----+----+----+----+----+----+
                 ^         ^
                 |         |
 min = 1 --------+         |
   j = 3 ------------------+

This time, A[ min ] is less than A[ j ], so min remains unchanged,
while 'j' gets increamented, and we have ...

   Index |  0 |  1 |  2 |  3 |  4 |  5 |  6
         +----+----+----+----+----+----+----+
   i = 0 | 89 | 45 | 68 | 90 | 29 | 34 | 17 |
         +----+----+----+----+----+----+----+
                 ^              ^
                 |              |
 min = 1 --------+              |
   j = 4 -----------------------+

This time, we find a new minimum, and 'j' is copied into 'min' before
we increment it.

   Index |  0 |  1 |  2 |  3 |  4 |  5 |  6
         +----+----+----+----+----+----+----+
   i = 0 | 89 | 45 | 68 | 90 | 29 | 34 | 17 |
         +----+----+----+----+----+----+----+
                                ^    ^
                                |    |
 min = 4 -----------------------+    |
   j = 5 ----------------------------+

This test fails, and j simply gets incremented.

   Index |  0 |  1 |  2 |  3 |  4 |  5 |  6
         +----+----+----+----+----+----+----+
   i = 0 | 89 | 45 | 68 | 90 | 29 | 34 | 17 |
         +----+----+----+----+----+----+----+
                                ^         ^
                                |         |
 min = 4 -----------------------+         |
   j = 6 ---------------------------------+

The final test succeeds, and the inner loop completes (i.e., j has
reached the final value of n - 1).

   Index |  0 |  1 |  2 |  3 |  4 |  5 |  6
         +----+----+----+----+----+----+----+
   i = 0 | 89 | 45 | 68 | 90 | 29 | 34 | 17 |
         +----+----+----+----+----+----+----+
                                          ^
                                          |
 min = 6 ---------------------------------+

When we finish the inner ('j') loop, the value of 'min' is the index
of the smallest value found (i.e., 6).  Since this is the smallest
value, we want it to be placed first in the array.  However, we don't
want to lose the element in that position, so we swap (or exchange)
the element in A[ i ] with that of A[ min ].  And we increament the
value of the outer loop control variable (i)

   Index |  0 |  1 |  2 |  3 |  4 |  5 |  6
         +----+----+----+----+----+----+----+
   i = 1 | 17 | 45 | 68 | 90 | 29 | 34 | 89 |
         +----+----+----+----+----+----+----+

Thus, the outer loop specifies the "first" element of the "remaining
portion" of the array.  That is, 'i' is the element that will contain
the next smallest value in the remaining elements.  Since we are
starting with 'i', the first element against which it should be
compared is i + 1.  And since the inner loop will be specifying the
elements against which a comparison will occur, this value (j) will
always be above the value i.  This is why the outer loop can be from
0 to n - 2.  Because n - 1 is the largest valid index, and the inner
loop will always be specifying at least 1 more than the outer loop.
If we had the outer loop as:

 1 : for i := 0 to n – 1 do

Then the inner loop would not need to be executed, since the first
value for j would be i + 1, which in this case would be (n - 1) + 1
which is a value larger than the largest value of our array index.

So, the values provided at the beginning, show the elements of the
array after the completion of each iteration of the outer loop:

 Index |  0 |  1 |  2 |  3 |  4 |  5 |  6
       +---------------------------------
 i = 0 | 89   45   68   90   29   34   17
     1 | 17 | 45   68   90   29   34   89
     2 | 17   29 | 68   90   45   34   89
     3 | 17   29   34 | 90   45   68   89
     4 | 17   29   34   45 | 90   68   89
     5 | 17   29   34   45   68 | 90   89
 done  | 17   29   34   45   68   89 | 90
0
 
HonorGodCommented:
Sorry, the proportional font makes the output look terrible...  If you copy the text, and paste it into an empty notepad, it might be easier to read.
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now