Top Down Sort

Speaker Notes

Slide 1:

This deals with the top down sort done on arrays or tables. The content of the array or table is reordered as a result of the internal sort.

Slide 2:

Again remember that you are sorting on an array or table. The original numbers that I am referring to would be in that structure. Note that there would also be data that these numbers point to such as the contents of an accumulator that is also in an array or table, a name that is also in an array or table etc. I will deal with that later in this presentation, but for now, the slides will focus on the sort.

In COBOL this could all be one table, in other languages it might have to be two arrays.

Note that there will be multiple passes before the sort is done. The number of passes is equal to the number of things to be sorted minus one. Since I need to sort 5 things, there will be four passes. If I needed to sort 12 things, there would be 11 passes.

Slide 3:

The before numbers show the numbers as they were at the end of the processing in the previous slide. The after numbers in each slide will become the before numbers in the next slide.

Note that I am still in pass #1 - pass 1 will end when all of the numbers have been checked once.

I am now incrementing SUB2 by 1. SUB1 represents the pass and it will stay 1 throughout pass1. SUB2 represents the thing that I am comparing to and will be incremented by 1 until all the numbers have been compared to the number thatSUB1 is pointing to.

Slide 4:

I am again incrementing SUB2 by 1 while SUB1 stays the same for the entire pass.

I am now comparing the number SUB1 is pointing to which is 15 to the number SUB2 is pointing to which is 12. They need to be flipped. To do a flip I need a hold area to store one of the numbers in while I am moving things around.

In this example, I am moving 15 to the HOLD, then I am moving 12 to where 15 used to be and then I am moving 15 back to where 12 used to be.

Note that I could have done the flip in the reverse order. Moving 12 to the hold area. Moving 15 to where 12 used to be, and finally moving 12 to the place where 15 used to be.

Slide 5:

I have now compared the number in position 1 to all of the elements in the table/array. Any flips were done to make sure that the smallest number is in the first spot in the table. Now when I move to the next step and increment SUB2, it will be outside the range of the table. That means that pass 1 is complete. See the next slide for information about preparing for pass 2.

Slide 6:

Note that the purpose of the first pass is to get the smallest number in slot 1. This was successful.

Now pass 2 is ready to start. The subscripts need to be reset. SUB1 is incremented to 2 for the second pass and SUB2 is set so that it will look at the next element in the table. In other words, the first element in the table is locked in and contains the smallest number. Now I am going to start to compare the second element in the table to the remaining elements starting with the number right below it.

Slide 7:

36 and 24 need to be flipped. 36 is moved to the HOLD. 24 is moved to where 36 is. Then 36 is moved back to where 24 was. The numbers are flipped.

Slide 8:

24 and 15 need to be flipped. 24 is moved to the hold area. 15 is moved to the spot that 24 occupies. 24 is moved to the spot where 15 was originally located.

Slide 9:

We have now done the last check for pass 2. When 1 is added to SUB2 it will put it outside the table range and so the pass will be complete. The next slide will reset.

Note that at this point the two smallest numbers are locked in to the first two positions of the table/array.

Slide 10:

Pass 2 is over because SUB2 is greater than the number of elements. At this point SUB1 is incremented by 1 to start looking at the next element. Then SUB2 is initialized at SUB1 + 1.

Note that at the end of the second pass, the first two numbers are in order and locked in as the first two elements of the final table/array.

Slide 11:

This is the start of pass 3. We are comparing the third element in the table/array that SUB1 is pointing to the fourth item in the table array that SUB2 is pointing to. Note that on the first check in a pass SUB2 is always 1 greater than SUB1.

The numbers need to be flipped. 36 is moved to the hold area, 24 is moved to where 36 was located. 36 is moved back to where 24 was originally.

Slide 12:

24 and 20 need to be flipped. 24 is moved to the hold area. 20 is moved to the place where 24 was located. Then 24 is moved back to the place where 20 was originally located.

Note that I have now compared to the last element in the table, when SUB2 is incremented it will be larger than the table/array so we will need to reset as shown on the next slide.

Note that at the end of pass 3, the three smallest numbers are locked in at the top.

Slide 13:

The three smallest numbers are locked at the top. SUB1 will now point to the fourth element and SUB2 will point to the fifth element.

Slide 14:

36 and 24 need to be flipped. 36 is moved to the hold area. 24 is moved to where 36 is currently located. 36 is moved from the hold area to where 24 was originally.

Slide 15:

When SUB1 is pointing to the last element of the table, there is nothing left to sort. If we tried to make SUB2 one bigger than SUB1 it would be outside the table.

Slide 16:

Note that when another element is involved such as name, it must be flipped as well. If number and name appear in the same array they can be held in the same hold area. If two arrays are involved (one for number and one for name), then you will need to have a hold area for the number and a hold area for the name.

The comparison remains unchanged. It is the flip that now involves making sure both parts are moved so the number and name will retain their association.