Transcript Northside Middle School

Java Methods
A & AB
Object-Oriented Programming
and Data Structures
Maria Litvin ● Gary Litvin
13ACEHRPT
Searching and Sorting
Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved.
APCS Examination Alert
Recursion is an important topic with frequent questions on
both the A and the AB APCS Examination.
The A Examination requires that a student can understand
and evaluate recursive methods.
The A Examination does not require that students
generate free response recursive solutions.
The AB Examination does require that students generate
some free response recursive solutions.
13-2
Recursion Definition
Recursion is the computer programming
process, whereby a method calls itself.
13-3
Recursion Requires an Exit
The original BASIC programming language
makes frequent use of the GOTO control
structure.
GOTO is very much frowned upon by computer
scientists who do not like to see unconditional
jumps in a program.
100 REM Program that counts integers starting at 0
110 K = 0
120 K = K + 1
130 PRINT K
140 GOTO 120
13-4
// Java1901.java
// This program demonstrates recursion without an exit.
// The recursive calls will continue until the program aborts
// with an error message.
public class Java1901
{
static int k = 0;
public static void main(String args[])
{
count();
}
public static void count()
{
k++;
System.out.print(k + " ");
count();
}
}
13-5
// Java1902.java
// This program demonstrates how to add an exit or base case to control recursive calls
public class Java1902
{
static int k = 0;
public static void main(String args[])
{
System.out.println("CALLING ITERATIVE COUNT METHOD");
count1();
System.out.println("\n\nCALLING RECURSIVE COUNT METHOD");
count2();
System.out.println("\n\nEXECUTION TERMINATED");
}
public static void count1()
/***** ITERATIVE COUNT *****/
{
for (int k = 1; k <= 100; k++)
System.out.print(k + " ");
}
public static void count2()
/***** RECURSIVE COUNT *****/
{
k++;
System.out.print(k + " ");
if (k < 100) count2();
}
13-6
}
Important Recursion Rule
All recursive methods must have an
exit that stops the recursive
process.
The special case or condition that
stops the recursive calls is called
the base case.
13-7
// Java1903.java
This program demonstrates the <Skip> method.
public class Java1903
{
public static void main(String args[])
{
System.out.println("CALLING ITERATIVE SKIP METHOD");
skip1(4);
System.out.println("CALLING RECURSIVE SKIP METHOD");
skip2(3);
System.out.println("EXECUTION TERMINATED");
}
public static void skip1(int n)
/***** ITERATIVE SKIP *****/
{
for (int k = 1; k <= n; k++)
System.out.println();
}
public static void skip2(int n)
/***** RECURSIVE SKIP *****/
{
if ( n > 0)
{
System.out.println();
skip2(n-1);
}
}
}
13-8
// Java1904.java
// This program demonstrates the <count(a,b)> method, which displays
// consecutive integers from a to b.
public class Java1904
{
public static void main(String args[])
{
System.out.println("CALLING ITERATIVE COUNT METHOD");
count1(10,25);
System.out.println("\n\nCALLING RECURSIVE COUNT METHOD");
count2(26,40);
System.out.println("\n\nEXECUTION TERMINATED");
}
public static void count1(int a, int b)
/***** ITERATIVE COUNT *****/
{
for (int k = a; k <= b; k++)
System.out.print(k + " ");
}
public static void count2(int a, int b)
/***** RECURSIVE COUNT *****/
{
if (a <= b)
{
System.out.print(a + " ");
count2(a+1,b);
}
}
}
13-9
// Java1905.java
// This program compares the difference between "post-recursive" calls and "pre-recursive" calls.
public class Java1905
{
public static void main(String args[])
{
System.out.println("CALLING POST-RECURSIVE COUNT METHOD");
count1(100,200);
System.out.println("\n\nCALLING PRE-RECURSIVE COUNT METHOD");
count2(100,200);
System.out.println("\n\nEXECUTION TERMINATED");
}
public static void count1(int a, int b)
/**** POST-RECURSIVE COUNT ****/
{
if (a <= b)
{
System.out.print(a + " ");
count1(a+1,b);
}
}
public static void count2(int a, int b)
/**** PRE-RECURSIVE COUNT ****/
{
if (a <= b)
{
count2(a+1,b);
System.out.print(a + " ");
}
}
}
13-10
The Internal Stack & Recursion
Java has a special internal data structure, called a stack that is
hidden from the programmer.
A stack is a data structure that will only access data from one
end, usually called the top, in such a manner that it behaves
like a LIFO.
Data is accessed Last In, First Out.
Program execution sequence is handled by something called an
Index Pointer.
The Index Pointer, or IP for short, contains the next memory
address of the line to be executed.
NOTE: An IP, which points to a memory address in a computer is in
no way related to an Internet Protocol (IP) Address on the internet.
13-11
// Java1906.java
// This program demonstrates how recursion can display output in reverse order.
public class Java1906
{
public static void main(String args[])
{
System.out.println("\n\nCALLING PRE-RECURSIVE COUNT METHOD");
count2(100,105);
System.out.println("\n\nEXECUTION TERMINATED");
}
public static void count2(int a, int b)
{
if (a <= b)
{
System.out.println("Interrupting method completion; pushing " + a
+ " on stack.");
count2(a+1,b);
System.out.println("Returning to complete method; popping " + a
+ " from stack.");
System.out.println("Displaying popped value " + a);
}
}
}
13-12
Fundamental Recursion Concepts
All recursive methods require an
that stops the recursive process.
or base case
The stack controls recursion, since it controls the
execution sequence of methods, and stores local
method information.
Every method call requires the completion of the
called method, even if the execution sequence is
interrupted by another recursive method call.
Incomplete recursive calls result in a LIFO execution
sequence.
13-13
Recursion Basics
Guidelines for Writing Recursive Methods


