Sorting, Continued
We implemented the Bubble Sort
Hungarian folk dancers doing the bubble sort.
Trickle Down!
4 9 1 2 7 5 3 x
p = 1
4 9 1 2 7 5 3 x
p
p p += 1
4 9 1 2 7 5 3 x
p p += 1
4 9 1 2 7 5 3 I see x[k-1] > x[k] (neigbor to left is bigger)
4 1 9 2 7 5 3 k = p - 1
1 4 9 2 7 5 3
p
1 4 9 2 7 5 3
p
1 4 2 9 7 5 3
1 2 4 9 7 5 3
p
1 2 4 9 7 5 3
1 2 4 7 9 5 3
p
1 2 4 5 7 9 3
p hint while p < len(x):
p += 1
trickle down
p = 1
while p < len(x):
p += 1
trickle_down
p = 1
while p < len(x):
p += 1
k = p - 1
while k > 0 and x[k - 1] > x[k]:
swap(x, k - 1, k)
k -= 1
F Block
8 2 4 6 2 5
p p = 0
Scan through the list starting at p.
find the INDEX of the samllest element
swap it with p
increment p.
8 2 4 6 2 5
p k k = p
smallest = x[k]
smallest_index = p
k += 1
since x[k] < smallest, smallest_index = k
in gthis case, k = 1 is the smallest index
swap(x, p, k)
2 8 4 6 2 5
increment p.
2 8 4 6 2 5
p
k k = 2 is the index of the smalest so far
k do nothing
k k = 4 is the index of the smallest
k do nothing
swap(x, p, k)
2 2 4 6 8 5
p
k k = 2 is index of smallest swap with itself
2 2 4 6 8 5
p k = 5 is index of smallest
2 2 4 5 8 6
p k = 5 is index of the smallest
2 2 4 5 6 8
p while p < len(x):
smallest_value
index_of_smallest_value
k does the scanning
p divides sorted from non-sorted
B Block
9 5 3 1 7 8 input
p p = 1
p += 1
9 5 3 1 7 8
p
5 9 3 1 7 8 out of order so swap
p
5 9 3 1 7 8 p += 1
p
5 3 9 1 7 8 trickle down
3 5 9 1 7 8
p p += 1
3 5 1 9 7 8 trickle down
3 1 5 9 7 8
3 1 5 9 7 8
1 3 5 9 7 8
p
1 3 5 7 9 8 trickle down
p p += 1
1 3 5 7 8 9 p == len(x) indicates donness
p = 1
while p < len(x):
p += 1
trickle down
How does trickle down work?
1 4 7 9 10 3 x is my list. Put k = p - 1
p entry that moves is x[p - 1]
is x[k - 1] > x[k] Is the neighbor to the left bigger?
while the neighbor to the left is bigger, swap.
while k > 0 and x[k - 1] > x[k]:
swap(x, k - 1, k)
sorts.py We will have
a chance to implement these on Friday in open lab time.
Minisort We will step through this and you will implement it.
5 2 3 7 1 9 x
p p = 0
q find index of smallest element
swap by indices
1 2 3 7 5 9
p p += 1
q q = p
q find index of smallest element
swap by indices
1 2 3 7 5 9
p p += 1
q q = p
1 2 3 7 5 9
p
q
1 2 3 5 7 9
p
q
1 2 3 5 7 9
p
q
Gnome Sort This is described on
the sorts.py page. Try taking
a small list and doing it by hand to see it work. You can
watch an amimation of it here.
A Little Number Theory
Number theory focuses on the structure of the integers, especially insofar as divisibility is concerned. Both the mathematical and Pythonic language will be used here. Typography is the tell.
Definition. If \(d\) is a nonzero integer and \(a\) is any integer, we write \(d \vert a\) if for some integer \(q\), \(a = dq\). This is a formal way of saying that \(d\) divides \(a\) evenly. In this case we will say that \(d\) is a divisor or factor of \(a\). We will say that \(d\) is a proper divisor of \(a\) if \(d \not= \pm a\).
Notice that all integers are divisible by 1 and -1. Also notice that all nonzero integers divide 0 evenly.
If d and a are integers, we test
for divisiblity using the predicate a%d == 0.
Here are some simple facts about divisibility. supppse \(d\vert a\) and \(d \vert b\). Then we can write \(a = dq\) and \(b = sq\) for some integers \(s\) and \(t\). Notice that $$ a + b = dq + sq = q(d + s).$$ Since \(d + s\) is an integer, \(d\vert a + b\). Also, if \(c\) is an integer we have \(ac = dqc = d(qc)\). Since \(qc\) is an integer, \(d| ac\).
An easy consequence of this is that if \(d \vert a\) and \(d \vert b\), then \(d \vert ax + by\) for any integers \(x\) and \(y\).
Theorem. [Division Algorithm] If \(b\) and \(a\) are integers with \(a\gt 0\), then there are unique integers \(q\) and \(r\) so that \(b = aq + r\) and \(0 \le r \lt a\).
We shall not prove this theorem, although I should mention that the mechanism of doing so is the fact that any nonvoid subset of the positive integers has a least element.
This is the reason that the mod operator % works.
In fact, what this theorem delivers is that q = b//a
and r = b%a. That's what you really need to now.
Hence we have this identity.
b = a*b//a + b%a
Commmon Divisors Suppose that \(a\) and \(b\) are integers. An integer \(d\) is a common divisor of \(a) and \(b\) if \(d\vert a\) and \(d \vert b\). Observe that 1 is a common divisor of any pair of integers.
Since every pair of integers has a common divisor, and no divisor of an integer can be larger than that integer, every pair of integers has a greatest common divisor (gcd).
Here is the wormwood method of computing a gcd
gcd(144, 52)