? 2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 1
Chapter 10
Sorting and Searching
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 2
Chapter 10 Objectives
After you have read and studied this chapter,you
should be able to
Perform linear and binary search algorithms on small
arrays.
Determine whether a linear or binary search is more
effective for a given situation.
Perform selection and bubble sort algorithms.
Describe the heapsort algorithm and show how its
performance is superior to the other two algorithms.
Apply basic sorting algorithms to sort an array of objects.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 3
Searching
When we maintain a collection of data,one of the operations we need is a search routine to locate desired data quickly.
We will use an array of integers to present searching algorithms,Here’s the problem statement:
Given a value X,return the index of X in the array,if such X
exists,Otherwise,return NOT_FOUND (-1),We assume there
are no duplicate entries in the array.
We will count the number of comparisons the algorithms make to analyze their performance,The ideal searching algorithm will
make the least possible number of comparisons to locate the desired data.
Two separate performance analyses are normally done,one for successful search and another for unsuccessful search.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 4
Search Result
number
23 17 5 90 12 44 38
0 1 2 3 4 5 6 7 8
84 77
Unsuccessful Search:
Successful Search:
NOT_FOUNDsearch( 45 )
search( 12 ) 4
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 5
Linear Search
Search the array from the first to the last position in linear
progression,
public int linearSearch ( int[] number,int searchValue )
{
int loc = 0;
while ( loc < number.length && number[loc] != searchValue ) {
loc++;
}
if ( loc == number.length) { //Not found
return NOT_FOUND;
}
else {
return loc; //Found,return the position
}
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 6
Linear Search Performance
We analyze the successful and unsuccessful searches
separately,
We count how many times the search value is
compared against the array elements.
Successful Search
Best Case – 1 comparison
Worst Case – N comparisons (N – array size)
Unsuccessful Search
Best Case =
Worst Case – N comparisons
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 7
Binary Search
If the array is sorted,then we can apply the binary search
technique,
number
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
The basic idea is straightforward,First search the value in
the middle position,If X is less than this value,then search
the middle of the left half next,If X is greater than this
value,then search the middle of the right half next,Continue in this manner.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 8
Sequence of Successful Search - 1
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 44 )low high mid
0 8#1
highlow
2 h ig hlo wm id
38 < 44 low = mid+1 = 5
mid
4
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 9
Sequence of Successful Search - 2
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 44 )low high mid
0 8#1
2 h ig hlo wm id
44 < 77high = mid-1=5
4
mid
6
highlow
5 8#2
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 10
Sequence of Successful Search - 3
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 44 )low high mid
0 8#1
2 h ig hlo wm id
44 == 44
4
5 8#2 6
highlow
5 5#3
mid
5
Successful Search!!
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 11
Sequence of Unsuccessful Search - 1
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 45 )low high mid
0 8#1
highlow
2 h ig hlo wm id
38 < 45 low = mid+1 = 5
mid
4
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 12
Sequence of Unsuccessful Search - 2
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 45 )low high mid
0 8#1
2 h ig hlo wm id
45 < 77high = mid-1=5
4
mid
6
highlow
5 8#2
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 13
Sequence of Unsuccessful Search - 3
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 45 )low high mid
0 8#1
2 h ig hlo wm id
44 < 45
4
5 8#2 6
highlow
5 5#3
mid
5
low = mid+1 = 6
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 14
Sequence of Unsuccessful Search - 4
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 45 )low high mid
0 8#1
2 h ig hlo wm id
4
5 8#2 6
5 5#3 5
high low
6 5#4
Unsuccessful Search
low > highno more elements to search
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 15
Binary Search Routine
public int binarySearch ( int[] number,int searchValue )
{
int low = 0,
high = number.length - 1,
mid = (low + high) / 2;
while ( low <= high && number[mid] != searchValue ) {
if (number[mid] < searchValue) {
low = mid + 1;
}
else { //number[mid] > searchValue
high = mid - 1;
}
mid = (low + high) / 2; //integer division will truncate
}
if ( low > high) {
mid = NOT_FOUND;
}
return mid;
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 16
Binary Search Performance
Successful Search
Best Case – 1 comparison
Worst Case – log2N comparisons
Unsuccessful Search
Best Case =
Worst Case – log2N comparisons
Since the portion of an array to search is cut into half after every comparison,we compute how many times
the array can be divided into halves,
After K comparisons,there will be N/2K elements in the list,We solve for K when N/2K = 1,deriving K =
log2N.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 17
Comparing N and log2N Performance
Array Size Linear – N Binary – log2N
10 10 4
50 50 6
100 100 7
500 500 9
1000 1000 10
2000 2000 11
3000 3000 12
4000 4000 12
5000 5000 13
6000 6000 13
7000 7000 13
8000 8000 13
9000 9000 14
10000 10000 14
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 18
Sorting
When we maintain a collection of data,many applications call for rearranging the data in certain order,e.g,arranging Person
information in ascending order of age.
We will use an array of integers to present sorting algorithms,Here’s the problem statement:
Given an array of N integer values,arrange the values into
ascending order.
We will count the number of comparisons the algorithms make to analyze their performance,The ideal sorting algorithm will make
the least possible number of comparisons to arrange data in a designated order.
We will compare different sorting algorithms by analyzing their worst-case performance.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 19
Selection Sort
1,Find the smallest element
in the list.
0 1 2 3 4 5 6 7 8
23 17 5 90 12 44 38 84 77
minfirst
exchange
0 1 2 3 4 5 6 7 8
5 17 23 90 12 44 38 84 77
sorted unsorted
This is the result of one pass.
2,Exchange the element in
the first position and the
smallest element,Now the
smallest element is in the first position,
3,Repeat Step 1 and 2 with
the list having one less
element (i.e.,the smallest
element is discarded from further processing).
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 20
Selection Sort Passes
0 1 2 3 4 5 6 7 8
5 17 23 90 12 44 38 84 77
sorted
5 12 23 90 17 44 38 84 772
5 12 17 90 23 44 38 84 773
5 12 17 23 38 44 77 84 907
5 12 17 23 38 44 77 84 908
1
Pass #
Result AFTER one
pass is completed.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 21
Selection Sort Routine
public void selectionSort( int[] number )
{
int startIndex,minIndex,length,temp;
length = number.length;
for (startIndex = 0; startIndex <= length-2; startIndex++){
//each iteration of the for loop is one pass
minIndex = startIndex;
//find the smallest in this pass at position minIndex
for (i = startIndex+1; i <= length-1; i++) {
if (number[i] < number[minIndex]) minIndex = i;
}
//exchange number[startIndex] and number[minIndex]
temp = number[startIndex];
number[startIndex] = number[minIndex];
number[minIndex] = temp;
}
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 22
Selection Sort Performance
We derive the total number of
comparisons by counting the
number of times the inner loop
is executed.
For each execution of the outer
loop,the inner loop is executed length – start times.
The variable length is the size of
the array,Replacing length with
N,the array size,the sum is
derived as…
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 23
Bubble Sort
With the selection sort,we make one exchange at the end
of one pass,
The bubble sort improves the performance by making
more than one exchange during its pass.
By making multiple exchanges,we will be able to move
more elements toward their correct positions using the
same number of comparisons as the selection sort makes.
The key idea of the bubble sort is to make pairwise
comparisons and exchange the positions of the pair if they
are out of order.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 24
One Pass of Bubble Sort
The largest value 90 is at the end of
the list.
0 1 2 3 4 5 6 7 8
23 17 5 90 12 44 38 84 77
17 23 5 90 12 44 38 84 77
17 5 23 90 12 44 38 84 77
17 5 23 12 90 44 38 84 77
17 5 23 12 44 90 38 84 77
17 5 23 12 44 38 90 84 77
17 5 23 12 44 38 84 90 77
17 5 23 12 44 38 84 77 90
exchange
ok
exchange
exchange
exchange
exchange
exchange
exchange
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 25
Bubble Sort Routine
public void bubbleSort( int[] number )
{
int temp,bottom,i;
boolean exchanged = true;
bottom = number.length - 2;
while ( exchanged ) {
exchanged = false;
for (i = 0; i <= bottom; i++) {
if (number[i] > number[i+1]) {
temp = number[i]; //exchange
number[i] = number[i+1];
number[i+1] = temp;
exchanged = true; //exchange is made
}
}
bottom--;
}
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 26
Bubble Sort Performance
In the worst case,the outer
while loop is executed N-1 times
for carrying out N-1 passes.
For each execution of the outer
loop,the inner loop is executed
bottom+1 times,The number of comparisons in each successive
pass is N-1,N-2,…,1,
Summing these will result in the
total number of comparisons.
So the performances of the bubble sort and the
selection sort are approximately equivalent,However,
on the average,the bubble sort performs much better
than the selection sort because it can finish the sorting without doing all N-1 passes,
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 27
Heapsort
Selection and bubble sorts are two fundamental sorting
algorithms that take approximately N2 comparisons to sort
an array of N elements.
One sorting algorithm that improves the performance to
approximately 1.5Nlog2N is called heapsort.
The heapsort algorithm uses a special data structure
called a heap.
A heap structure can be implemented very effectively by
using an array.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 28
Sample Heap
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
root
index
left child
of
44
right child
of
44
Level #
1
2
3
4
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 29
Heap Constraints
A heap must satisfy the following two constraints:
Structural Constraint,Nodes in a heap with N
nodes must occupy the positions numbered 0,
1,...,N-1,
Value Relationship Constraint,A value stored in a
node must be larger than the maximum of the
values stored in its left and right children,
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 30
Nonheaps
Heaps
Structural Constraints
Sample heaps and nonheaps that violate the structural constraints:
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 31
Nonheaps
Heaps
Value Relationship Constraints
Sample heaps and nonheaps that violate the value relationship constraints:
45
25 16
3 1222
45
12 34
11 229
90
35 24
13 1612
45
55 16
3 1258
45
25 33
34 2322
45
25 55
3 1222
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 32
Heapsort Algorithm
How can we use the heap structure to sort N
elements?
Heapsort is carried out in two phases:
Construction Phase,Construct a heap with given N
elements,
Extraction Phase,Pull out the value in the root
successively,creating a new heap with one less
element after each extraction,
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 33
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
0 1 2 3 4 5 6 7 8
90
23
23 > max{84,44}? NO,so swap.
84
23
77 12
77
23
1 }? YES,so stop
Extraction Phase
After each extraction,a heap must be rebuilt with one less element,One sample extraction step:
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
0 1 2 3 4 5 6 7 8
Before After
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 34
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
0 1 2 3 4 5 6 7 8
Rebuild Steps
A sequence of rebuild steps to sort the list.
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
0 1 2 3 4 5 6 7 8
Before
90
84
77
23
84
77
23
17
77
44
38
44
38
5
38
23
17
12
23
17
12
17
12
5
12
5
5
Done
Sorting was completed
after 8 rebuild steps.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 35
Construction Phase
Rebuild steps are applied from position?(N-2)/2? to
position 0.
23
17 5
12 44 3890
84 77
0
1 2
3 4 5 6
7 8
Before
23
17 5
12 44 3890
84 77
0
1 2
3 4 5 6
7 8
(9-2)/2? = 3
44
5
1
90
84
17
0
90
84
77
23
Done
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 36
Heap Implementation
We need to implement the abstract data structure
heap into a concrete data structure.
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
Abstract Heap Structure Concrete Implementation
0 1 2 3 4 5 6 7 8
23173851277448490
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 37
The construct Method
private void construct( )
{
for (int i = (heap.length-2) / 2; i >= 0; i--) {
current = i;
done = false;
while ( !done ) {
if ( current has no children ) {
done = true;
}
else {
if ( current node < larger child ) {
swap the two nodes;
set current points to the larger child;
}
else {
done = true;
}
}
}
}
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 38
The extract Method
private void extract( )
{
for (int size = heap.length-1; size >= 0; size--) {
remove the root node data;
move the last node to the root;
done = false; //rebuild the heap with one less element
while ( !done ) {
if ( current has no children ) {
done = true;
}
else {
if ( current node < larger child ) {
swap the two nodes;
set current points to the larger child;
}
else {
done = true;
}
}
}
}
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 39
Heapsort Performance
The total number of comparisons in the extraction phase
is (N-1)?K where K is the depth of a heap.
We solve for K using the fact that the heap must satisfy
the structural constraint,
122
1
1
KK
i
i
total # nodes in a heap
with depth K
this holds because
of the structural
constraint
1212 1 KK N
)1(l o g 2 NK
Therefore,
NNKN 2l o g)1(
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 40
Heapsort Performance - 2
There are N/2 rebuild steps in the construction phase.
Each rebuild step will take no more than K comparisons.
The total number of comparsions in the construction phase is approximately
NN 2log2
Therefore,the total number of comparisons for both
phases is
NNNNNN 222 l o g5.1l o gl o g2
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 41
Sample Program,Sorting an AddressBook
Problem Statement
Add the sorting capability to the AddressBook class
from Chapter 9,The new AddressBook class will include
a method that sort Person objects in alphabetical order
or in descending order of their ages.
How do we compare Person objects? The
following is invalid:
Person p1 = …;
Person p2 = …;
if ( p1 < p2 ) { … }
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 42
Comparing Person Objects
Modify the Person class to include a variable that tells
which attribute to compare.
class Person
{
…
public static final int NAME = 0;
public static final int AGE = 1;
public static int compareAttribute = NAME; //default
…
public static void setCompareAttribute( int attribute )
{
compareAttribute = attribute;
}
…
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 43
The compareTo Method
To compare Person objects,first set the comparison
attibute and then call the compareTo Method.
Person.setCompareAttribute( Person.NAME );
int compResult = p1.compareTo( p2 );
if (compResult < 0) {
//p1,less than” p2
}
else if (compResult == 0) {
//p1,equals” pw
}
else {
//p2,greater than” p2
}
public int compareTo( Person p )
{ int compResult;
if ( comparisonAttribute == AGE ) {
int p2age = p.getAge();
if ( this.age < p2age ) {
compResult = LESS;
}
…
else { //compare Name
String p2Name = p.getName();
compResult = this.name.
compareTo(p2Name);
}
return compResult;
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 44
The sort Method
public Person[ ] sort ( int attribute )
{
Person[ ] sortedList = new Person[ count ];
Person p1,p2,temp;
//copy references to sortedList; //see figure next slide
for (int i = 0; i < count; i++) {
sortedList[i] = entry[i];
}
//Set the comparison attribute
Person.setCompareAttribute( attribute );
//begin the bubble sort on sortedList
…
}
return sortedList;
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 45
The Use of sortedList in the sort Method
The End
0 1 2 3
entry
15 11 10 13
0 1 2 3
sortedList
19…
References in entry are copied
to sortedList before sorting.
0 1 2 3
15 11 10 13
0 1 2 3
sortedList
19…
entry
Sort and return
sortedList.
Chapter 10
Sorting and Searching
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 2
Chapter 10 Objectives
After you have read and studied this chapter,you
should be able to
Perform linear and binary search algorithms on small
arrays.
Determine whether a linear or binary search is more
effective for a given situation.
Perform selection and bubble sort algorithms.
Describe the heapsort algorithm and show how its
performance is superior to the other two algorithms.
Apply basic sorting algorithms to sort an array of objects.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 3
Searching
When we maintain a collection of data,one of the operations we need is a search routine to locate desired data quickly.
We will use an array of integers to present searching algorithms,Here’s the problem statement:
Given a value X,return the index of X in the array,if such X
exists,Otherwise,return NOT_FOUND (-1),We assume there
are no duplicate entries in the array.
We will count the number of comparisons the algorithms make to analyze their performance,The ideal searching algorithm will
make the least possible number of comparisons to locate the desired data.
Two separate performance analyses are normally done,one for successful search and another for unsuccessful search.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 4
Search Result
number
23 17 5 90 12 44 38
0 1 2 3 4 5 6 7 8
84 77
Unsuccessful Search:
Successful Search:
NOT_FOUNDsearch( 45 )
search( 12 ) 4
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 5
Linear Search
Search the array from the first to the last position in linear
progression,
public int linearSearch ( int[] number,int searchValue )
{
int loc = 0;
while ( loc < number.length && number[loc] != searchValue ) {
loc++;
}
if ( loc == number.length) { //Not found
return NOT_FOUND;
}
else {
return loc; //Found,return the position
}
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 6
Linear Search Performance
We analyze the successful and unsuccessful searches
separately,
We count how many times the search value is
compared against the array elements.
Successful Search
Best Case – 1 comparison
Worst Case – N comparisons (N – array size)
Unsuccessful Search
Best Case =
Worst Case – N comparisons
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 7
Binary Search
If the array is sorted,then we can apply the binary search
technique,
number
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
The basic idea is straightforward,First search the value in
the middle position,If X is less than this value,then search
the middle of the left half next,If X is greater than this
value,then search the middle of the right half next,Continue in this manner.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 8
Sequence of Successful Search - 1
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 44 )low high mid
0 8#1
highlow
2 h ig hlo wm id
38 < 44 low = mid+1 = 5
mid
4
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 9
Sequence of Successful Search - 2
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 44 )low high mid
0 8#1
2 h ig hlo wm id
44 < 77high = mid-1=5
4
mid
6
highlow
5 8#2
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 10
Sequence of Successful Search - 3
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 44 )low high mid
0 8#1
2 h ig hlo wm id
44 == 44
4
5 8#2 6
highlow
5 5#3
mid
5
Successful Search!!
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 11
Sequence of Unsuccessful Search - 1
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 45 )low high mid
0 8#1
highlow
2 h ig hlo wm id
38 < 45 low = mid+1 = 5
mid
4
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 12
Sequence of Unsuccessful Search - 2
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 45 )low high mid
0 8#1
2 h ig hlo wm id
45 < 77high = mid-1=5
4
mid
6
highlow
5 8#2
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 13
Sequence of Unsuccessful Search - 3
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 45 )low high mid
0 8#1
2 h ig hlo wm id
44 < 45
4
5 8#2 6
highlow
5 5#3
mid
5
low = mid+1 = 6
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 14
Sequence of Unsuccessful Search - 4
5 12 17 23 38 44 77
0 1 2 3 4 5 6 7 8
84 90
search( 45 )low high mid
0 8#1
2 h ig hlo wm id
4
5 8#2 6
5 5#3 5
high low
6 5#4
Unsuccessful Search
low > highno more elements to search
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 15
Binary Search Routine
public int binarySearch ( int[] number,int searchValue )
{
int low = 0,
high = number.length - 1,
mid = (low + high) / 2;
while ( low <= high && number[mid] != searchValue ) {
if (number[mid] < searchValue) {
low = mid + 1;
}
else { //number[mid] > searchValue
high = mid - 1;
}
mid = (low + high) / 2; //integer division will truncate
}
if ( low > high) {
mid = NOT_FOUND;
}
return mid;
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 16
Binary Search Performance
Successful Search
Best Case – 1 comparison
Worst Case – log2N comparisons
Unsuccessful Search
Best Case =
Worst Case – log2N comparisons
Since the portion of an array to search is cut into half after every comparison,we compute how many times
the array can be divided into halves,
After K comparisons,there will be N/2K elements in the list,We solve for K when N/2K = 1,deriving K =
log2N.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 17
Comparing N and log2N Performance
Array Size Linear – N Binary – log2N
10 10 4
50 50 6
100 100 7
500 500 9
1000 1000 10
2000 2000 11
3000 3000 12
4000 4000 12
5000 5000 13
6000 6000 13
7000 7000 13
8000 8000 13
9000 9000 14
10000 10000 14
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 18
Sorting
When we maintain a collection of data,many applications call for rearranging the data in certain order,e.g,arranging Person
information in ascending order of age.
We will use an array of integers to present sorting algorithms,Here’s the problem statement:
Given an array of N integer values,arrange the values into
ascending order.
We will count the number of comparisons the algorithms make to analyze their performance,The ideal sorting algorithm will make
the least possible number of comparisons to arrange data in a designated order.
We will compare different sorting algorithms by analyzing their worst-case performance.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 19
Selection Sort
1,Find the smallest element
in the list.
0 1 2 3 4 5 6 7 8
23 17 5 90 12 44 38 84 77
minfirst
exchange
0 1 2 3 4 5 6 7 8
5 17 23 90 12 44 38 84 77
sorted unsorted
This is the result of one pass.
2,Exchange the element in
the first position and the
smallest element,Now the
smallest element is in the first position,
3,Repeat Step 1 and 2 with
the list having one less
element (i.e.,the smallest
element is discarded from further processing).
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 20
Selection Sort Passes
0 1 2 3 4 5 6 7 8
5 17 23 90 12 44 38 84 77
sorted
5 12 23 90 17 44 38 84 772
5 12 17 90 23 44 38 84 773
5 12 17 23 38 44 77 84 907
5 12 17 23 38 44 77 84 908
1
Pass #
Result AFTER one
pass is completed.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 21
Selection Sort Routine
public void selectionSort( int[] number )
{
int startIndex,minIndex,length,temp;
length = number.length;
for (startIndex = 0; startIndex <= length-2; startIndex++){
//each iteration of the for loop is one pass
minIndex = startIndex;
//find the smallest in this pass at position minIndex
for (i = startIndex+1; i <= length-1; i++) {
if (number[i] < number[minIndex]) minIndex = i;
}
//exchange number[startIndex] and number[minIndex]
temp = number[startIndex];
number[startIndex] = number[minIndex];
number[minIndex] = temp;
}
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 22
Selection Sort Performance
We derive the total number of
comparisons by counting the
number of times the inner loop
is executed.
For each execution of the outer
loop,the inner loop is executed length – start times.
The variable length is the size of
the array,Replacing length with
N,the array size,the sum is
derived as…
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 23
Bubble Sort
With the selection sort,we make one exchange at the end
of one pass,
The bubble sort improves the performance by making
more than one exchange during its pass.
By making multiple exchanges,we will be able to move
more elements toward their correct positions using the
same number of comparisons as the selection sort makes.
The key idea of the bubble sort is to make pairwise
comparisons and exchange the positions of the pair if they
are out of order.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 24
One Pass of Bubble Sort
The largest value 90 is at the end of
the list.
0 1 2 3 4 5 6 7 8
23 17 5 90 12 44 38 84 77
17 23 5 90 12 44 38 84 77
17 5 23 90 12 44 38 84 77
17 5 23 12 90 44 38 84 77
17 5 23 12 44 90 38 84 77
17 5 23 12 44 38 90 84 77
17 5 23 12 44 38 84 90 77
17 5 23 12 44 38 84 77 90
exchange
ok
exchange
exchange
exchange
exchange
exchange
exchange
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 25
Bubble Sort Routine
public void bubbleSort( int[] number )
{
int temp,bottom,i;
boolean exchanged = true;
bottom = number.length - 2;
while ( exchanged ) {
exchanged = false;
for (i = 0; i <= bottom; i++) {
if (number[i] > number[i+1]) {
temp = number[i]; //exchange
number[i] = number[i+1];
number[i+1] = temp;
exchanged = true; //exchange is made
}
}
bottom--;
}
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 26
Bubble Sort Performance
In the worst case,the outer
while loop is executed N-1 times
for carrying out N-1 passes.
For each execution of the outer
loop,the inner loop is executed
bottom+1 times,The number of comparisons in each successive
pass is N-1,N-2,…,1,
Summing these will result in the
total number of comparisons.
So the performances of the bubble sort and the
selection sort are approximately equivalent,However,
on the average,the bubble sort performs much better
than the selection sort because it can finish the sorting without doing all N-1 passes,
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 27
Heapsort
Selection and bubble sorts are two fundamental sorting
algorithms that take approximately N2 comparisons to sort
an array of N elements.
One sorting algorithm that improves the performance to
approximately 1.5Nlog2N is called heapsort.
The heapsort algorithm uses a special data structure
called a heap.
A heap structure can be implemented very effectively by
using an array.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 28
Sample Heap
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
root
index
left child
of
44
right child
of
44
Level #
1
2
3
4
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 29
Heap Constraints
A heap must satisfy the following two constraints:
Structural Constraint,Nodes in a heap with N
nodes must occupy the positions numbered 0,
1,...,N-1,
Value Relationship Constraint,A value stored in a
node must be larger than the maximum of the
values stored in its left and right children,
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 30
Nonheaps
Heaps
Structural Constraints
Sample heaps and nonheaps that violate the structural constraints:
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 31
Nonheaps
Heaps
Value Relationship Constraints
Sample heaps and nonheaps that violate the value relationship constraints:
45
25 16
3 1222
45
12 34
11 229
90
35 24
13 1612
45
55 16
3 1258
45
25 33
34 2322
45
25 55
3 1222
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 32
Heapsort Algorithm
How can we use the heap structure to sort N
elements?
Heapsort is carried out in two phases:
Construction Phase,Construct a heap with given N
elements,
Extraction Phase,Pull out the value in the root
successively,creating a new heap with one less
element after each extraction,
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 33
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
0 1 2 3 4 5 6 7 8
90
23
23 > max{84,44}? NO,so swap.
84
23
77 12
77
23
1 }? YES,so stop
Extraction Phase
After each extraction,a heap must be rebuilt with one less element,One sample extraction step:
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
0 1 2 3 4 5 6 7 8
Before After
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 34
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
0 1 2 3 4 5 6 7 8
Rebuild Steps
A sequence of rebuild steps to sort the list.
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
0 1 2 3 4 5 6 7 8
Before
90
84
77
23
84
77
23
17
77
44
38
44
38
5
38
23
17
12
23
17
12
17
12
5
12
5
5
Done
Sorting was completed
after 8 rebuild steps.
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 35
Construction Phase
Rebuild steps are applied from position?(N-2)/2? to
position 0.
23
17 5
12 44 3890
84 77
0
1 2
3 4 5 6
7 8
Before
23
17 5
12 44 3890
84 77
0
1 2
3 4 5 6
7 8
(9-2)/2? = 3
44
5
1
90
84
17
0
90
84
77
23
Done
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 36
Heap Implementation
We need to implement the abstract data structure
heap into a concrete data structure.
90
84 44
12 5 3877
17 23
0
1 2
3 4 5 6
7 8
Abstract Heap Structure Concrete Implementation
0 1 2 3 4 5 6 7 8
23173851277448490
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 37
The construct Method
private void construct( )
{
for (int i = (heap.length-2) / 2; i >= 0; i--) {
current = i;
done = false;
while ( !done ) {
if ( current has no children ) {
done = true;
}
else {
if ( current node < larger child ) {
swap the two nodes;
set current points to the larger child;
}
else {
done = true;
}
}
}
}
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 38
The extract Method
private void extract( )
{
for (int size = heap.length-1; size >= 0; size--) {
remove the root node data;
move the last node to the root;
done = false; //rebuild the heap with one less element
while ( !done ) {
if ( current has no children ) {
done = true;
}
else {
if ( current node < larger child ) {
swap the two nodes;
set current points to the larger child;
}
else {
done = true;
}
}
}
}
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 39
Heapsort Performance
The total number of comparisons in the extraction phase
is (N-1)?K where K is the depth of a heap.
We solve for K using the fact that the heap must satisfy
the structural constraint,
122
1
1
KK
i
i
total # nodes in a heap
with depth K
this holds because
of the structural
constraint
1212 1 KK N
)1(l o g 2 NK
Therefore,
NNKN 2l o g)1(
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 40
Heapsort Performance - 2
There are N/2 rebuild steps in the construction phase.
Each rebuild step will take no more than K comparisons.
The total number of comparsions in the construction phase is approximately
NN 2log2
Therefore,the total number of comparisons for both
phases is
NNNNNN 222 l o g5.1l o gl o g2
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 41
Sample Program,Sorting an AddressBook
Problem Statement
Add the sorting capability to the AddressBook class
from Chapter 9,The new AddressBook class will include
a method that sort Person objects in alphabetical order
or in descending order of their ages.
How do we compare Person objects? The
following is invalid:
Person p1 = …;
Person p2 = …;
if ( p1 < p2 ) { … }
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 42
Comparing Person Objects
Modify the Person class to include a variable that tells
which attribute to compare.
class Person
{
…
public static final int NAME = 0;
public static final int AGE = 1;
public static int compareAttribute = NAME; //default
…
public static void setCompareAttribute( int attribute )
{
compareAttribute = attribute;
}
…
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 43
The compareTo Method
To compare Person objects,first set the comparison
attibute and then call the compareTo Method.
Person.setCompareAttribute( Person.NAME );
int compResult = p1.compareTo( p2 );
if (compResult < 0) {
//p1,less than” p2
}
else if (compResult == 0) {
//p1,equals” pw
}
else {
//p2,greater than” p2
}
public int compareTo( Person p )
{ int compResult;
if ( comparisonAttribute == AGE ) {
int p2age = p.getAge();
if ( this.age < p2age ) {
compResult = LESS;
}
…
else { //compare Name
String p2Name = p.getName();
compResult = this.name.
compareTo(p2Name);
}
return compResult;
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 44
The sort Method
public Person[ ] sort ( int attribute )
{
Person[ ] sortedList = new Person[ count ];
Person p1,p2,temp;
//copy references to sortedList; //see figure next slide
for (int i = 0; i < count; i++) {
sortedList[i] = entry[i];
}
//Set the comparison attribute
Person.setCompareAttribute( attribute );
//begin the bubble sort on sortedList
…
}
return sortedList;
}
2000 McGraw-Hill Introduction to Object-Oriented Programming with Java--Wu Chapter 10 - 45
The Use of sortedList in the sort Method
The End
0 1 2 3
entry
15 11 10 13
0 1 2 3
sortedList
19…
References in entry are copied
to sortedList before sorting.
0 1 2 3
15 11 10 13
0 1 2 3
sortedList
19…
entry
Sort and return
sortedList.
