Transcript CIS 234: Arithmetic Shortcut Operators

CIS 234: Sorting
Dr. Ralph D. Westfall
May, 2010
Exercise


random number between 0 - 999
you try to guess the number



another person tells you whether each
guess is too high or too low
count how many tries it takes to guess the
number
try it again with 0 - 99, without hints

which is faster? why?
Sorting

very common in programming

necessary within programs that keep track
of a lot of data


retrieving information from a database
using social security #
also useful to make output more
understandable


lists e.g., phone directory
analyses e.g., best sales prospects
Sorting is Resource Intensive

requirements increase rapidly as the
number of items increases



processing time
memory
some algorithms are more efficient, but
they are also harder to program

algorithm is a formula or set of steps for
solving a problem
Sorting Resources - 2

for simple algorithms, processing time is
proportional to N * N (N = size of list)


list with 20 items takes 4 times longer to
sort than a list with 10 items (400 vs. 100)
more complex algorithms: processing
time is proportional to N * log2(N)

list with 20 items takes 2.6 times longer to
sort than a list with 10 items (86 vs. 33)
Sorting Resource Requirements
N
N * N N * log2(N)
10
100
33
20
400
86
50
2,500
282
100
10,000
664
10,000
100,000,000
132,877
20,000
400,000,000
285,754
50,000 2,500,000,000
780,482
100,000 10,000,000,000 1,660,964
Ratio?
1.0
1.5
2.9
5
250
465
1,064
2,000
Swapping


sorts need to exchange values to get
items in order
can't exchange values by just putting
values into each other
int a = 17;
int b = 8;
a = b; // a = ? b = ?
b = a; // a = ? b = ?
(hand check)
Swapping - 2

to avoid losing values, need a
temporary variable to hold 1 value
int a = 17;
int b = 8;
temporary = a;
a = b;
b = temporary;
// a = ? b = ?
// a = ? b = ?
// a = ? b = ?
Bubble Sort



simple, easy to program, slow
compares each number to a number
after it
if the 2nd number is smaller, the values
are exchanged


smaller (lighter) numbers "float" to top
process needs to be repeated (N – 1)
times or until no more exchanges
Bubble Sort - 2
for (a = 0; a < (numArray.length-1); ++a)
// not <= ; loop ends at ? # of repetitions ?
for (b = a + 1; b < (numArray.length); ++b)
if (numArray[a] > numArray[b])
{
temp = numArray[b];
numArray[b] = numArray[a];
numArray[a] = temp;
}
More Efficient Bubble Sort

calculate loop comparison values before
loops
for (a = 0; a < numArray.length-1; ++a)
for (b = a+1; b < numArray.length; ++b)
// replace above with:
lengthActual = numArray.length;
lengthMinus1 = lengthActual - 1;
for (a = 0; a < lengthMinus1; ++a)
for (b = a + 1; b < lengthActual; ++b)
Bubble Sort Mechanics



in 1st pass through loop, smallest value
"floats" to top position
don't need to compare top position next
time
in 2nd pass through loop, next smallest
value "floats" to 2nd from top
Exercise

visually demonstrate a bubble sort:




4-5 people holding numbers
1 person as outer loop
1 person as inner loop
switch positions based on moving
comparisons between each pair
Using a Sorting Class

use a separate class to sort arrays or
objects


can be used repeatedly in a program
possible problems


arrays are sorted in their memory
locations, so the previous order is lost
more difficult to set up a general sort that
can handle objects created from different
classes
Using a Sorting Class - 2

can handle sorting issues by creating a
separate array to be sorted



copy with System.arrayCopy(…) or create
array of objects with a getter to return sort
value to determine sorting of the objects
sort class receives 1 argument: this array
returns an array of positions in input array


1st element is position of smallest element
last element is position of largest, etc.
Sorting Class Creates Indexes

an index is an array of positions
index can be used as a subscript to find
items in the original array in sorted order
int[ ] myArray = {7, 9, 2, 4, 3};
int [ ] ndx
= {3, 4, 0, 2, 1};
value of myArray[0] ?
myArray[1] ?
int [ ] ndx2 = {2, 4, 3, 0, 1};
myArray[ndx2[0]] ? myArray[ndx2[1]] ?

Review




Why is sorting important?
Sorting doesn’t require much computer
resources: T or F?
In an inefficient sort, if the size of the
list doubles, the resource requirements
are ___ times greater?
A bubble sort is efficient: T or F?
Review - 2


To swap two values, how many extra
values are needed? 0, 1 or 2?
How are index values used to show the
sorted order of array elements?