📄 pasl1008.html
字号:
<p>Finally, sorted : 1 2 3 4 5 6 7 8</p>
<p>You see that smaller data comes up like bubble and bigger data
sank down gradually, as you may note the 8. That's why this
method is called <b>bubble sort</b>.
</td></tr></table></center><p>
Before we go to quick sort, let's discuss shell sort. Well, shell sort is a
kind of exchange sort, actually, but it is optimized for speed. This algorithm
is invented by Donald Shell, long long ago. His algorithm was named according to his name.</p>
<p>The idea is comparing two datas in a quite distance in an array. Suppose, I
have 8 data. First I compare the first with the fifth, and so on. Look at
this excerpt :</p>
<pre>
for gap:=(NumberOfData div 2) downto 1 do
for i:=1 to NumberOfData-gap do
if Data[i]>Data[i+gap] then
swap Data[i] with Data[i+gap];
</pre><p>
It is quite similar to bubble sort, right ? Actually, it IS quite speedy
and powerful. Let's track it down ! Suppose we have 8 data, then gap is
initially 4 (8 <tt>div</tt> 2 is equal to 4, right ?). Variable i moves from 1 to 4.
It start comparing the first with the fifth, the second with the sixth, the
third with the seventh, and the fourth with the eighth. As usual, if there
are any mismatches in order, it swaps around. Then the gap reduces from 4
to 3. Again, i moves from 1 to 5, comparing it. And so on.
</p>
<p>(You may skip this if you want to)</p><hr><pre>
Let's look at our first scrambled data in our bubble sort example :
At first, gap is 4.
5 3 8 4 1 7 6 2
1st comparison : ^ ^ (mismatch order, swap)
1 3 8 4 5 7 6 2
2nd comparison : ^ ^ (good order, no swap)
3rd comparison : ^ ^ (mismatch order, swap)
1 3 6 4 5 7 8 2
4th comparison : ^ ^ (mismatch order, swap)
1 3 6 2 5 7 8 4 ----> Then the gap is 3.
5th comparison : ^ ^ (good order, no swap)
6th comparison : ^ ^ (good order, no swap)
7th comparison : ^ ^ (good order, no swap)
8th comparison : ^ ^ (good order, no swap)
9th comparison : ^ ^ (mismatch order, swap)
1 3 6 2 4 7 8 5 ----> Then the gap is 2.
10th comparison : ^ ^ (good order, no swap)
11th comparison : ^ ^ (mismatch order, swap)
1 2 6 3 4 7 8 5
12th comparison : ^ ^ (mismatch order, swap)
1 2 4 3 6 7 8 5
13th comparison : ^ ^ (good order, no swap)
14th comparison : ^ ^ (good order, no swap)
15th comparison : ^ ^ (mismatch order, swap)
1 2 4 3 6 5 8 7 ----> Then the gap is 1.
16th comparison : ^ ^ (good order, no swap)
17th comparison : ^ ^ (good order, no swap)
18th comparison : ^ ^ (mismatch order, swap)
1 2 3 4 6 5 8 7
19th comparison : ^ ^ (good order, no swap)
20th comparison : ^ ^ (mismatch order, swap)
1 2 3 4 5 6 8 7
21th comparison : ^ ^ (good order, no swap)
22th comparison : ^ ^ (mismatch order, swap)
1 2 3 4 5 6 7 8
</pre><hr>
<p>Finished and completely sorted. Easy, no ? Much faster than bubble sort.</p>
<p>Let's look at the fasted sort method in the world in general data : quick
sort. It is invented by E. Hoare. It uses recursive method exhaustively.
The idea is simple actually. Divide the data into two equal parts. Let the
middle data be the pivot point. Gather all data below the pivot into the
left side of the pivot, and the greater on the right. Let's see how is the
partings. The equal parts is now unequal in size, since there are possibilities
that one side is bigger than others. Each part is treated the same
way, sorted with the same way. But now, the left side is choosing its new
pivot and have two parts again. It is also done to the right side.
</p><p>Enough about lengthy theory. I'll bet you are yawning now. Let's look at
the inside : Suppose Data is a global array of byte.</p><hr>
<pre>
procedure qsort(lower, upper : byte)
var
left, right, pivot : byte;
begin
pivot:=Data[(lower+upper) div 2];
left:=lower;
right:=upper;
while left<=right do
begin
while Data[left] < pivot do left:=left+1; { Parting for left }
while Data[right] > pivot do right:=right-1;{ Parting for right}
if left<=right then { Validate the change }
begin
swap Data[left] with Data[right];
left:=left+1;
right:=right-1;
end;
end;
if right>lower then qsort(lower,right); { Sort the LEFT part }
if upper>left then qsort(left ,upper); { Sort the RIGHT part }
end;
</pre><hr>
<p>Usage : <tt>qsort(1,NumberOfData);</tt></p>
<p>(This is quite technical, you may skip this without losing the details of
the lesson. You may read this through to know how <tt>qsort</tt> works.)</p><hr>
<p>At first we assume that the center point of data contains the correct order
in the sequence. Thus, we make this as a pivot point. At the excerpt above,
we have two pointers, named left and right, pointing the first data and the
last one. Then we seek at the left hand side first for mismatch data. In
order to swap the data around, we must seek its pair on the right hand side
first. It is NOT the pivot we change, but the mismatches data so that they
place the correct parting.</p>
<p>You may wonder whether it is safe to do that assumption. Yes, IT IS. Why ?
It is because the search for mismatch data is not limited from edge to the
pivot, but it may overlap the center. Thus, the parting is not equal any
longer. The parting is decided when the left marker and the right marker
crosses. It means that the comparison is done throughout the data.</p>
<p>When the marker crosses, the left marker is at the right hand side of the
right marker so that RIGHT parting made of left marker and the upper bound
of the data. The LEFT parting is made from lower bound to right marker.
Then each parting is sorted again, using recursive method.</p>
<p>The two ifs before end; makes sure that the lower limit of the parameter
is always less than the upper limit. This also as a quitting conditions to
avoid endless repetitive recursive call.</p>
<p>Let's look at our first scrambled data :</p><pre>
5 3 8 4 1 7 6 2
Current position : | | |
left : at first data (5)---+ | |
right : at last data (2)---------+-------+
pivot : at fourth data(4)---------+ Remember that (1+8) div 2 = 4
Do the left parting :
5 > 4 --> mismatch the order, left marker stays
Do the right parting :
2 < 4 --> mismatch the order, right marker stays
Since left marker and right marker haven't crossed yet, it is legal to swap
both data, so it became :
2 3 8 4 1 7 6 5
Left marker moves to the second data (3), right marker to the seventh (6).
Since left marker and right marker haven't crossed yet, the main loop goes.
Do the left parting :
3 < 4 --> legal, continue.
8 >= 4 --> mismatch, left marker stays.
Do the right parting :
6 > 4 --> legal, continue.
7 > 4 --> legal, continue.
1 <= 4 --> mismatch, right marker stays.
Since left marker and right marker haven't crossed yet, it is legal to swap
both data, so it became :
2 3 1 4 8 7 6 5
Left marker moves to the fourth data (4), right marker moves to the fourth
data, too. It hasn't crossed yet, so it continues.
Left marker stops the left parting because 4 is not less than 4, so does
the right marker. It swaps itself, so nothing is changed. Then left marker
advances to the fifth data, right marker to third data.
Left parting is made by lower bound and right marker (data no 1 to 3) and
right one is made by left marker and upper bound (data no 5 to 8)
This goes to recursive process. Let's look at the left parting first.
2 3 1 ...
left marker = 2
right marker = 1
pivot = 3 { (1+3) div 2 = 2, Data[2]=3 }
Do the left parting :
2 < 3 --> legal, continue
3 >= 3 --> mismatch, left marker stops
Do the right parting :
1 <= 3 --> mismatch, right marker stops
Because left and right marker haven't crossed, it is legal
to swap data. So, it becomes :
2 1 3 ... (pivot is still=3)
Left marker advances to 3, and right marker to 1. It crossed.
The left parting would be from data no 1 to 2 and the right
parting would consist only 3.
We look into the left parting first:
2 1 ...
left marker = 2
right marker = 1
pivot = 2 { (1+2) div 2 = 1, Data[1] = 2 }
Do the left parting :
2 >= 2 --> mismatch, left marker stays
Do the right parting :
1 <= 2 --> mismatch, right marker stays.
Swap the data so we have 1 2 ..., now we advance both left and
right marker. It crossed. We have just 1 as the left parting
and 2 as the right parting. So, we have nothing to sort. We
then exit the recursive calls and revert to: 1 2 3 ...,
sorted form of the original left parting.
Then we look into the original right parting:
... 8 7 6 5
left marker = 8 (position 5)
right marker = 5 (position 8)
pivot = 7 { (5+8) div 2 = 6, Data[6] = 7 }
Do the left parting:
8 >= 7 --> mismatch, left marker stops
Do the right parting:
5 <= 7 --> mismatch, right marker stops
Data then swapped: ... 5 7 6 8
Then the left marker points at 7, the right marker points at 6
because we advance the pointer. The pivot is still 7.
Do the left parting:
7 >= 7 --> mismatch, left marker stops
Do the right parting:
6 <= 7 --> mismatch, right marker stops.
Then we swap the data: ... 5 6 7 8
And advance the pointers so that left marker points to 7 (again)
and right marker points at 6 (again) :-) Pivot is still 7.
The pointers are crossed, so we have another left parting from
5 to 6 and the right parting from 7 to 8. However, the data is
already sorted, so the parting is essentially does nothing but
to return from recursive calls.
All data sorted after quitting the recursive calls :
1 2 3 4 5 6 7 8
</pre>
<hr><p>Phew, quite a lengthy explanation, huh ? Looks like you need a break by now.
OK, see you next time !</p>
<hr><p><B><H3>Where to go ?</H3></B>
<A HREF="../news.html">Back to main page</A><BR>
<A HREF="pasles01.html">Back to Pascal Tutorial Lesson 1 contents</A><BR>
<A HREF="pasq1008.html">To the quiz</A><BR>
<A HREF="pasl1007.html">Back to Chapter 8</A> about processing strings<BR>
<A HREF="pasl1009.html">To Chapter 10</A> about complex data structure<BR>
<A HREF="../mylink.html">My page of programming link</A><BR>
<A HREF="../faq.html">Contact me here</A>
<hr><P CLASS="cpy">By : Roby Joehanes, © 1996, 2000</P>
</BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -