Transcript File

Computer Science 2
2-4-2015
Sorting
Goals
Dry run review
Develop a process (pseudo code) and
code to put a bunch of things in order.
Write a program that will sort an array of
records.
for count:= 5 downto 1 do
program Sample2;
writeln(data[count].a:5, data[count].b:5:2);
type
rectype = record of
for count:= 1 to 4 do
a:integer;
begin
b:real;
with data[count] do
end;
begin
arraytype = array[1..5] of rectype;
a := a + b;
var
b := a*b;
data: arraytype;
end;
count:integer;
end;
begin
for count:= 1 to 5 do
for count := 1 to 5 do
with data[count] do
begin
writeln(a,b:5:2)
data[count].a:= 2* count;
end.
data[count].b:= count -2;
end;
for count:= 1 to 5 do
data[count].b:= data[count].b +data[count].a;
Sorting
How do you put things in order? (Low to
high)
Pseudo-Code
Develop a sorting algorithm
So…
How should this information be organized?
Sorted by school?
Sorted by name?
Sorted by type of gift?
Today’s goal. Be able to sort an array of
records using one of the sorts we have
seen previously.
Bubble Sort
Speed: O(n2)
Stability: Stable
How it works: Check- Switch
http://www.dat.ruc.dk/~keld/algoritmik_e99/Appl
ets/Chap08/Bubble/BubbleSort.html
Show it after each pass
Low
8
High
2
6
9
21 1
Bubble Sort: To sort by name
{This is just the code for Bubble Sort}
for pass:= 1 to (size -1) do
begin
for check:= 1 to size-1 do
if TheArray[check]
>TheArray[check+1]
begin
dummy:= TheArray[check];
TheArray[check]:= TheArray[check+1];
TheArray[check+1]:= dummy;
end;
end;{Of the for loop}
then
Array of Record Sorting Assignment
 10 name/phone numbers
 Get add the names and numbers
 Set it up as a menu (with the while loop)
 Show All
 Sort by Name
 Find Phone Number (Get a name and find the corresponding
number)
 Add a person (Push)
 Quit
 After the user searches for one name, let them search for other
names, until they are done.
 Push: Modify it to hold an unknown number of names.
 Push: Develop a faster method to find the person taking
advantage of the data being in order.