1 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

32

15

2

17

19

26

41

17

17

Input:

In example above: Use j pointer to track current spot of traveling item.

2 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

32

15

2

17

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

3 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

32

15

2

17

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

sorted

unexamined

4 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

32

15

2

17

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

sorted

unexamined

5 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

15

32

2

17

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

6 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

15

32

2

17

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

sorted

unexamined

7 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

15

32

2

17

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

sorted

unexamined

8 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

15

2

32

17

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

Note: We’ve temporarily broken our invariant that the items up through item i should be sorted!

9 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

32

17

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

Once the traveller settles, the invariant is restored.

unexamined

10 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

32

17

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

sorted

unexamined

11 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

32

17

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

sorted

unexamined

12 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

32

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

13 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

32

19

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

sorted

unexamined

14 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

32

19

26

41

17

17

Input:

j

In example above: Use j pointer to track current spot of traveling item.

sorted

unexamined

i

15 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

32

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

16 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

32

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

sorted

17 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

32

26

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

sorted

18 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

26

32

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

19 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

26

32

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

sorted

unexamined

20 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

26

32

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

sorted

unexamined

21 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

26

32

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

22 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

26

32

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

sorted

23 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

26

32

41

17

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

sorted

24 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

26

32

17

41

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

25 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

26

17

32

41

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

26 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

19

17

26

32

41

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

27 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

17

19

26

32

41

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

28 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

17

19

26

32

41

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

sorted

29 of 35

Insertion Sort W/Swaps

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

17

19

26

32

41

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

sorted

30 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

17

19

26

32

41

17

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

unexamined

sorted

31 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

17

19

26

32

17

41

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

32 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

17

19

26

17

32

41

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

33 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

17

19

17

26

32

41

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

34 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

17

17

19

26

32

41

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

35 of 35

In-place Insertion Sort

General strategy:

  • Repeat for i = 0 to N - 1:
    • Designate item i as the traveling item.
    • Swap item backwards until traveller is in the right place among all previously examined items.

2

15

17

17

17

19

26

32

41

Input:

i

j

In example above: Use j pointer to track current spot of traveling item.

sorted