Transcript Pascal I O(n2) Sorts

Computer Science 2
Review the Bubble Sort
Getting an unknown # of …. Into an
array.
Looking at another type of sort.
Learning Objectives
• Demonstrate how a Bubble Sort Works
• Be able to implement the code in order to
sort values
• Develop a method to storing an unknown
number of items in an array.
• Take a look at another method of sorting.
Bubble Sort Review
•
•
•
•
•
•
In your notes answer the following:
What is the speed of a bubble sort?
Is it stable?
What does stability mean?
How does a bubble Sort Work?
Show the following items after each pass
of the Bubble sort until they are in order.
• LOW
HIGH
• 50
8
20 14 6
12 2
Online
time.
Sorting Program
• Option #1
–
–
–
–
–
Randomly generate 100 scores from 1 to 50.
Show the numbers before they are sorted
show the numbers after they are sorted.
Push: Show graphically the numbers being sorted.
Push: Change it to 5000 numbers and time how long it takes for
them to sort.
– Push: Improve the efficiency of the sort.
• Option #2
– Input 10 race times for the 100 meter dash. (enter the time as
seconds)
– Output: The times sorted from fastest to slowest.
– Push: Enter the name that goes with each time, and show a chart of
names and times for the race.
How can you store an unknown
number of Song Titles into an array?
• Type
– Songtype = array[1..100] of string;
• Var
– Songs:songtype;
– numberOfSongs:integer;
Code
Another Sort
•
•
•
•
•
Selection Sort
http://en.wikipedia.org/wiki/Selection_sort
Speed:_________
Stability: _____________
How it works: _____________
Showing it after each pass
• Low
• 8 30
• High
• 10 14
22
3
15
26
2
15
45
High
3
31
Low
7
Selection Sort: Code
{*** This is just the sorting code }
for pass:= size downto 2 do
begin
mark:=pass;
for check:= 1 to pass do
if TheArray[check] > TheArray[mark] then
mark:=check;
{Mark}
dummy:=TheArray[mark]; {Switch}
TheArray[mark]:=TheArray[pass];
TheArray[pass]:= dummy;
end; {Of the for pass loop}
Program Options
• Song Sort: Input an unknown number of songs
(but less than 100)
–
–
–
–
Show out of order
Sort
Show in order
Push: Let the user also enter the Style of music, and be
able to sort by style.
• Name age sort
– Input: An unknown number of names and ages
– Output: The names and corresponding ages in a chart
sorted by age.
– Push: Let the user decide if they want to sort by age or
name, then sort and show the chart.