Hello ! We meet again ! How are you ? Good ? Thank God ! Ready to take this lesson ? Good ! Topics discussed this time are :
Like an array, record is just grouping various data under one name. However array can only store ONE type of data, but record can store ALL kind of data, including arrays.
How could we declare a record ? Actually, record is a customized kind of data type. So, I hereby want to introduce you the type part of Pascal program. The type part is placed BEFORE the var part. Let's look at the outline of somewhat-complex-Pascal-program-structure :
program programname; uses units1, units2, ...; type name = variabletype; : : (type declarations) var (variable declarations) : : (procedures and functions) : : begin (main begin...end block) : : end.
You can declare variable type anywhere, but normally, before variable declaration. Here is one example to declare record :
type
TEmployee = record
name : string[25];
address : string[40];
age : byte;
position : string[10];
commision : real;
end;
var
x : TEmployee;
Record will be no use after its declaration if there are no variable using it. So, you can use the declaration if you have a variable of that kind of data. In this case, x. So, let's look at the main begin...end block :
begin x.name := 'Paul Doherty'; x.address := '11th Kingston Avenue'; x.age := 35; x.position := 'Salesman'; x.commision := 0.10; end.
Through x, all accesses are available. Beware that : TEmployee.name is NOT the way to access name field.
Each data stored inside a record is called FIELDS. So, the TEmployee has fields of name, address, age, position, and commision.
Sometime, if we have so many fields inside a record, we find it is bothersome to write the variable, like the example above : so many x has to be written. We may want to simplify it. The example above (the main begin..end block) can be written as follows :
begin
with x do
begin
name := 'Paul Doherty';
address := '11th Kingston Avenue';
age := 35;
position := 'Salesman';
commision := 0.10;
end;
end.
Suppose you have a variable called name, how can Pascal distinct it from the record fields of name ? Within with...do statement, the record field overrides. If you want to assign the name variable, not the one which is the field of x, do it outside of with...do block.
You can use array of records. Suppose you have declared the TEmployee record tag. Now you want to declare an array of it. It's simple :
var MyEmployee : array[1..100] of TEmployee;
Just like declaring normal arrays. How to access it ? Suppose I access the first element :
begin MyEmployee[1].name := 'Paul Doherty'; MyEmployee[1].address := '11th Kingston Avenue'; MyEmployee[1].age := 35; MyEmployee[1].position := 'Salesman'; MyEmployee[1].commision := 0.10; end.
With with...do it's all the same :
begin
with MyEmployee[1] do
begin
name := 'Paul Doherty';
address := '11th Kingston Avenue';
age := 35;
position := 'Salesman';
commision := 0.10;
end;
end.
Can we do nested record as looping and conditional do ? Good question ! It IS perfectly legal. But you may do it like this :
type
TCommision = record
sales : real;
production : real;
absence : real;
end;
TEmployee = record
name : string[25];
address : string[40];
age : byte;
position : string[10];
commision : TCommision;
end;
In that example, the field commision of TEmployee record tag is a record of TCommision. How to access the sales field of commision ? Easy ! Suppose you have declared x as a variable of TEmployee : x.commision.sales:=0.5; Just add another period after commision then type sales, that's it ! Using arrays are pretty much the same ! MyEmployee[1].commision.sales:=0.3;
You may nest records more than 2 steps. To accomplish such task you may use analogies to the previous example. To access them is quite the same, just type down the period and subfield name and so on. The deeper you nest, the longer you type.
You may use with...do block inside another with...do block to access nested records. Go on, try it !
One special caution should be taken :
Pascal give a special gift that may not even exist in other programming languages :
CONDITIONAL RECORDS. What is conditional records exactly ? Conditional records
are record with a variable length depending on the contents of a field. That field whose
contents become so important is called pivot field. Let's look at this :
type
TEmployee = record
Name : string[20];
Age : byte;
case department:byte of
0: (sales : longint);
1: (product : integer);
end;
TEmployee has the field of name, age, and department. Department is a byte field. If the department is 0, then the TEmployee contains sales field as the next field. Or else, in this case 1, it has product field as the next one. The usage is quite rare though. Yet, this is very useful indeed.
Need to know :
You have already known division in Pascal. How can we get the remainder ? Well, use mod :
x := n mod 13; { x is the remainder of n after divided by 13 }
As the lesson in this chapter is quite short, I decided to give you some extras. That is sorting methods. Three of which I'm going to tell you is the extreme :
The simplest but quite powerful sorting methods among all is bubble sort. It is very easy to implement. The idea is bubbling up the desired data into sorted order. Suppose we want to sort the data ascendingly, earlier or smaller data will come up gradually. The main layout algorithm for this, is just like this :
for i:=1 to NumberOfData-1 do
for j:=i+1 to NumberOfData do
if Data[i]>Data[j] then
swap Data[i] with Data[j];
That's all ! Very simple. If you want to sort descendingly, replace the '>' with '<' in If statement. Sorting a record using specific fields, like name or something just replace the if statement :
if Data[i].name<Data[j].name then ....
Unfortunately there are no first key and second key, as you may note. Pascal knows only the first key. How to accomplish the second key ? Errrm, you may sort the data twice. First with the second key, finally with the first key. Easy, no ?
Swapping datas require a temporary variable. The swap Data[i] .... can be changed into :
begin
t:=Data[i];
Data[i]:=Data[j];
Data[j]:=t;
end;
Note that t is a temporary variable. Variable t and the Data must be in the same type. Suppose Data is an array of byte, t must also an array of byte. Otherwise, computer will spit an error.
Some Pascal version may need special care in swapping records. Suppose t is a record and Data is an array of record of the same type. You may see the exchange is done through the fields. Example the record consists of name and address, the swapping is done like this :
begin
t.name:=Data[i].name; { one by one }
t.address:=Data[i].address;
Data[i].name:=Data[j].name;
Data[i].address:=Data[j].address;
Data[j].name:=t.name;
Data[j].address:=t.address;
end;
Yup ! Simple, eh ? All sorting methods need swapping and the swapping is done in the same way.
The algorithm :
(If you are curious, you may read through. If you are as just practical as
me, you may skip this part without losing lesson details.)
|
The idea of bubble sort is just comparing all the data. The first data is compared to the second, to the third, and so on until the end of the data. Then the second data compared to the third, to the fourth, so on. Then the third data to the fourth and so on ... and so on. Why it is called as the Bubble sort. It is because that the comparison and the swapping make the desired data to gradually come up like a bubble. Example : Suppose we have data like this Follow the algorithm -- i.e. comparing the first and the second data : 5 and 3. 5 is greater than 3, hence it must be swapped out Then the first and the third. Since 3 is smaller than 8, no swapping is necessary. Then the first and the fourth : No swapping either. The first and the fifth -- since 1 is smaller than 3, it must be swapped : And so on, till the end of data, the sequence remains the same. Then the second with the third -- no changes this time. The second with the fourth. Change must be done : And so on : 1 2 5 8 4 7 6 3 1 2 4 8 5 7 6 3 1 2 3 8 5 7 6 4 1 2 3 5 8 7 6 4 1 2 3 4 8 7 6 5 1 2 3 4 7 8 6 5 1 2 3 4 6 8 7 5 1 2 3 4 5 8 7 6 1 2 3 4 5 7 8 6 1 2 3 4 5 6 8 7 Finally, sorted : 1 2 3 4 5 6 7 8 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 bubble sort. |
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.
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 :
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];
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 div 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.
(You may skip this if you want to)
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
Finished and completely sorted. Easy, no ? Much faster than bubble sort.
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.
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.
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;
Usage : qsort(1,NumberOfData);
(This is quite technical, you may skip this without losing the details of the lesson. You may read this through to know how qsort works.)
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.
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.
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.
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.
Let's look at our first scrambled data :
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
Phew, quite a lengthy explanation, huh ? Looks like you need a break by now. OK, see you next time !
Where to go ?
Back to main page
Back to Pascal Tutorial Lesson 1 contents
To the quiz
Back to Chapter 8 about processing strings
To Chapter 10 about complex data structure
My page of programming link
Contact me here
By : Roby Joehanes, © 1996, 2000