19
…and insert this element at the correct spot of the sorted side.
60
70
The Insertionsort Algorithm
❐...and
inserting it
Sorted side Unsorted side
20
50
60
70
The Insertionsort Algorithm
❐In this
example, the
new element
Sorted side Unsorted side
21
30
40
50
60
70
The Insertionsort Algorithm
❐Sometimes
we are lucky
and the new
inserted item
doesn’t need
Sorted side Unsorted side
22
40
50
60
70
The Insertionsort Algorithm
❐Sometimes
we are lucky
twice in a
row.
Sorted side Unsorted side
23
40
50
60
70
How to Insert One Element
❶Copy the
new element
to a separate
location.
Sorted side Unsorted side
24
50
60
70
How to Insert One Element
❷Shift
elements in
the sorted
side,
creating an
25
…like this.
Is this the correct spot for the new element? No, because the new
30
40
50
60
70
How to Insert One Element
❷Shift
elements in
the sorted
side,
creating an
open space
for the new
26
50
60
70
How to Insert One Element
❷Continue
shifting
elements…
27
50
60
70
How to Insert One Element
❷Continue
shifting
elements…
28
Finally, this is the correct location for the new element. In general there
are two situations that indicate the “correct location” has been found:
20
30
40
50
60
70
How to Insert One Element
❷…until you
reach the
location for
the new
element.
29
40
50
60
70
How to Insert One Element
❸Copy the
new element
back into the
array, at the
correct
Sorted side Unsorted si
d
30
50
60
70
How to Insert One Element
❐The last
element
must also be
inserted.
Start by
Sorted side Unsorted si
d
31
30
40
50
60
70
A Quiz
How many
shifts will
occur before we
copy this
element back
into the array?
32
30
40
50
60
70
A Quiz
❐ Four items
are shifted.
33
50
60
70
A Quiz
❐ Four items
are shifted.
❐And then
the element is
34
❐Both Selectionsort and Insertionsort have a worst-
case time of O(n2), making them impractical for
large arrays.
❐But they are easy to program, easy to debug.
❐Insertionsort also has good performance when the
array is nearly sorted to begin with.
❐But more sophisticated sorting algorithms are
needed when good performance is needed in all
cases for large arrays.
Timing and Other Issues
35
Feel free to send your ideas to:
Presentation copyright 1997 Addison Wesley Longman,
For use with
Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch.
Some artwork in the presentation is used with permission from Presentation Task Force
(copyright New Vision Technologies Inc) and Corel Gallery Clipart Catalog (copyright