A recursive method must have a well-defined termination or
stopping state.
For the factorial method, this was expressed in the lines:
if (n == 1)
return 1;


The recursive step, in which the method calls itself, must
eventually lead to the stopping state.
For the factorial method, the recursive step was expressed in
the lines:
else
return n * factorial(n - 1);
13-14
// Java1907.java
This program demonstrates the <sum> method.
// It also demonstrates recursion with return methods.
public class Java1907
{
public static void main(String args[])
{
System.out.println("CALLING ITERATIVE SUM METHOD");
System.out.println("1 + 2 + 3 + 4 + 5 + 6 = " + sum1(6));
System.out.println("\n\nCALLING RECURSIVE SUM METHOD");
System.out.println("1 + 2 + ... + 99 + 100 = " + sum2(100));
System.out.println("\n\nEXECUTION TERMINATED");
}
public static int sum1(int n)
/*****
ITERATIVEOutput
SUM *****/
Java1907.java
{
int sum = 0;
CALLING ITERATIVE SUM METHOD
for (int k = 1; k <= n; k++)
1 + 2 + 3 + 4 + 5 + 6
= 21
sum += k;
return sum;
}
public static int sum2(int n)
/***** RECURSIVE SUM *****/
CALLING RECURSIVE SUM METHOD
{
1 + 2 + ... + 99 + 100 = 5050
if (n == 0)
return 0;
else
return n + sum2(n-1);
EXECUTION TERMINATED
}
}
13-15
Stepping Through
public static int sum2(int n)
{
if (n == 0)
return 0;
else
return n +sum2(n-1);
}
CALL #
n
What 1is sum2(4)? 4
2
3
4
5
3
2
1
0
Method sum2 returns
4 + Sum2(3)
3 + Sum2(2)
2 + Sum2(1)
1 + Sum2(0)
0
sum2(4) = 4 + 3 + 2 + 1 + 0 = 10
13-16
// Java1908.java
// This program demonstrates the <fact> method.
public class Java1908
{
public static void main(String args[])
{
System.out.println("CALLING ITERATIVE FACTORIAL METHOD");
System.out.println("6 Factorial = " + fact1(6));
System.out.println("\n\nCALLING RECURSIVE FACTORIAL METHOD");
System.out.println("7 Factorial = " + fact2(7));
System.out.println("\n\nEXECUTION TERMINATED");
}
public static int fact1(int n)
/*****
ITERATIVEOutput
FACT *****/
Java1908.java
{
int temp = 1;
CALLING ITERATIVE FACTORIAL METHOD
for (int k = n; k > 0; k--)
6 Factorial = 720
temp *= k;
return temp;
}
CALLING
RECURSIVE
METHOD
public static int fact2(int n)
/*****
RECURSIVE
FACTFACTORIAL
*****/
{
7 Factorial = 5040
if (n == 0)
return 1;
else
EXECUTION TERMINATED
return n * fact2(n-1);
}
Doesn’t this look like the mathematical definition of factorial?13-17
}
Stepping Through
public static int fact2(int n)
{
if (n == 0)
return 1;
else
return n * fact2(n-1);
}
CALL #
n
Method fact2 returns
1 fact2(6)?6
What is
6 * Fact2(5)
2
5
5 * Fact2(4)
3
4
4 * Fact2(3)
4
3
3 * Fact2(2)
5
2
2 * Fact2(1)
6
1
1 * Fact2(0)
7
0
1
sum2(6) = 6 * 5 * 4 * 3 * 2 * 1 * 1 = 720
13-18
// Java1909.java
This program demonstrates the <gcf> method.
public class Java1909
{
public static void main(String args[])
{
System.out.println("CALLING ITERATIVE GCF METHOD");
System.out.println("GCF of 120 and 108 is " + gcf1(120,108));
System.out.println("\n\nCALLING RECURSIVE GCF METHOD");
System.out.println("GCF of 360 and 200 is " + gcf2(360,200));
System.out.println("\n\nEXECUTION TERMINATED");
}
public static int gcf1(int n1, int n2)
/*****
ITERATIVEOutput
GCF *****/
Java1909.java
{
int temp = 0; int rem = 0;
CALLING ITERATIVE GCF METHOD
do
GCF of 120 and 108 is 12
{
rem = n1 % n2;
if (rem == 0) temp = n2;
CALLING RECURSIVE GCF METHOD
else
{
GCF of 360 and 200 is 40
n1 = n2;
n2 = rem;
}
EXECUTION TERMINATED
}
while (rem != 0);
return temp;
Recursive gcf2 is shown on the next slide.
}
13-19
Stepping Through the Recursive
Process with gcf2(360,400)
public static int gcf2(int n1, int n2)
{
int rem = n1 % n2;
if (rem == 0)
return n2;
else
return gcf2(n2,rem);
}
CALL#
n1
n2
rem
Method gcf2 returns
1
360
400
360
gcf2(400,360)
2
400
360
40
gcf2(360,40)
3
360
40
0
40
gcf2(360,400) = 40
13-20
APCS Examination Alert
Evaluating recursive method, like the examples
that follow will be required for both the A and AB
multiple choice part of the examination.
Few students are comfortable with this type of
problem at the first introduction.
Most students achieve excellent evaluation skills
with repeated practice.
13-21
Exercise 01
Determine m1(5)
public int m1(int n)
{
if (n == 1)
return 25;
else
return m1(n-1);
}
25 is returned
no matter what N is
as long as N >= 1
CALL #
n
Method m1 returns
1
2
3
4
5
5
4
3
2
1
m1(4)
m1(3)
m1(2)
m1(1)
25
m1(5) == 25
13-22
Exercise 02
Determine m2(5)
public int m2(int n)
{
if (n == 1)
return 25;
else
return m2(n+1);
}
It is not possible for N
to ever reach 1.
The function recursively
calls itself until the
computer's stack runs
out of memory.
CALL #
n
Method m2 returns
1
2
3
4
5
6
7
8
m2(6)
m2(7)
m2(8)
m2(9)
Error results because the base case cannot be reached.
13-23
Exercise 03
Determine m3(5).
public int m3(int n)
{
if (n == 1)
return 25;
else
return n + m3(n-1);
}
CALL #
1
2
3
4
5
n
Method m3 returns
5
4
3
2
1
5 + m3(4)
4 + m3(3)
3 + m3(2)
2 + m3(1)
25
m3(5) == 5 + 5 + 3 + 2 + 25 == 39
13-24
Exercise 04
Determine m4(1).
public int m4(int n)
{
if (n == 5)
return 0;
else
return n + m4(n+1);
}
CALL #
1
2
3
4
5
n
Method m4 returns
1
2
3
4
5
1 + m4(2)
2 + m4(3)
3 + m4(4)
4 + m4(5)
0
m4(1) == 1 + 2 + 3 + 4 + 0 = = 10
13-25
Exercise
Exercise
05 05
Determine
Determine
m5(6)
m5(6)
== 38 .
public int m5(int n)
{
if (n == 1 || n == 0)
return 0;
else
return n + m5(n-1) + m5(n-2);
}
CALL #
n
Method m5 returns
1
2
3
4
5
6
6
5
4
3
2
1
6 + m5(5) + m5(4)
5 + m5(4) + m5(3)
4 + m5(3) + m5(2)
3 + m5(2) + m5(1)
2 + m5(1) + m5(0)
0
What?
m5(6) == 6 + 5 + 4 + 3 +2 + 0 == 20 ???
13-26
Exercise 05 Explained
Since anything less than 2
will return 0, we only add
the numbers that are 2 or
over. Now we have
6+5+4+4+3+3+2+3
+ 2 + 2 + 2 + 2 = 38
13-27
Exercise 06
Determine m6(5)
public int m6(int n)
{
if (n == 1)
return 1;
else
return n * m6(n-1);
}
CALL #
1
2
3
4
5
This is a recursive
factorial function.
n
Method m6 returns
5
4
3
2
1
5 * m6(4)
4 * m6(3)
3 * m6(2)
2 * m6(1)
1
m6(5) == 1 * 2 * 3 * 4 * 5 == 120
13-28
Exercise 07
Determine m7(5,6)
public int m7(int a, int b)
{
if (a == 0)
return 0;
else
return b + m7(a-1,b);
}
CALL #
1
2
3
4
5
6
a
5
4
3
2
1
0
b
6
6
6
6
6
6
This is a recursive way to
multiply 2 numbers.
(Not that you would ever
want to do it this way!)
Method m7 returns
6 + m7(4,6)
6 + m7(3,6)
6 + m7(2,6)
6 + m7(1,6)
6 + m7(0,6)
0
m7(5,6) = 6 + 6 + 6 + 6 + 6 + 0 = 30
13-29
Exercise 08
Determine m8(4,3)
public int m8(int a, int b)
{
if (a == 0)
return 1;
else
return b * m8(a-1,b);
}
CALL #
1
2
3
4
5
a
4
3
2
1
0
b
3
3
3
3
3
This is a recursive
power function.
It computes BA.
Method m8 returns
3 * m8(3,3)
3 * m8(2,3)
3 * m8(1,3)
3 * m8(0,3)
1
m8(4,3) == 3 * 3 * 3 * 3 * 1 == 81
13-30
Exercise 09
Determine m9(4,3)
public int m9(int a, int b)
{
if (b == 0)
return 1;
else
return a * m9(a,b-1);
}
CALL #
1
2
3
4
This is also a
recursive power
function.
But, it computes AB.
a
b
Method m9 returns
4
4
4
4
3
2
1
0
4 * m9(4,2)
4 * m9(4,1)
4 * m9(4,0)
1
m9(4,3) == 4 * 4 * 4 * 1 == 64
13-31
Exercise 10
Determine m10(7,3)
public int m10(int a, int b)
{
if (a < b)
return 5;
else
return b + m10(a-1,b+1);
}
CALL #
1
2
3
4
a
b
Method m10 returns
7
6
5
4
3
4
5
6
3 + m10(6,4)
4 + m10(5,5)
5 + m10(4,6)
5
m10(7,3) == 3 + 4 + 5 + 5 == 17
13-32
Towers of Hanoi
13-33
Multiple Recursive Calls
and The Tower of Hanoi
Towers of Hanoi at the Start of the 5-Disk Problem
1
2
3
4
5
Peg A
Peg B
Peg C
13-34
Multiple Recursive Calls
and The Tower of Hanoi
Towers of Hanoi at the End of the 5-Disk Problem
1
2
3
4
5
Peg A
Peg B
Peg C
13-35
The Trivial One-Disk Problem
Let us look at a variety of problems, starting with the simplest
possible situation. Suppose that you only need to move one
disk from peg A to peg C. Would that be any kind of problem?
1
Peg A
Peg B
Peg C
13-36
The Trivial One-Disk Problem
How do we solve the 1-Disk problem?
In exactly one step that be described with the single statement:
Move Disk1 from Peg A to Peg C
1
Peg A
Peg B
Peg C
13-37
The Easy Two-Disk Problem
Start
1
2
Peg A
Peg B
Peg C
13-38
The Easy Two-Disk Problem
Step 1
2
1
Peg A
Peg B
Peg C
13-39
The Easy Two-Disk Problem
Step 2
Peg A
1
2
Peg B
Peg C
13-40
The Easy Two-Disk Problem
Step 3 - Finished
1
2
Peg A
Peg B
Peg C
13-41
Tower of Hanoi Formula
There is a pattern in the number of minimum
moves to solve a given Tower of Hanoi
problem.
With n the number of disks to be moved, the
formula below computes the number or
required moves.
n
2
-1
13-42
Tower of Hanoi
General Solution
Move n-1 disks from Source Peg to Auxiliary Peg
Move the nth disk from Source Peg to Destination Peg
Move n-1 disks from Auxiliary Peg to Destination Peg
13-43
Tower of Hanoi Formula
Towers of Hanoi at Start of N-Disk Problem
1
2
N-2
N-1
N
Peg A
Peg B
Peg C
13-44
Tower of Hanoi Formula
Move N-1 Disks from Peg A to Peg B
1
2
N-2
N
N-1
Peg A
Peg B
Peg C
13-45
Tower of Hanoi Formula
Move Nth Disk from Peg A to Peg C
1
2
N-2
Peg A
N-1
N
Peg B
Peg C
13-46
Tower of Hanoi Formula
Move N-1 Disks from Peg B to Peg C
1
2
N-2
N-1
N
Peg A
Peg B
Peg C
13-47
Why Recursion?
Recursion is preferred over iteration
when it is easier to write program code
recursively.
13-48
Comparing Objects in Java
• boolean result = obj1.equals(obj2);
• int diff = obj1.compareTo(obj2);
• int diff = c.compare(obj1, obj2);
13-49
obj1.equals(obj2)
• The boolean method equals comes from the
class Object:
public boolean equals(Object other)
{ ... }
• Object’s equals is not very useful: compares
addresses of objects
• Programmers often override equals in their
classes
13-50
obj1.equals(obj2) (cont’d)
public class Pet
{
Or:
private String name;
if (other instanceof Pet)
...
public boolean equals (Object other)
{
if (other != null)
return name.equals(((Pet)other).name);
else
instanceof
return false;
is a boolean
}
operator in
}
Java
13-51
obj1.equals(obj2) (cont’d)
• equals is called polymorphically from library
methods, such as ArrayList’s contains or
indexOf  that is why we have to properly
override Object’s equals.
• The equals method is properly defined in
String, Integer, Double, etc.
13-52
obj1.compareTo(obj2)
• compareTo is an abstract method defined
in the java.util.Comparable<T> interface:
public int compareTo (T other);
• Returns a positive integer if obj1 is
T is the type
parameter
“greater than” obj2, a negative integer if
obj1 is “less than” obj2, zero if they are
“equal.”
Sort of like obj1 - obj2
13-53
obj1.compareTo(obj2) (cont’d)
public class Pet implements Comparable<Pet>
{
equals is not
private String name;
required by
...
Comparable,
public int compareTo(Pet other)
but it is a good
{
idea to provide
return name.compareTo(other.name);
it and make it
}
agree with
compareTo
public boolean equals(Object other)
{
return other instanceof Pet &&
compareTo((Pet)other) == 0;
}
}
13-54
obj1.compareTo(obj2) (cont’d)
• compareTo is called polymorphically from library
methods, such as Arrays.binarySearch(Object[ ]
arr).
• Objects of classes that implement Comparable are
called “comparable” (pronounced com-'parable).
• Strings, Integers, Doubles are comparable.
13-55
obj1.compareTo(obj2) (cont’d)
«interface»
Comparable<String>
«interface»
Comparable<Integer>
«interface»
Comparable<Double>
String
Integer
Double
compareTo is
based on
lexicographical
order
compareTo is
based on
numerical values
13-56
compare(obj1, obj2)
• compare is an abstract method defined in
the java.util.Comparator<T> interface:
T is the type
parameter
public intacompare
obj1, T obj2);
• Returns
positive(Tinteger
if obj1 is
“greater than” obj2, a negative integer if
obj1 is “less than” obj2, zero if they are
“equal.”
Sort of like obj1 - obj2
13-57
compare (obj1, obj2) (cont’d)
public class PetComparatorByName
implements Comparator<Pet>
{
...
public int compare (Pet pet1, Pet pet2)
{
return pet1.getName().
compareTo(pet2.getName());
}
}
13-58
compare(obj1, obj2) (cont’d)
• A programmer can define different
comparators to be used in different
situations.
• compare is called from library methods,
such as
Arrays.sort(T [ ] arr, Comparator<T> c)
(or from your own methods) that take a
comparator object as a parameter.
13-59
Sequential Search
• Scans the list comparing the target value to
each element.
Dan
0
Fay
1
Cal
2
Ben
3
Guy
4
Amy
5
Amy?
Amy?
Amy?
Amy?
Amy?
Amy!
Eve
6
13-60
Sequential Search (cont’d)
public int sequentialSearch(Object [ ] arr, Object value)
{
for (int i = 0; i < arr.length ; i++)
{
if (value.equals(arr [i]))
return i;
}
return -1;
}
For primitive data types it is
if (value == arr [ i ])
13-61
Sequential Search (cont’d)
• The average number of comparisons (assuming
the target value is equal to one of the elements of
the array, randomly chosen) is about n / 2 (where
n = arr.length).
• Worst case: n comparisons.
• Also n comparisons are needed to establish that
the target value is not in the array.
• We say that this is an O(n) (order of n) algorithm.
13-62
11.3 Binary Search

If we know in advance that a list of numbers is
in ascending order, we can quickly zero in on
the search value or determine that it is absent
using the binary search algorithm.

We shall show that this algorithm is O(log n).
13-63
Binary Search
• The elements of the list must be arranged
in ascending (or descending) order.
• The target value is always compared with
the middle element of the remaining
search range.
• We must have random access to the
elements of the list (an array or ArrayList
are OK).
13-64
Binary Search (cont’d)
Amy
0
Ben
1
Cal
2
Dan
3
Eve
4
Fay
5
Guy
6
Eve
4
Fay
5
Guy
6
Eve?
Amy
0
Ben
1
Cal
2
Dan
3
Eve?
Amy
0
Ben
1
Cal
2
Dan
3
Eve
4
Fay
5
Guy
6
Eve!
13-65
Binary Search (cont’d)
• Recursive implementation:
public int binarySearch (int [ ] arr, int value, int left, int right)
{
if (right < left)
return -1;
// Not found
int middle = (left + right) / 2;
if (value == arr [middle] )
return middle;
else if (value < arr[middle])
return binarySearch (arr, value, left, middle - 1);
else // if ( value > arr[middle])
return binarySearch (arr, value, middle + 1, right);
}
13-66
Binary Search (cont’d)
• Iterative implementation:
public int binarySearch (int [ ] arr, int value, int left, int right)
{
while (left <= right)
{
int middle = (left + right) / 2;
if ( value == arr [middle] )
return middle;
else if ( value < arr[middle] )
right = middle - 1;
else // if ( value > arr[middle] )
left = middle + 1;
}
return -1; // Not found
}
13-67
Binary Search (cont’d)
• A “divide and conquer” algorithm.
• Works very fast: only 20 comparisons are
needed for an array of 1,000,000 elements;
(30 comparisons can handle 1,000,000,000
elements; etc.).
• We say that this is an O(log n) algorithm.
13-68
Sorting
• To sort means to rearrange the elements of a
list in ascending or descending order.
• Examples of sorting applications:
a
directory of files sorted by name or date
 bank checks sorted by account #
 addresses in a mailing list sorted by zip code
 hits found by a search engine sorted by
relevance
 credit card transactions sorted by date
13-69
Sorting (cont’d)
• The algorithms discussed here are based on
“honest” comparison of values stored in an
array. No tricks.
• How fast can we sort an array of n elements?
 If
we compare each element to each other we
need n(n-1) / 2 comparisons (that is, n2 by the
“order of magnitude.”)
 Faster “divide and conquer” sorting algorithms
need approximately n·log2 n comparisons (much
better).
13-70
Sorting (cont’d)
Time
n2
n log2 n
n
n
n2
n log2 n
10
100
35
100
10,000
700
1000
1,000,000
10,000
13-71
Sorting (cont’d)
Time
n2
n log2 n
n
n
n2
n log2 n
10
100
35
100
10,000
700
1000
1,000,000
10,000
13-72
Selection Sort
1. Select the max among the first n elements:
1 13
8
5
2
1
3
n
2. Swap it with the n-th element :
1
3
8
5
2
1 13
n
3. Decrement n by 1 and repeat from Step 1
(while n > 1)
1
3
8
5
n
2
1 13
13-73
Selection Sort (cont’d)
• Iterative implementation:
public void selectionSort (double [ ] arr, int n)
{
while (n > 1)
{
int maxPos = 0;
for (int k = 1; k < n; k++)
if (arr [k] > arr [maxPos] )
maxPos = k;
double temp = arr [maxPos];
swap a[maxPos]
arr [maxPos] = arr [n-1];
and a[n-1]
arr [n-1] = temp;
n--;
}
}
13-74
Selection Sort (cont’d)
• The total number of comparisons is
always
(n-1) + (n-2) + ... + 1 = n(n-1) / 2
• No average, best, or worst case —
always the same.
• An O(n2) algorithm.
13-75
Mergesort
1. Split the array into two roughly equal “halves.”
5
1
3
2
4
7
6
2. Sort (recursively) each half using Mergesort.
1
3
5
2
4
3. Merge the two halves together
1
2
3
6
7
1
3
5
2
4
6
7
The smaller one goes first
13-76
Mergesort (cont’d)
public void mergesort ( double arr [ ],
int from, int to )
{
if (from <= to)
return;
int middle = (from + to ) / 2;
mergesort (arr, from, middle);
mergesort (arr, middle + 1, to);
if (arr [middle] > arr [middle+ 1] )
{
copy (arr, from, to, temp) ;
merge (temp, from, middle, to, arr);
}
}
Optional shortcut:
“if not yet sorted”...
double temp[ ] is
initialized outside
the mergesort
method
13-77
Mergesort (cont’d)
• Takes roughly n·log2 n comparisons.
• Without the shortcut, there is no best or worst case.
• With the optional shortcut, the best case is when the
array is already sorted: takes only (n-1)
comparisons.
13-78
Insertion Sort
1. k = 1; keep the first k elements in order.
2. Take the (k+1)-th element and insert among the
first k in the right place.
1
3
5
2 13 1
k
8
3. Increment k and repeat from Step 2 (while k < n)
1
2
3
5 13 1
k
8
13-79
Insertion Sort (cont’d)
• Iterative implementation:
public void insertionSort (double arr [ ], int n)
{
int k, i;
for (k = 1 ; k < n; k++)
{
double saved = arr [ k ];
for (i = k; i > 0 && arr [ i-1 ] > saved; i--)
arr [ i ] = a[ i - 1 ];
arr [ i ] = saved;
}
}
13-80
Insertion Sort (cont’d)
• The average number of comparisons is
roughly half of the number in Selection Sort.
• The best case is when the array is already
sorted: takes only (n-1) comparisons.
• The worst case is n(n-1) / 2 when the array is
sorted in reverse order.
• On average, an O(n2) algorithm.
13-81
Bubble Sort Logic
Compare adjacent array elements.
Swap the elements if they are not ordered correctly.
Continue this process until the largest element is in
the last index of the array.
Repeat the comparison process in the same manner. During the
second pass make one less comparison, and place the
second-largest number in the second-to-last element of the array.
Repeat these comparison passes with N elements,
N-1 times. Each pass makes one less comparison.
13-82
Regular Bubble
Sort
public void bubbleSort()
{
int temp;
for (int p = 1; p < size; p++)
for (int q = 0; q < size-1; q++)
if (intArray[q] > intArray[q+1])
{
temp = intArray[q];
intArray[q] = intArray[q+1];
intArray [q+1] = temp;
}
}
13-83
Quicksort
1. Pick one element, called “pivot”
5
1
6
2
4
7
3
2. Partition the array, so that all the elements to the
left of pivot are  pivot; all the elements to the
right of pivot are  pivot.
4
1
3
2
5
7
6
3. Sort recursively the left and the right segments
using Quicksort.
13-84
Quicksort (cont’d)
• Takes roughly n·log2 n comparisons.
• May get slow if pivot consistently fails to split
the array into approximately equal halves.
• An O(n log n) algorithm.
13-85
Sorting Objects
Sorting Arrays of Objects



Any of the sort methods can be modified to sort
arrays of objects.
We assume that the objects implement the
Comparable interface and support the method
compareTo.
Then, we simply replace the type of all array
parameters with Object and make the
appropriate use of compareTo where the
comparison operators are used.
13-86
java.util.Collections
• Provides static methods for dealing with
ArrayLists and other Java collections.
• Works for arrays of numbers, Strings, and
Objects.
• Methods:
int pos = Collections.binarySearch (list, target);
Collections.sort (list);
Collections.shuffle (list);
13-87