Defination:
Sorting and searching are among
the most common programming processes.
§ In selection
sort, The list is divided into two sublists, sorted and unsorted,
which are divided by an imaginary wall.
§ We find the
smallest element from the unsorted sublist and swap it with the element at the
beginning of the unsorted data.
§ After each
selection and swapping, the imaginary wall between the two sublists move one
element ahead, increasing the number of sorted elements and decreasing
§ the number of
unsorted ones.
§ Each time we
move one element from the unsorted sublist to the sorted sublist, we say that
we have completed a sort pass.
Example:
•
70 75 89 61 37
–
Smallest is 37
–
Swap with index 0
•
37 75 89 61 70
–
Smallest is 61
–
Swap with index 1
•
37 61 89
75 70
–
Smallest is 70
–
Swap with index 2
• 37
61 70 75 89
– Smallest
is 75
– Swap
with index 3
– Swap
with itself
• 37
61 70 75 89
– Don’t
need to do last element because there’s only one left.
Selection sort algorithm(descending):
1.
Find
largest element (of remaining elements).
2.
Swap
largest element with current element (starting at index 0).
3.
Finished
if at the end of the array. Otherwise, repeat 1 and 2 for the next index.
Example(descending):
•
8 4
9 8 3 5 1 6 7
–
Largest
is 98
–
Swap
with index 0
•
98 84
35 1 67
–
Largest
is 84
–
Swap
with index 1
–
Swap
with itself
•
9 8
8 4 3 5 1 6 7
–
Largest
is 67
–
Swap
with index 2
•
9 8
8 4 6 7 1 35
–
Largest
is 35
–
Swap
with index 3
•
9 8
8 4 6 7 3 5 1
–
Don’t
need to do last element because there’s only one left
•
9 8
8 4 6 7 3 5 1
