Transcript Document

Insertion Sort
Suppose that you have a hand of cards that you want
to sort – in this case, assume that you have all
thirteen cards of one suit.
One way to do this is to put the cards in your hand
one at a time, in order.
So, you start with one card in your hand, say the 4.
Then you take the next card and, starting from the
right, slide the cards that are bigger towards the right
until you come to the right spot.

Insertion Sort (cont'd)



That is, you keep sliding over cards which are
bigger until you find a card that is smaller, or you
run out of cards.
Then you insert the new card in that spot.
You repeat this until all the cards have been placed
into the hand.
Insertion Sort Example
x =
a[x] =
Hand
0
7
x =
a[x] =
Card = 1
0
7
x =
a[x] =
Card = 1
0
x =
a[x] =
0
1
1
1
2
5
3 4
3 12

1
2
5
3 4
3 12

1
7
2
5
3 4
3 12
x =
a[x] =
Card = 5
0
1
x =
a[x] =
Card = 5
0
1
x =
a[x] =
0
1
1
7

3 4
3 12
2
7
3 4
3 12

1

1
5

1
7
2
2
7
3 4
3 12

2
5
3 4
3 12
x =
a[x] =
0
1
1
5
2
3
3 4
7 12

Running Time



In the worst case, we have to shift over all the
cards each time, so that's 1 card, then 2 cards, then
3 cards, ... for a total for n*(n-1)/2.
That's the same as Selection Sort and Bubble Sort.
In the best case, we don't have to shift over any
cards, so the time is proportional to the number of
cards. That's called linear time.
When to Use Each Sort



Insertion sort is fast when the data is in order, or
nearly in order, that is, either a few items are out of
place, or many are out of place, but near to where
they should be.
Selection sort is used when it is expensive to swap
items, since each item is swapped just once. That
means when we are copying large items.
Bubble sort is good for tests – it's only four lines.
Bubble Sort Revisited
We can make Bubble Sort a little more efficient (in
the best and and average case) by checking if we
actually do any swaps. If no swaps are done, then
the list is in order, and we can stop sorting.
Random Algorithms
An interesting class of algorithms are random
algorithms, or stochastic algorithms. We use
(pseudo-) random numbers to help us in solving a
problem. For example, we can estimate the value
of Pi (the ratio of the circumference of a circle to it
s diameter) by doing the following:
Estimating Pi



Draw a square, say two feet per side on the
ground.
Inside the square, draw a circle of diameter two
feet.
From a distance, throw pennies onto the square
and count the number of pennies that land in the
circle.
Estimating Pi (cont'd)


Since the fraction of pennies that land in the circle
is proportional to the size of the circle vs. the
square, we can estimate Pi.
Pi = 4 * number of pennies inside the
circle/number of pennies thrown.