Logic of Top-Down Sort:
15 These are the numbers I want to sort.
36
24
12
20
Pass 1:
|
Before |
Processing |
After |
|
|
Set up: Establish 2 subscripts: SUB1=1 and SUB2 = 2 |
|
|
15 36 24 12 20 |
Compare: 15 - what SUB1 is pointing to 36 - what SUB2 is pointing to 15 < 36 so leave alone |
15 36 24 12 20 |
|
15 36 24 12 20 |
Add 1 to SUB2 so, SUB2 = 3 Compare: 15 - what SUB1 is pointing to 24 - what SUB2 is pointing to 15 < 24 so leave alone |
15 36 24 12 20 |
|
15 36 24 12 20 |
Add 1 to SUB2 so, SUB2 = 4 Compare: 15 - what SUB1 is pointing to 12 - what SUB2 is pointing to 15 not < 12, so flip meaning move what SUB1 is pointing to, to the spot where SUB2 is pointing and what SUB2 was pointing to, to the spot where SUB1 was pointing |
12 36 24 15 20 |
|
12 36 24 15 20 |
Add 1 to SUB2 so, SUB2 = 5 Compare: 12 - what SUB1 is pointing to 20 - what SUB2 is pointing to 12 < 20 so leave alone |
12 36 24 15 20 |
|
|
The next add to SUB2 puts it out of the range of the table (5 elements in the table), so Pass 1 is over. Pass 1 ends with the smallest number in the table at the top - in element 1. |
12 36 24 15 20 |
Pass 2:
|
Before |
Processing |
After |
|
12 36 24 15 20 |
Start of Pass: 12 is locked in place Reset subscripts: SUB1 = 2 (add 1 to SUB1) and SUB2 = 3 (one more than SUB1) |
|
|
12 36 24 15 20 |
Compare: 36 - what SUB1 is pointing to 24 - what SUB2 is pointing to 36 not < 24 so flip |
12 24 36 15 20 |
|
12 24 36 15 20 |
Add 1 to SUB2 so, SUB2 = 4 Compare: 24 - what SUB1 is pointing to 14 - what SUB2 is pointing to 24 not < 15 so flip |
12 15 36 24 20 |
|
12 15 36 24 20 |
Add 1 to SUB2 so, SUB2 = 5 Compare: 15 - what SUB1 is pointing to 20 - what SUB2 is pointing to 15 < 20 so leave alone |
12 15 36 24 20 |
|
|
The next add to SUB2 puts it out of the range of the table (5 elements in the table), so Pass 2 is over. Pass 2 ends with the smallest two number in the table at the top - in element 1 and element 2. |
12 15 36 24 20 |
Pass 3:
|
Before |
Process |
After |
|
12 15 36 24 20 |
Start of Pass: 12 and 15 are locked in place Reset subscripts: SUB1 = 3 (add 1 to SUB1) and SUB2 = 4 (one more than SUB1) |
|
|
12 15 36 24 20 |
Compare: 36 - what SUB1 is pointing to 24 - what SUB2 is pointing to 36 not < 24 so flip |
12 15 24 36 20 |
|
12 15 24 36 20 |
Add 1 to SUB2 so, SUB2 = 5 Compare: 24 - what SUB1 is pointing to 20 - what SUB2 is pointing to 24 not < 20 so flip |
12 15 20 36 24 |
|
|
The next add to SUB2 puts it out of the range of the table (5 elements in the table), so Pass 3 is over. Pass 3 ends with the smallest three number in the table at the top - in element 1 and element 2 and element 3. |
12 15 20 36 24 |
Pass 4:
|
Before |
Processing |
After |
|
12 15 20 36 24 |
Start of Pass: 12 and 15 and 20 are locked in place Reset subscripts: SUB1 = 4 (add 1 to SUB1) and SUB2 = 5 (one more than SUB1) |
|
|
12 15 20 36 24 |
Compare: 36 - what SUB1 is pointing to 24 - what SUB2 is pointing to 36 not < 24 so flip |
12 15 20 24 36 |
|
|
The next add to SUB2 puts it out of the range of the table (5 elements in the table), so Pass 4 is over and since adding 1 to SUB1 would have it point at the last element in the table, the sort is over. Note: Since this example sorted 5 numbers, 4 passes were needed (one less than the number of numbers being sorted). |
12 15 20 24 36 |