1
❐Chapter 13 presents several
common algorithms for
sorting an array of integers.
❐Two slow but simple
Quadratic Sorting
2
Sorting an Array of Integers
❐The picture
shows an
array of six
70
3
50
60
70
The Selectionsort Algorithm
❐Start by
finding the
smallest
entry.
4
70
The Selectionsort Algorithm
❐Start by
finding the
5
70
The Selectionsort Algorithm
❐Start by
finding the
70
[0] [1] [2] [3] [4] [5]
6
At this point, we can view the array as being split into two sides: To the
70
The Selectionsort Algorithm
70
Sorted side Unsorted side
7
60
70
The Selectionsort Algorithm
❐Find the
Sorted side Unsorted side
8
20
70
The Selectionsort Algorithm
❐Swap with
Sorted side Unsorted side
9
…and the effect is to increase the size of the sorted side by one
element.
The Selectionsort Algorithm
Sorted side Unsorted side
10
The Selectionsort Algorithm
Sorted side Unsorted side
11
The Selectionsort Algorithm
Sorted side Unsorted side
12
70
The Selectionsort Algorithm
Sorted side Unsorted side
Sorted side
is bigger
13
The Selectionsort Algorithm
❐The process
Sorted side Unsorted side
14
And now the sorted side has five elements.
The Selectionsort Algorithm
15
The Selectionsort Algorithm
❐The array is
16
70
The Insertionsort Algorithm
❐The
Insertionsort
algorithm
17
However, in the Selectionsort, the sorted side always contained the
70
The Insertionsort Algorithm
❐The sorted
Sorted side Unsorted side
18
The Insertionsort Algorithm
Sorted side Unsorted side