Yep, I think I do that already, if only for the aesthetic pleasure of symmetry. Now that I know it’s optimal, I’ve got that reason, too.
Don’t leave me hanging! How do you do that by hand? Wikipedia is even less clear to me on this one than on the others.
Heapsort would be horribly inconvenient to do by hand. It would require maintaining index/position numbers for all your objects. Something a computer does easily — indeed automatically in a standard linear array — but would be a nuisance for real, physical objects manipulated by a person.
In the heap-building stage, you construct an implicit binary tree, where an object’s index position determines its location in the tree. The object at index X has its children at 2X and 2X+1, and its parent is at floor(X/2). When you add a new object at position N+1, you have to “percolate” it up through the tree: compare the object with its current parent; if it’s smaller (or “earlier” alphabetically), stop; otherwise exchange it with the parent and iterate on the same (now promoted) object. Iteration also stops if you reach the root of the tree, of course. Anyway, every time you swap objects, you’d also have to swap their index numbers in order to properly track the tree structure.
One pretty good explanation of Heapsort (with diagrams!) can be found here. Google turns up many others.
Heapsort is a very complicated algorithm to do by hand, sadly. Let’s see if I can remember how to do this.
The first step is to turn your unordered list into a heap. A heap has the following properties: the root item(at the ith position) is greater than its two children(at the (2 * i)th position and the (2 * i + 1)th position, and its two children are the root items of valid heaps. Note that eventually, the children of the root node won’t exist. That’s fine.
Here’s an example of a valid heap, with integers:
50 25 10 24 5 9 8 21
50, in the 1st position, is the root node of the entire heap. It’s children are the 2nd and 3rd nodes(21 and (21 + 1) respectively). 50 is greater than both 25 and 10, so the first property is satisfied. For the second property to be satisfied, both 25 and 10 must be the roots of valid heaps.
25, at the 2nd position, has its children in the 4th and 5th positions(2 * 2 and (2 * 2 + 1) respectively). 25 is greater than both 24 and 5, so the first property is satisfied. Now we need to check the second property again.
24, at the 4th position, would have children at both the 8th and 9th positions, but there’s only 8 items, so it only has the one child. 24 is greater than 21, so the first property is satisfied. 21 has no children, so it’s a valid heap(21 is greater than all of its children, since it has none). This means that 24 is the root of a valid heap.
5, in the 5th position, has no children, so it is also a valid heap. This means that 25 is at the root of a valid heap as well. You can repeat this check for the heap rooted at 10(the second position), and you’ll find that 10 is the root of a valid heap. Since 25 is the root of a valid heap and 10 is the root of a valid heap, 50 is the root of a valid heap. So our entire list is a valid heap.
The problem that we face is that the lists we want to sort may well not be valid heaps. “Heapifying” an arbitrary list is the first step of the heapsort algorithm. Before we worry about that, though, we need to know how to turn a specific kind of list (that we’ll call a semi-heap) into a heap, and then I’ll show you that every list is just made of semi-heaps, and by heapifying the semi-heaps we’ll end of heapifying the entire list.
A semi-heap is pretty simple. It’s a list where the two children of the root node are heaps. The only different from a heap is that in a semi-heap, the root node need not be larger than its children. So:
50 25 10 24 5 9 8 21
is a semi-heap(as well as a heap), because the two children are heaps, as I showed earlier. However, the following are also all semi-heaps:
50 25 100 24 5 9 8 21
1 25 10 24 5 9 8 21
21 25 10 24 5 9 8 22*****
25 50 10 24 5 9 8 21
Let’s look at the list marked with the *****. Suppose we wanted to turn that list into a heap. The only thing that seems out of place is the root node, 21. If we want the list to be a heap, the root element should be the largest, so let’s swap the root node, 21, with the largest node, 25. We’ll get:
25 21 10 24 5 9 8 22
Unfortunately, we still don’t have a heap. 21’s children are now 24 and 5, so the root is larger than its children – this is a semi-heap instead of a heap. Let’s swap again and see if that fixes the problem.
25 24 10 21 5 9 8 22
Still no good – 21 is smaller than its child, 22. One more time?
25 24 10 22 5 9 8 21
There. Now we have a valid heap. The exact algorithm for heapifying a semi-heap is:
The items in the second half of this list(0, 8, 35, 3, and 4) are all the roots of heaps because they have no children. Their parents are all semi-heaps. If we were to perform the heapify operation on the parents, they would all become heaps. Then the parents of the parents would be come semi-heaps, and could be heapified. If we were to repeat this process, eventually we’d heapify the first item, and the whole list would be a heap. Ensuring that we’re always working on semi-heaps may seem tricky but actually isn’t. Start at the half-way point of the list and work backwards and you’ll always be working on semi-heaps. On a 10 element list, for example, first heapify the 5th element, then the 4th, then the 3rd, then the 2nd and finally the 1st. Once you’re done, you’ll have a valid heap. An example is in order:
5 100 65 21 9 0 8 35 3 4
We start at the half-way point, the 5th element(9). 9 has one child(4), so it’s already been heapified. We move on to the 4th element.
21 has two children, 35 and 3. 21 is smaller than 35, so we swap the two:
5 100 65 35 9 0 8 21 3 4
21 now has no children, so it’s the root of a valid heap. We move on to the 3rd element.
65 has two children, 0 and 8. It’s already a valid heap. Move on to the second element.
100 has two children, 35 and 9. It’s already a valid heap. Move on to the first element.
5 has two children, 100 and 65. Swap 5 with the largest of its children:
100 5 65 35 9 0 8 21 3 4
5 now has 35 and 9 as its children. Swap again:
100 35 65 5 9 0 8 21 3 4
5 now has 21 and 3 as its children. Swap once more:
100 35 65 21 9 0 8 5 3 4
We’ve now turned our list into a valid heap.
How does this help with sorting? Well, notice that the largest element of the heap will always be at the root(think about it: the root is larger than its children. Its children are larger than their children, the the root is also larger than those children. Repeat the argument to show that the root is larger than every element in the heap). To sort the heap in an ascending(or, for the pedants, non-descending) order, we want the largest element at the end of the heap. So take the heap that you just created, and swap the largest element with the last element:
4 35 65 21 9 0 8 5 3 100
100 is exactly where we want it to be, so just leave it alone, and consider the rest of the array alone:
4 35 65 21 9 0 8 5 3 | 100
The first part is now a semi-heap. Do the heapify operation again, and the second largest element in the list will be at the root:
65 35 8 21 9 0 4 5 3 | 100
Now swap it with the last element of the heap:
3 35 8 21 9 0 4 5 | 65 100
Heapify:
35 21 8 5 9 0 4 3 | 65 100
Swap:
3 21 8 5 9 0 4 | 35 65 100
Heapify:
21 9 8 5 3 0 4 | 35 65 100
Swap:
4 9 8 5 3 0 | 21 35 65 100
Heapify:
9 5 8 4 3 0 | 21 35 65 100
Swap:
0 5 8 4 3 | 9 21 35 65 100
Heapify:
8 5 0 4 3 | 9 21 35 65 100
Swap:
3 5 0 4 | 8 9 21 35 65 100
Heapify:
5 4 0 3 | 8 9 21 35 65 100
Swap:
3 4 0 | 5 8 9 21 35 65 100
Heapify:
4 3 0 | 5 8 9 21 35 65 100
Swap:
0 3 | 4 5 8 9 21 35 65 100
Heapify:
3 0 | 4 5 8 9 21 35 65 100
Swap:
0 | 3 4 5 8 9 21 35 65 100
One you have only one element at the root, you’re done: the list is sorted.
Doing that by hand would probably be quite difficult, though.
I’m not terribly happy with the Wikipedia entry myself, but doing some googling and personal thunking, I’ll see if what I think is happening works if I try and do it here.
Firstly, if we have a stack of books like so:
ABCDEFGH (in order)
Now let’s split that up as so:
A BC DEFG (two for each on in the previous group)
Now we can pretend that, indeed, each pair of books is a child to the one in the group before it:
A
/ \
B C
/ \ / \
D E F G
So we know that in each parent § and child pair (C1 and C2), that the parent will be less than both of it’s children (P < C1 and P < C2), and the child on the left will be less than the one on the right (C1 < C2.)
So now if we have an unsorted stack of books:
H FU SDBE
H
/ \
F U
/ \ / \
S D B E
What we do is start from the lower right side and work our way left and up:
B < E? Yes (Figure out which is the higher of the two children)
U < E? No, fix it
H FE SDBU
H
/ \
F E
/ \ / \
S D B U
So now the U is in the right position, but obviously it is still funky.
B < U? Yes (Figure out which is the higher of the two children)
E < U? Yes (two conditions good)
E < B? No! Fix it
H FB SDEU
H
/ \
F B
/ \ / \
S D E U
Now we test under F. Just going to fast forward here:
H SB FDEU
H
/ \
S B
/ \ / \
F D E U
H FB DSEU
H
/ \
F B
/ \ / \
D S E U
H DB FSEU
H
/ \
D B
/ \ / \
F S E U
D HB FSEU
D
/ \
H B
/ \ / \
F S E U
D BH FSEU
D
/ \
B H
/ \ / \
F S E U
B DH FSEU
B
/ \
D H
/ \ / \
F S E U
Now we’ve gotten to the top and fixed it, but obviously things are still fishy, so we start again. But note that we will not do the top node! B is correct as the top. I believe that for each “pass,” we will lose one level that needs to be checked at the top.
B DE FSHU
B
/ \
D E
/ \ / \
F S H U
And it happens that after fixing just the lower right one, we are all done!
Correction after reading other explanators, it is the furthest right from which things get correct. And we toss him off to the side when we remake our tree.
Keep in mind that the bubble sort is very efficient against lists that are not badly ordered, which is why the Shell variation of the bubble sort works so well. In the bubble sort, the time consuming part of the sort is the actual swap, and the Shell sort swaps over a greater distance, making it more efficient.
For those that aren’t familiar with Shell vs. bubble - the traditional bubble sort compares an item in the list to its neighbor and swaps it if needed. The higher numbers “bubble” up to one end and the lower to the other. Shell simply does the same thing, but moves the numbers over a larger range than 1 at a time.
using pseudocode:
K = N-2.
Start:
I=1
J=K
SwapFlag=False
Compare:
if List(I) > List(J) then
swap List(I) and List(J)
SwapFlag=true
end if
J=J+1
if J <= N then
I=I+1
goto Compare
endif
’ at this point we have reached the end of the list. If a swap occurred, repeat using the same range.
if SwapFlag=true then
goto Start
endif
’ no swaps occured, so decrease the range using integer division
K=K\2
’ exit when we get to 1
if K=1 then
exit sort
else
goto Start
endif
By the time we get down to a regular bubble sort (K=2), the list is fairly well ordered and the bubble sort works efficiently.
Shell sort will hold its own with Quicksort et al. until you get up into fairly large numbers of items being sorted. Quicksort will then kick Shell’s butt pretty hard.