Data Structures : Selection Sort

Data Structures

Sorting

Selection sort

Algorithm

The algorithm works as follows:

1. Find the minimum value in the list

2. Swap it with the value in the first position

3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)

Example:

                    64 25 12 22 11

        11 25 12 22 64

        11 12 25 22 64

        11 12 22 25 64

        11 12 22 25 64 

(Nothing appears changed on this last line because the last 2 numbers were already in order)

 Question: 

Show the steps of a selection sort on the following data: 

C D F M R S A E B

1-  How many comparisons of element did you make for this sort? 

2-  How many moves of elements did you make for this sort?

Answer:

C D F M R S A E B (Comp. 1, Swap 1) 

A D F M R S C E B (Comp. 2, Swap 2)

A B F M R S C E D (Comp. 3, Swap 3)

A B C M R S F E D (Comp. 4, Swap 4)

A B C D R S F E M (Comp. 5, Swap 5)

A B C D E S F R M (Comp. 6, Swap 6)

A B C D E F S R M (Comp. 7, Swap 7)

A B C D E F M R S (Comp. 8, Swap 7)

A B C D E F M R S

1-  8 comparisons.

2-  7 movements.