Transcript Unit 7 Search and Sort

Unit 8 Search, Sort,
Recursion
Chapters 12 and 13
SEARCH
Number Guessing Algorithm
• Activity
• Get in groups of 3 and have 1 person pick a number and not tell
the others.
• The other people alternate picking numbers until they have.
• Questions
• How do you minimize the number of guesses that it takes to get
the correct #?
Demo using a Phone Book
Sequential Search
• The simplest type of search is the sequential search.
• In the sequential search, each element of the array is
compared to the key, in the order it appears in the array, until
the desired element is found.
• If you are looking for an element that is near the front of the
array, the sequential search will find it quickly. The more data
that must be searched, the longer it will take to find the data
that matches the key.
index
0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
value
-4
2
7
10 15 20 22 25 30 36 42 50 56 68 85 92 103
•
i
16
How many elements
will it need to
examine?
Sequential Search Cont.
• Consider this method which will search for a key integer value. If found, the index
(subscript) of the first location of the key will be returned. If not found, a value of -1
will be returned.
public static int seqSearch(int [ ] numbers, int key){
for (int index = 0; index < numbers.length; index++){
if ( numbers[index] == key )
return index; //We found it!!!
}
// If we get to the end of the loop,
// a value has not yet been returned.
// We did not find the key in this array.
return -1;
}
Sequential Search Continued
• If the key value is found, the index of the location is returned. This
tells us that the return value x, will be the first integer found such
that
numbers[index] == key.
• There may be additional key locations in this array beyond this
location.
Binary Search
• Do you remember playing the game "Guess a Number",
where the responses to the statement "I am thinking of a
number between 1 and 100" are "Too High", "Too Low", or
"You Got It!"?
• A strategy that is often used when playing this game is to
divide the intervals between the guess and the ends of the
range in half. This strategy helps you to quickly narrow in on
the desired number.
Binary Search Continued
Consider the following array of integers:
We will be searching for the integer 77:
Array of integers, named num, arranged in "ascending order"!!
Index
0
1
2
3
4
5
6
7
8
9
value
13
24
34
46
52
63
77
89
91
100
Goal: Search for 77:
1. Find the middle of the array by adding the array index of the first value to the
index of the last value and dividing by two: (0 + 9) / 2 = 4 Integer division is
used to arrive at the 4th index as the middle. (The actual mathematical middle
would be between the 4th and 5th index, but we must work with integer
indexes.)
• The 4th index holds the value 52, which is less than 77. Therefore, we
know that 77 will be in that portion of the array to the right of 52. We
now find the middle of the right portion of the array by using the same
approach. (5 + 9) / 2 = 7
Binary Search Continued
Consider the following array of integers:
We will be searching for the integer 77:
Array of integers, named num, arranged in "ascending order"!!
Index
0
1
2
3
4
5
6
7
8
9
value
13
24
34
46
52
63
77
89
91
100
2. Calculate the new mid, min, and max
a) min = mid + 1 (5)
b) max stays the same (9).
c) mid = The (9+5 /2) = 7
• Index 7 holds the integer 89, which comes after 77.
Binary Search Continued
Consider the following array of integers:
We will be searching for the integer 77:
Array of integers, named num, arranged in "ascending order"!!
Index
0
1
2
3
4
5
6
7
8
9
value
13
24
34
46
52
63
77
89
91
100
3. Calculate the new mid, min, and max
a) min stays the same (5).
b) max = mid – 1 (6)
c) mid = The (5+6 /2) = 5
• Index 5 holds the integer 63, which comes before 77.
Binary Search Continued
Consider the following array of integers:
We will be searching for the integer 77:
Array of integers, named num, arranged in "ascending order"!!
Index
0
1
2
3
4
5
6
7
8
9
value
13
24
34
46
52
63
77
89
91
100
4. Calculate the new mid, min, and max
a) min stays the same (5).
b) max = mid + 1 (7)
c) mid = The (5+ 7/2) = 6
• Index 6 holds the value 77.
Binary Search Continued.
• When searching an array, the binary search process utilizes this
same concept of splitting intervals in half as a means of finding the
"key" value as quickly as possible.
• If the array that contains your data is in order (ascending or
descending), you can search for the key item much more quickly by
using a binary search algorithm ("divide and conquer”)
• How many elements will it need to examine?
• Example: Searching the array below for the value 42:
index
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
value
-4
2
7
10
15
20
22
25
30
36
42
50
56
68
85
92
103
min
mid
max
Binary search code
// Returns the index of an occurrence of target in a,
// or a negative number if the target is not found.
// Precondition: elements of a are in sorted order
public static int binarySearch(int[] a, int target) {
int min = 0;
int max = a.length - 1;
while (min <= max) {
int mid = (min + max) / 2;
if (a[mid] < target) {
min = mid + 1;
} else if (a[mid] > target) {
max = mid - 1;
} else {
return mid;
// target found
}
}
return -(min + 1);
}
// target not found
Review
• If you have n elements in an array, what is the maximum
number of array elements that might need to be accessed to
find a key using the sequential search algorithm
• N
• What game is binary search like?
• Guessing Game
• In the Binary Search Algorithm, how many elements are
eliminated as not being the correct key each time through the
loop?
• ½
• Which algorithm, on average, is more efficient: sequential
search or binary search?
• Binary search.
RECURSION
Overview
•
•
•
•
•
M. C. Escher : Drawing Hands
Why Recursion?
You already know it!
Definition
Trust the Recursion!
Conclusion
Why recursion?
• Recursion can solve some kinds of problems better than
iteration
• Iteration == loops
• Leads to elegant, simplistic, short code (when used well)
• Many programming languages ("functional" languages such as
Scheme, ML, and Haskell) use recursion exclusively (no loops)
• A different way of thinking of problems
You Already Know it!
Recursion
• Recursion is an algorithmic technique where a method calls
itself with some part of the task
• Such a method is called recursive, and is said to recur (not
recurse!) when it calls itself.
• Many problems in computer science are particularly suited to
recursive solutions
• We will see several of these later
• An equally powerful substitute for iteration (loops)
• This is a very tricky concept.
compute()
Recursion Cases
•
Every recursive algorithm involves at least 2 cases:
base case: A simple occurrence that can be answered directly.
i.e If we are unstacking the Russian Nesting Dolls, have we
reached the smallest nesting doll?
recursive case: A more complex occurrence of the problem
that cannot be directly answered, but can instead be described
in terms of smaller occurrences of the same problem.
• Some recursive algorithms have more than one base or
•
recursive case, but all have at least one of each.
A crucial part of recursive programming is identifying these
cases.
Trust the Recursion!
• When authoring recursive code:
• The base case is usually easy: “When to stop?”
• In the recursive step
• How can we break the problem down into two:
• A piece I can handle right now
• The answer from a smaller piece of the problem
• Assume your self-call does the right thing on a smaller piece of the
problem
• How to combine parts to get the overall answer
• Practice will make it easier to see idea
• Exercises today
• Examples of recursion in our discussion on sorting algorithms
• More practice as we lead up to the AP exam
Recursion
• The if (<problem is simple>) is called the base case
• All recursive methods must have a base case
• What happens if they don’t?
compute()
• The rest of the method is called the recursive case
• When recurring, the problem must get “simpler” somehow
• What happens if it doesn’t?
Recursion – Pseudo Java Code
• The simplest recursive methods look like this:
public <static> <int> method(<parameters>) {
// base case
if(<problem is very simple>) {
<solve problem directly>
}
// recursive case
else {
<partial solution> = method(<“Smaller” params>)
<solve problem based on partial solution>
}
}
Example 1: Line of stars
• Consider the following method to print a line of * characters:
// Prints a line containing the given number of stars.
// Precondition: n >= 0
public static void printStars(int n) {
for (int i = 0; i < n; i++) {
System.out.print("*");
}
System.out.println();
// end the line of output
}
• Write a recursive version of this method (that calls itself).
• Solve the problem without using any loops.
• Hint: Your solution should print just one star at a time.
Solving for the Base Case
• What are the cases to consider?
• What is a very easy number of stars to print without a loop?
public static void printStars(int n) {
if (n == 1) {
// base case; just print one star
System.out.println("*");
}
else {
...
}
}
Handling more cases
• Handling additional cases, with no loops (in a bad way):
public static void printStars(int n) {
if (n == 1) {
// base case; just print one star
System.out.println("*");
}
else if (n == 2) {
System.out.print("*");
System.out.println("*");
}
else if (n == 3) {
System.out.print("*");
System.out.print("*");
System.out.println("*");
}
else if (n == 4) {
System.out.print("*");
System.out.print("*");
System.out.print("*");
System.out.println("*");
}
else ...
}
Handling more cases 2
• Taking advantage of the repeated pattern (somewhat better):
public static void printStars(int n) {
if (n == 1) {
// base case; just print one star
System.out.println("*");
}
else if (n == 2) {
System.out.print("*");
printStars(1);
// prints "*"
}
else if (n == 3) {
System.out.print("*");
printStars(2);
// prints "**"
}
else if (n == 4) {
System.out.print("*");
printStars(3);
// prints "***"
}
else ...
}
Using recursion properly
• Condensing the recursive cases into a single case:
public static void printStars(int n) {
// Base Case - just print one star
if (n == 1) {
System.out.println("*");
}
// recursive case; print one more star
else {
System.out.print("*");
printStars(n - 1);
}
}
Example 2: Remembering GCD
Euclid's Algorithm
• Consider two positive integers, a and b. To find the Greatest
Common Divisor (GCD) of these two, we follow these steps:
While (b != 0),
temp = b
b = a MOD b
a = temp
• The current value of a is the GCD of the original a and b
values.
• When b = 0, then GCD is stored in a
http://www.ehow.com/how_2247601_find-greatest-commondivisor.html
Iterative GCD
public static int gcd(int a, int b){
int temp;
do {
//GCD(a,b) = GCD(b, a % b)
// Store b prior to assigning it, so that we can assign
that value to a.
temp = b;
b = a % b;
a = temp;
} while (b != 0);
return Math.abs(a);
}
Recursive GCD
public int gcd(int a, int b) {
// Base Case
if (b == 0){
return Math.abs(a);
}
// recursive case
else{
return gcd( b, a % b );
}
}
Russian Doll Recursion Activity
• In Pairs,
• Write two pseudo-code algorithms to determine how many dolls
are nested in the Russian Dolls
• 1 Iterative method
• 1 Recursive method
Recursive tracing
• Consider the following recursive method:
public static int mystery(int n) {
if (n < 10)
{
return n;
}
else {
int a = n / 10;
int b = n % 10;
return mystery(a + b);
}
}
What is the result of the following call?
mystery(648)
A recursive trace
mystery(648):
 int a = 648 / 10;
 int b = 648 % 10;
 return mystery(a + b);
mystery(72):
 int a = 72 / 10;
 int b = 72 % 10;
 return mystery(a + b);
mystery(9):
 return 9;
public static int mystery(int n) {
if (n < 10){
return n;
}
else {
int a = n / 10;
int b = n % 10;
return mystery(a + b);
}
}
// 64
// 8
// mystery(72)
// 7
// 2
// mystery(9)
Recursive tracing 2
• Consider the following recursive method:
public static int mystery2(int n) {
if (n < 10) {
return (10 * n) + n;
}
else {
int a = mystery2(n / 10);
int b = mystery2(n % 10);
return (100 * a) + b;
}
}
• What is the result of the following call?
mystery2(348)
A recursive trace 2
public static int mystery2(int n) {
if (n < 10) {
return (10 * n) + n;
}
else {
int a = mystery2(n / 10);
int b = mystery2(n % 10);
return (100 * a) + b;
}
}
mystery2(348)
 int a = mystery2(34);
• int a = mystery2(3);
return (10 * 3) + 3;
// 33
• int b = mystery2(4);
return (10 * 4) + 4;
// 44
• return (100 * 33) + 44;
// 3344
 int b = mystery2(8);
return (10 * 8) + 8;
• return (100 * 3344) + 88;
// 88
// 334488
Pair Activity
Summary
• What is recursion?
• Recursion is when a method calls itself in its method body
• Such a method is called recursive, and is said to recur (not recurse!) when it
calls itself.
• What are the two types of cases that all recursive algorithms have?
base case: A simple occurrence that can be answered directly.
recursive case: A more complex occurrence of the problem that cannot be
directly answered, but can instead be described in terms of smaller occurrences of
the same problem.
Exercises
• Write a recursive method pow that accepts an integer base
and exponent and returns the base raised to that exponent.
• Example: pow(3, 4) returns 81
• Solve the problem recursively and without using loops.
• Write a recursive method fib that accepts an integer n and
returns the nth number in the Fibonacci sequence.
• The nth Fibonacci number equals the sum of the previous two
numbers if n >=3. The sequence begins with the 0th number.
• 0 1 1 2 3 5 8 13 21 ….base and exponent and returns the base raised
to that exponent.
• Example: fib(7) returns 13
pow solution
// Returns base ^ exponent.
// Precondition: exponent >= 0
public static int pow(int base, int exponent) {
if (exponent == 0) {
// base case; any number to 0th power is 1
return 1;
} else {
// recursive case: x^y = x * x^(y-1)
return base * pow(base, exponent - 1);
}
}
SORTING ALGORITHMS
4 2 6 8 1 3 7 5
Bubble Sort
4 2 6 8 1 3 7 5
Selection Sort
4 2 6 8 1 3 7 5
Selection Sort
• The selection sort is a combination of searching and sorting.
• During each pass, the unsorted element with the smallest (or
largest) value is moved to its proper position in the array.
• The number of times the sort passes through the array is one
less than the number of items in the array. In the selection
sort, the inner loop finds the next smallest (or largest) value
and the outer loop places that value into its proper location
Selection sort example
• Initial array:
index
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
value
22
18
12
-4
27
30
36
50
7
68
91
56
2
85
42
98
25
7
8
9
value -4 18 12 22 27 30 36 50
7
68 91 56
index
index
• After 1st, 2nd, and 3rd passes:
0
1
2
3
3
4
4
5
2
85 42 98 25
1
2
7
8
9
value -4
2
12 22 27 30 36 50
7
68 91 56 18 85 42 98 25
index
0
1
2
3
value -4
2
7
22 27 30 36 50 12 68 91 56 18 85 42 98 25
5
6
10 11 12 13 14 15 16
0
4
5
6
6
7
8
9
10 11 12 13 14 15 16
10 11 12 13 14 15 16
Selection Sort Continued
public static void selectionSort (int arr[] ){
int i, j, first, temp;
for ( i = arr.length - 1; i > 0; i-- ){
//initialize to subscript of first element
first = 0;
//locate smallest element between positions 1 and i
for(j = 1; j <= i; j ++){
if( arr[j] > arr[first] ){
first = j;
}
}
//swap smallest found with element in position i.
temp = arr[first];
arr[first] = arr[i];
arr[i] = temp;
}
}
Selection Sort Summary
• Selection sort is an in place comparison sort
• Selection sort has the property of minimizing the number of
swaps. In applications where the cost of swapping items is
high, selection sort very well may be the algorithm of choice.
• It is much less efficient on large lists than the more advanced
algorithms such as quicksort, heapsort, or merge sort
• The algorithm finds the minimum value, swaps it with the
value in the first position, and repeats these steps for the
remainder of the list. It does no more than n swaps, and thus
is useful where swapping is very expensive.
Insertion Sort
• Insertion sort algorithm somewhat resembles selection sort.
• Array is imaginary divided into two parts - sorted one and unsorted
one.
• At the beginning, sorted part contains first element of the array and
unsorted one contains the rest.
• At every step, algorithm takes first element in the unsorted part and
inserts it to the right place of the sorted one.
• When unsorted part becomes empty, algorithm stops.
Insertion Sort Continued
Insertion sort algorithm step looks like this:
becomes
Insertion sort example
• Initial array:
index
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
value
22
18
12
-4
27
30
36
50
7
68
91
56
2
85
42
98
25
index
• After 1st, 2nd, 3rd and 8th passes:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
value
18 22
12
-4
27
30
36
50
7
68
91
56
2
85
42
98
25
index
0
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
-4
27
30
36
50
7
68
91
56
2
85
42
98
25
3
4
5
6
7
8
9
10
11
12
13
14
15
16
22
27
30
36
50
7
68
91
56
2
85
42
98
25
4
5
6
7
8
9
10
11
12
13
14
15
16
50
68
91
56
2
85
42
98
25
value
1
12 18 22
index
0
1
2
value
-4
index
0
1
2
3
value
-4
7
12
18
12 18
22 27 30 36
Insertion Sort Continued
• The main operation of the algorithm is insertion. The
task is to insert a value into the sorted part of the array.
Let us see the variants of how we can do it.
• "Sifting down" using swaps
• The simplest way to insert next element into the sorted
part is to sift it down, until it occupies correct position.
Initially the element stays right after the sorted part. At
each step algorithm compares the element with one
before it and, if they stay in reversed order, swap them.
Insertion Sort Continued
This approach writes sifted element to temporary position many times. Next
implementation eliminates those unnecessary writes.
Insertion Sort Continued
• Shifting instead of swapping
• We can modify previous algorithm, so it will write shifted
element only to the final correct position. Let us see an
illustration.
Insertion Sort Method
public static void insertionSort(int[] arr) {
int i, j, newValue;
for (i = 1; i < arr.length; i++) {
// Get a new value to insert into our "sorted" array
newValue = arr[i];
j = i;
// Shift values to right as long as they are greater
// than new value
while (j > 0 && arr[j - 1] > newValue) {
arr[j] = arr[j - 1];
j--;
}
// Place our new value in it's correct position
arr[j] = newValue;
}
}
Insertion Sort Summary
• Insertion sort is a simple sorting algorithm, a comparison sort in
which the sorted array (or list) is built one entry at a time.
• It is much less efficient on large lists than the more advanced
algorithms such as quicksort, heapsort, or merge sort, but it has
various advantages:
•
•
•
•
Simple to implement
Efficient on (quite) small data sets
Efficient on data sets which are already substantially sorted
Stable (does not change the relative order of elements with equal
keys)
• In abstract terms, each iteration of an insertion sort removes an
element from the input data, inserting it at the correct position in
the already sorted list, until no elements are left in the input. The
choice of which element to remove from the input is arbitrary and
can be made using almost any choice algorithm.
Sorting Algoritms Visual
• http://www.sorting-algorithms.com
Summary
• How would you describe the Selection Sort algorithm – that is what happens
in each pass?
• The algorithm finds the minimum value, swaps it with the value in the first
position, and repeats these steps for the remainder of the list.
• When is Selection Sort – the sorting algorithm of choice?
• Selection sort has the property of minimizing the number of swaps. In
applications where the cost of swapping items is high, selection sort very well
may be the algorithm of choice.
• How would you describe the Insertion Sort algorithm – that is what happens
in each pass?
• Each iteration of an insertion sort removes an element from the input data,
inserting it at the correct position in the already sorted list, until no elements
are left in the input.
• When is Insertion Sort – the sorting algorithm of choice?
• Insertion sort is the algorithm of choice either when the data is nearly sorted
(because it is adaptive) or when the problem size is small (because it has low
overhead).
MERGESORT
When to use Mergesort
• Stability is required – more on that in a minute.
• Sorting linked lists – a data structure that we haven’t talked
about.
• When random access is much more expensive than sequential
access
• For example, external sorting on tape.
• The Arrays class has a sort method that is overloaded.
• For numeric types, Quicksort is used.
• For objects, Mergesort is used.
Stability – what is it?
• Stability means that equivalent elements retain their relative
positions, after sorting.
• Suppose you want to sort the following list based upon the state:
• There are 2 correct outputs
City
State
New York
NY
Chicago
IL
Renton
WA
Issaquah
WA
Los Angeles
CA
City
State
City
State
Los Angeles
CA
Los Angeles
CA
Chicago
IL
Chicago
IL
New York
NY
New York
NY
Renton
WA
Issaquah
WA
Issaquah
WA
Renton
WA
• The 1st one is stable, because the State key is sorted and the city field
maintains the order of the original list.
Stability – Why is it important?
• For primitives – really isn’t
• For objects – it definitely is.
• Example
• What do you expect to happen if you sort email messages first by
date and then by sender?
• You expect them to be sorted by date within each sender
• That only happens when your sort algorithm is stable.
Merge sort
• merge sort: Repeatedly divides the data in half, sorts each
half, and combines the sorted halves into a sorted whole.
The algorithm:
• Divide the list into two roughly equal halves.
• Sort the left half.
• Sort the right half.
• Merge the two sorted halves into one sorted list.
• Often implemented recursively.
• An example of a "divide and conquer" algorithm.
• Invented by John von Neumann in 1945
Merge sort example
index 0
1
2
3
4
5
6
7
value 22 18 12 -4 58
7
31 42
split
split
split
22 18 12 -4
22 18
22
merge
12 -4
split
18
split
12
split
-4
merge
58 7 31 42
58 7
58
split
7
merge
18 22
-4 12
merge
31 42
31
merge
7 58
31 42
merge
-4 12 18 22
7 31 42 58
merge
-4
42
7 12 18 22 31 42 58
Merging sorted halves
Merge halves code
// Merges the left/right elements into a sorted result.
// Precondition: left/right are sorted
public static void merge(int[] result, int[] left,
int[] right) {
int i1 = 0;
// index into left array
int i2 = 0;
// index into right array
for (int i = 0; i < result.length; i++) {
if (i2 >= right.length ||
(i1 < left.length && left[i1] <= right[i2])) {
result[i] = left[i1];
// take from left
i1++;
} else {
result[i] = right[i2];
// take from right
i2++;
}
}
}
Merge sort code
// Rearranges the elements of a into sorted order using
// the merge sort algorithm (recursive).
public static void mergeSort(int[] a) {
if (a.length >= 2) {
// split array into two halves
int[] left = Arrays.copyOfRange(a, 0, a.length/2);
int[] right = Arrays.copyOfRange(a, a.length/2, a.length);
// sort the two halves
…
// merge the sorted halves into a sorted whole
merge(a, left, right);
}
}
Merge sort code 2
// Rearranges the elements of a into sorted order using
// the merge sort algorithm (recursive).
public static void mergeSort(int[] a) {
if (a.length >= 2) {
// split array into two halves
int[] left = Arrays.copyOfRange(a, 0, a.length/2);
int[] right = Arrays.copyOfRange(a, a.length/2, a.length);
// sort the two halves
mergeSort(left);
mergeSort(right);
// merge the sorted halves into a sorted whole
merge(a, left, right);
}
}
Activity
• 13.30
Quick Sort
Summary
• When is Mergesort the sorting algorithm of choice?
• Stability is required
• What are the 3 main steps of Mergesort?
1.
2.
3.
Divide the list into two roughly equal halves.
Sort the halves.
Merge the two sorted halves into one sorted list.
Think-Pair-Share Activity
• How does mergeSort compare Objects in Java?
• That is, how do you know whether two objects of the same
type are < or > than each other?
• How would that work for two FormulaCell objects?
Comparing Objects
• Implement the Comparable Interface
• compareTo method
• Lists and Arrays that implement this interface can be sorted
automatically by the following methods
• Collections.sort
• Arrays.sort
The compareTo method (10.2)
• The standard way for a Java class to define a comparison
function for its objects is to define a compareTo method.
• Example: in the String class, there is a method:
public int compareTo(String other)
• A call of A.compareTo(B) will return:
a value <
a value >
or
0
0
0
if A comes "before" B in the ordering,
if A comes "after" B in the ordering,
if A and B are considered "equal" in the ordering.
Unit Review
Unit Review
Recursion (cb q16)
1. Consider the following recursive method.
public static int mystery(int n)
{
if (n == 0)
return 1;
else
return 3 * mystery(n - 1);
}
What value is returned as a result of the call mystery(5) ?
(a) 0
(b) 3
(c) 81
(d) 243
(e) 6561
Search (Barrons 3q30)
3. Under which conditions will a sequential search of arr be
faster than a binary search?
Consider a sorted array arr of n elements, where n is large and
n is even.
I The target is not in the list
II The target is in the first position of the list
III the target is in arr[1 + n/2]
(A)
(B)
(C)
(D)
(E)
I only
II only
III only
I and III only
II and III only
2. Sort (Barrons 2q30)
Consider the following mergeSort method and
the private instance variable a both in the same
Sorter class:
private Comparable [] a;
/* sorts a[first] to a[last] in increasing order. */
Public void mergeSort (int first, int last)
{
if (first != last)
{
int mid = (first + last) /2;
mergeSort(first, mid);
mergeSort(mid+1, last);
merge(first, mid, last);
}
}
Method mergeSort calls method merge, which
has this header:
// Merge a[lb] to a[mi+1] to a[ub].
Private void merge (int lb, int m, int ub)
If the first call to mergeSort is mergeSort(0,3)
how many further calls will there be to
mergeSort before an array b[0]…b[3] is sorted?
(A) 2
(B) 3
(C) 4
(D) 5
(E) 6
CollegeBoard
• http://apcentral.collegeboard.com/apc/public/repository/apcomputer-science-course-description.pdf
Efficiency of Selection Sort
(n-1) + (n-2) + … + 1
n(n-1) /2
(n2-n)/2
n2/2 – n/2
1,000,000
n2/2 – n/2
1,000,000,0002/2 -1,000,000/2
500,000,000,000 – 500,000
499,999,500,000
O(n2)
Big O - Notation
O(n2)
O(n log n)
O (log n)
O(1)
Selection Sort, Insertion Sort, Bubble Sort
Videos
• Search & Sort
• https://www.youtube.com/watch?v=IEOO5UToo6A