Transcript Topdown sort

Sorting arrays/tables
Top Down sort
Please use speaker notes for
additional information!
Top down sort - PASS #1
Original numbers:
15
36
24
12
20
SUB1
SUB2
1
2
HOLD
15
36
24
12
20
Compare 15 which is what SUB1 is
pointing to and 36 which is what
SUB2 is pointing to.
In this instance, 15 < 36 so nothing
is done.
After numbers:
15
36
24
12
20
Top down sort - PASS #1
Before numbers:
15
36
24
12
20
SUB1
SUB2
1
2
3
HOLD
15
36
24
12
20
Compare 15 which is what SUB1 is
pointing to and 24 which is what
SUB2 is pointing to.
In this instance, 15 < 24 so nothing
is done.
After numbers:
15
36
24
12
20
Top down sort - PASS #1
Before numbers:
15
36
24
12
20
SUB1
SUB2
1
2
3
4
15
36
24
12
20
HOLD
15
15
36
24
12
20
12
36
24
12
20
12
36
24
15
20
Three steps in flip:
1) Number SUB1 is pointing to is moved to hold
2) Number SUB2 is pointing to is moved to the
spot where SUB1 is pointing
3) Number from HOLD is moved to spot where
SUB2 is pointing
Compare 15 which is what SUB1 is
pointing to and 12 which is what
SUB2 is pointing to.
In this instance, 15 >12 so the
numbers must be flipped.
After numbers:
12
36
24
15
20
Top down sort - PASS #1
Before numbers:
12
36
24
15
20
SUB1
SUB2
1
2
3
4
5
HOLD
12
36
24
15
20
Compare 12 which is what SUB1 is
pointing to and 29 which is what
SUB2 is pointing to.
In this instance, 12 < 20 so nothing
is done.
After numbers:
12
36
24
15
20
Top down sort - PASS #1
Before numbers:
12
36
24
15
20
SUB1
SUB2
1
2
3
4
5
6
Adding 1 to SUB2 puts
SUB2 outside the range of
the table. Therefore the pass
is done. SUB1 is
incremented by 1 and SUB2
is reset to 1 more than SUB1.
PASS2 can now start.
12
36
24
15
20
At the end of the first pass,
the smallest number is located
in the first slot of the
array/table.
SUB1
1
2
SUB2
3
Numbers:
12
36
24
15
20
Top down sort - PASS #2
Before numbers:
12
36
24
15
20
SUB1
SUB2
2
3
12
36
24
15
20
HOLD
36
12
36
24
15
20
12
24
24
15
20
12
24
36
15
20
Three steps in flip:
1) Number SUB1 is pointing to is moved to hold
2) Number SUB2 is pointing to is moved to the
spot where SUB1 is pointing
3) Number from HOLD is moved to spot where
SUB2 is pointing
Compare 36 which is what SUB1 is
pointing to and 24 which is what
SUB2 is pointing to.
In this instance, 36 >24 so the
numbers must be flipped.
After numbers:
12
24
36
15
20
Top down sort - PASS #2
Before numbers:
12
24
36
15
20
SUB1
SUB2
2
3
4
12
24
36
15
20
HOLD
24
12
24
36
15
20
12
15
36
15
20
12
15
36
24
20
Three steps in flip:
1) Number SUB1 is pointing to is moved to hold
2) Number SUB2 is pointing to is moved to the
spot where SUB1 is pointing
3) Number from HOLD is moved to spot where
SUB2 is pointing
Compare 24 which is what SUB1 is
pointing to and 15 which is what
SUB2 is pointing to.
In this instance, 24 >15 so the
numbers must be flipped.
After numbers:
12
15
36
24
20
Top down sort - PASS #2
Before numbers:
12
15
36
24
20
SUB1
SUB2
2
3
4
5
12
15
36
24
20
Compare 15 which is what SUB1 is
pointing to and 20 which is what
SUB2 is pointing to.
In this instance, 15 < 20 so nothing
is done.
HOLD
The two smallest
numbers are locked
into the top
positions in the
array.
After numbers:
12
15
36
24
20
Top down sort - PASS #2
Before numbers:
12
15
36
24
20
SUB1
SUB2
2
3
4
5
6
Adding 1 to SUB2 puts
SUB2 outside the range of
the table. Therefore the pass
is done. SUB1 is
incremented by 1 and SUB2
is reset to 1 more than SUB1.
PASS3 can now start.
12
15
36
24
20
At the end of the second pass,
the 2 smallest numbers are
located in the first and second
slots of the array/table.
SUB1
1
2
3
SUB2
4
Numbers:
12
15
36
24
20
Top down sort - PASS #3
Before numbers:
12
15
36
24
20
SUB1
SUB2
3
4
12
15
36
24
20
HOLD
36
12
15
36
24
20
12
15
24
24
20
12
15
24
36
20
Three steps in flip:
1) Number SUB1 is pointing to is moved to hold
2) Number SUB2 is pointing to is moved to the
spot where SUB1 is pointing
3) Number from HOLD is moved to spot where
SUB2 is pointing
Compare 36 which is what SUB1 is
pointing to and 24 which is what
SUB2 is pointing to.
In this instance, 36 > 24 so the
numbers must be flipped.
After numbers:
12
15
24
36
20
Top down sort - PASS #3
Before numbers:
12
15
24
36
20
SUB1
SUB2
3
4
5
12
15
24
36
20
HOLD
24
12
15
24
36
20
12
15
20
36
20
12
15
20
36
24
Three steps in flip:
1) Number SUB1 is pointing to is moved to hold
2) Number SUB2 is pointing to is moved to the
spot where SUB1 is pointing
3) Number from HOLD is moved to spot where
SUB2 is pointing
Compare 24 which is what SUB1 is
pointing to and 20 which is what
SUB2 is pointing to.
In this instance, 24 > 20 so the
numbers must be flipped.
After numbers:
12
15
20
36
24
Top down sort - PASS #3
Before numbers:
12
15
20
36
24
SUB1
SUB2
3
4
5
6
Adding 1 to SUB2 puts
SUB2 outside the range of
the table. Therefore the pass
is done. SUB1 is
incremented by 1 and SUB2
is reset to 1 more than SUB1.
PASS4 can now start.
12
15
20
36
24
At the end of the third pass, the 3
smallest numbers are located in
the first, second and third slots of
the array/table.
SUB1
1
2
3
4
SUB2
5
Numbers:
12
15
20
36
24
Top down sort - PASS #4
Before numbers:
12
15
20
36
24
SUB1
SUB2
4
5
12
15
20
36
24
HOLD
36
12
15
20
36
24
12
15
20
24
24
12
15
20
24
36
Three steps in flip:
1) Number SUB1 is pointing to is moved to hold
2) Number SUB2 is pointing to is moved to the
spot where SUB1 is pointing
3) Number from HOLD is moved to spot where
SUB2 is pointing
Compare 36 which is what SUB1 is
pointing to and 24 which is what
SUB2 is pointing to.
In this instance, 36 > 24 so the
numbers must be flipped.
After numbers:
12
15
20
24
36
Top down sort - PASS #4
Before numbers:
12
15
20
24
36
SUB1
SUB2
4
5
6
Adding 1 to SUB2 puts
SUB2 outside the range of
the table. Therefore the pass
is done. When SUB1 is
incremented it points it at
the last element in the
table. This is the trigger to
tell us that the sort is done.
The sort is complete.
12
15
20
24
36
At the end of the
fourth pass, all of the
numbers are in order.
Numbers:
12
15
20
24
36
SUB1
1
2
3
4
5
Number and name
Three steps in flip:
Original numbers:
15
36
24
12
20
Original names:
Rake
Hoe
Shovel
Trowel
Sprinkler
SUB1
SUB2
HOLD
1
2
3
4
15 Rake
15
36
24
12
20
15 Rake
36 Hoe
24 Shovel
12 Trowel
20 Sprinkler
1) Number and name SUB1 is pointing to is
moved to hold
2) Number and name SUB2 is pointing to is
moved to the spot where SUB1 is pointing
3) Number and from HOLD is moved to spot
where SUB2 is pointing
12 Trowel
36 Hoe
24 Shovel
12 Trowel
20 Sprinkler
12 Trowel
36 Hoe
24 Shovel
15 Rake
20 Sprinkler
After numbers and names:
12 Trowel
36 Hoe
24 Shovel
15 Rake
20 Sprinkler