Solved

Could someone explain to me how Selection Sort works?

Posted on 2006-05-08
272 Views
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
Question by:warriorfan808

LVL 45

Expert Comment

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

LVL 41

Expert Comment

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

LVL 41

Accepted Solution

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

Suggested Solutions

zeroMAx challenge 20 66
changeXy challenge 13 40
noX challenge 17 53
delphi parse string to params 3 45
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
This is an explanation of a simple data model to help parse a JSON feed
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …