pjhayward's Pascal Tutorial

I recently got several questions about searching and sorting. Honestly, it sounded like someone was hoping for some help with their homework. If that's the case, here's my first bit of advice: Take the time to really understand what you're supposed to be learning. If you fudge your homework at this stage, you may never catch up.

With that said, I'll go ahead and answer the questions anyway, because I could use the practice.

First question: Write pseudocode for performing a sequential search.

A sequential search is exactly what it sounds like: it checks each item in the collection sequentially to see if it matches the search criteria. This is generally viewed as a bad approach, since there are a number of ways to improve your search efficiency. Still, the algorithm might go something like this:

For each item in collection
  If item meets search criteria
    return item
end for loop

This assumes you only want the first item that matches the criteria. If you want to be able to quickly repeat the search (which is often the case), you might want something more like this:

Create index storage list
For each item in the collection
  if item meets search criteria
    add item index to index storage list
end for loop
set search index to 0
return item from index storage list at the search index.

When you decide to want to search again, or if you want to search backwards, you just increment or decrement your search index and return the item in the index list at the search index. Easy!

Second question: Write pseudocode for inserting item in a queue

I'm going to make the assumption that this is for actually creating the queue, not using it. If you're using the queue, then it's a matter of queue.push(item) (or queue.offer(item), depending on the library), which is so trivial that I can't imagine it's the real question.

This question could be complicated somewhat by the fact that there are a number of ways to implement queues. Since the question asked for pseudocode, I'm going to assume the simplest solution - namely, that the queue is being stored in a dynamically sized list, meaning I don't have to reallocate memory and/or copy the list and all that mess. I will further assume that the queue is loaded from the tail, and unloaded at the head.

Append item to the end of the list.

Queues really are quite simple structures. You put items in one end, and pull them off the other. Inserting into the middle of the queue isn't permitted, which really simplifies things quite a bit.

An exception to that is if you are using priority queues. In the case of a priority queue, your submission will be added to the end of the list, then shifted to its appropriate location in the queue based on whatever requirements you choose for establishing priority. A list-based priority queue insert could look something like this: (yes, I know heap based priority queues are more efficient, but I don't want to take the time to explain heaps right now.)

Append item to the end of the list.
while item is not at the front of the list and item priority is higher than the preceding item
  swap item with preceding item

Third question: Write a pascal program that will produce the following output:
12345
23456
34567
45678
56789

program numberLoops;
var
  i:integer;
  j:integer;

begin
  for i:=1 to 5 do begin
    for j:= i to i+4 do begin
      write(j);
    end;
    writeln();
  end;
end.

While it's true that you could skip the innermost begin..end, I like to put them in to avoid problems if I need to modify the code later. Earlier on in my coding experience, I would skip them whenever I could, because it meant less typing. But after the fifth bug caused by adding code to be run as part of a loop that ended up outside the loop (because it wasn't inside a begin..end block), I decided it was worth the extra typing to avoid the bugs.

Fourth question: With the aid of a diagram, illustrate a descending order merge sort on the following numbers: 9,4,10,1,5,15,7

Okay, so this is the question that REALLY made me think this was a homework assignment. But hey, as long as you actually understand the material when you're done, I don't care.

Just to make sure I get this straight, I'm going to write out some merge sort psuedocode first.

If list size = 1 return list
split point = list size / 2;
sublist 1 = mergeSort(copy list from 0 to split point -1)
sublist 2 = mergeSort(copy list from split point to end)
create return list
while (sublist 1 size > 0 and sublist 2 size > 0)
  find larger value between sublist 1 [0] and sublist 2 [0]
    append largest value to the return list
    remove the value from its source sublist
return the return list.

Note that I'm grabbing the largest values first - that's because the question asked for descending order. If you wanted ascending order, you'd look for the smallest value first. So how do you know the first item in the sublist is the largest (or smallest) in the sublist? Because you've already sorted that sublist by passing it to another copy of the merge sort! Recursion is very powerful and useful, but you do need to be careful about making sure your program will eventually finish and exit the recursive loop. That's what the first line is for - that's the exit condition. Now for an illustration of how it works:

                                      Passed in lists                        Sorted lists
Initial call:                        {9,4,10,1,5,15,7}                     {15,10,9,7,5,4,1}
First level of recursion:      {9, 4, 10}        {1,5,15,7}            {10,9,4}        {15,7,5,1}
Second level:                {9}   {4, 10}     {1,5}  {15,7}          {9} {10,4}      {5,1} {15,7}
Third level                        {4} {10}   {1} {5} {15} {7}  ->       {4} {10}   {1} {5} {15} {7}

The actual order in which the sorted lists are obtained follow the order the passed in lists are made: So you'll get your list of {10,9,4} before you even start trying to sort {1,5,15,7}. Of course, if you wanted to be creative, you could start a new thread to handle sorting each sublist. But since concurrent programming wasn't part of the question, I don't think I'll confuse the issue by trying to explain it here.