I am learning Pascal. Pascal? Pascal in 2016? Yes, Pascal!
I enrolled in an Open University course on imperative programming and unfortunately the university’s language of choice is Pascal. Currently I’m really struggling with the language’s syntax. All those begins and ends, semicolons, no semicolons…
But I’m in no position to judge a programming language. And let’s not forget, Pascal was used by Donald E. Knuth to create Tex!!
So I either give up or I better get my sh… together.
The first exercise is a simple merge program. Two already sorted lists have to be merged into a single result list.
List1 = [11, 14, 18, 80, 100]
List2 = [8, 11, 11, 17, 22, 30, 55, 70]
ResultList = [8, 11, 11, 11, 14, 17, 18, 22, 30, 55, 70, 80, 100]
It’s not allowed to…
- …copy both lists to the result list and then sort its elements.
- …copy one list to the result list and then insert the elements of the second list in the correct order.
This is the given program frame without implementation of the merge algorithm:
And this is a possible implementation of the merge algorithm:
We start by comparing the first value of the first list with the first value of the second list.
Either the value of Field1 is less than the value of Field2, equal to the value of Field2 or greater than the value of Field2.
List1 < List2 → Copy the value of List1 to the result list at first position (ResultList := List1).
Increase the counter i for List1 and k for ResultList.
List1 >= List2 → Copy the value of List2 to the result list at first position (ResultList := List2).
Increase the counter j for List2 and k for ResultList.
Wash, rinse, repeat until one of the two lists (List1, List2) runs out of elements:
while (i <= LISTLENGTH1) and (j <= LISTLENGTH2) do…
That’s how we start:
And so on.
This is how the while loop ends. List2 runs out of elements first:
We are out of the while loop, but do not know which one of our two lists still holds some elements. This is done by if i > LISTLENGTH1 then.
4 > 5? No, so it must be List2.
We iterate over the remaining elements in List2 and add each element to our result list. Let’s not forget to increase the counter for j and k each time we copy an element.
Et voilà. Done.