Transcript document

Examples of Recursion
Data Structures in Java with JUnit
©Rick Mercer
Converting Decimal Numbers to other
bases
 Problem: Convert a decimal (base 10) number
into other bases
method Call
convert(99,
convert(99,
convert(99,
convert(99,
convert(99,
convert(99,
convert(99,
convert(99,
Return
2)
3)
4)
5)
6)
7)
8)
9)
1100011
10200
1203
344
243
201
143
120
Digits are multiplied by powers of the
base 10, 8, 2, or whatever
 First: converting from other bases to decimal

Decimal numbers multiply digits by powers of 10
950710 = 9 x 103 +

Octal numbers
5 x 102 +
0 x 101 + 7 x 100
powers of 8
15678 = 1 x 83 + 5 x 82 + 6 x 81 + 7 x 80
= 512 + 320
+
48
+
7 = 88710

Binary numbers
powers of 2
11012 = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20
=
8
+
4
+
0
+
1 = 1310
Converting base 10 to base 2
1) divide number (5) by new base(2), write remainder (1)
2) divide quotient (2), write new remainder (0) to left
3) divide quotient (1), write new remainder (1) to left
__2_
2 ) 5
__1_
2 ) 2
__0_
2 ) 1
Remainder =
1
Remainder =
0
Remainder =
1
Stop when the quotient is 0
510 = 1012
Print remainders in reverse order
Converting base 10 to base 8
1) divide number by new base (8), write remainder (1)
2) divide quotient (2), write new remainder (0) to left
3) divide quotient (1), write new remainder (1) to left
_12_
8 )99
__1_
8 )12
__0_
8 ) 1
Remainder =
3
Remainder =
4
Remainder =
1
Stop when the quotient is 0
9910 = 1438
Print remainders in reverse order
Possible Solutions
 We could either


store remainders in an array and reverse it or
write out the remainders in reverse order


have to postpone the output until we get quotient = 0
store result as a String (like a Recursion assignment)
 Iterative Algorithm
while the decimal number > 0 {
Divide the decimal number by the new base
Set the decimal number = decimal number divided by the base
Store the remainder to the left of any preceding remainders
}
Recursive algorithm
Base Case -- Recursive Case
 Base case

if decimal number being converted = 0

do nothing (or return "")
 Recursive case

if decimal number being converted > 0

solve a simpler version of the problem
– use the quotient as the argument to the next call

store the current remainder (number % base) in the
correct place
One solution
assertEquals("14", rf.convert(14, 10));
assertEquals("1100011", rf.convert(99, 2));
assertEquals("143", rf.convert(99, 8));
assertEquals("98", rf.convert(98, 10)); // 9*10+8
public String convert(int num, int base) {
if (num == 0)
return "";
else
return convert(num/base, base) + (num%base);
}
Hexadecimal, something we
see as Computer Scientists
 Convert this algorithm to handle all base up
through hexadecimal (base 16)






10 = A
11 = B
12 = C
13 = D
14 = E
15 = F
Quicksort:
O(n log n) Sorting
 Quicksort was discovered by Tony Hoare 1962
 Here is an outline of his famous algorithm:



Pick one item from the array--call it the pivot
Partition the items in the array around the pivot so all
elements to the left are  to the pivot and all elements to
the right are greater than the pivot
Use recursion to sort the two partitions a snapshot
partition 1: items  pivot
pivot
partition: items > pivot
Before and After
 Let's sort integers


Pick the leftmost one (27) as the pivot value
The array before call to partition(a, 0, n-1)
27 14 9 22 8 41 56 31 14 53 99 11 2 24

Array looks like this after first partition is done
24 14 9 22 8 14 11
items < pivot
2 27 53 99 56 31 41
pivot
items > pivot
The partition method
 partition divvies up a around the split and
returns the position of the split, an integer in the
range of 0..n-1

The postcondition of partition:
a[first]..a[split-1] <= a[split]
&&
a[split+1]..a[last] > a[split]
 Notes:
May be more than 1 element equal to the pivot
 Put them in left partition could have been the right

Recursive call to sort smaller
part of the array
quickSort(a, split+1, last);
// sort right
QuickSort the right. At some point


Pivot will be 53
Assume left portion is already sorted
24 14 9 22 8 14 11 2 27 53 99 56 31 41
left is already sorted, begin to sort part to the right of split
2 8 9 11 14 14 22 24 27 31 41 53 99 56
pivot
items < pivot
items > pivot
Complete the sort
// sort left and right around new split
quickSort(a, first, split-1);
2 8 9 11 14 14 22 24 27 31 41 53 99 56
2 8 9 11 14 14 22 24 27 31 41 53 99 56
// sort right
quickSort(a, split+1, last);
2 8 9 11 14 14 22 24 27 31 41 53 99 56
2 8 9 11 14 14 22 24 27 31 41 53 56 99
Entire array is now sorted
Start Over (i ==1)
 Now let's back up and start with empty partitions
int partition(int a[], int first, int last) {
int lastSmall = first;
int i = (first + 1); // Beginning of unknowns
first lastSmall i
27
unknown items (all are unknown--except first)
41 14 56 31
9 22
8 14 53 99 11
2 24
 Compare all items from a[i]..a[last]


if a[i] > a[first] (the pivot), do nothing
if a[i] <= a[first], swap a[lastSmall+1] with a[i]
Result of the 1st loop
iteration(i==2)

The following array shows no changes were
made in the array since a[i] <= a[first] was false
 So simply add 1 to i (i++)--create 2 partitions
 Now partition 1 has one element (the pivot 27)
and partition 2 has 1 element (41)
first lastSmall i
27
unknown items
41 14 56 31 9 22 8 14 53 99 11 2 24
partition 1: all items <= pivot
partition 2: all items > pivot
Result of the 2nd loop
iteration(i==3)

The following array shows a swap was made in
the array since a[i] <= a[first] was true (14 < 27)
 a[i] (14) is swapped with a[lastSmall+1] (41)
 lastSmall gets incremented to point to the last
element in partition 1
 i gets incremented to reference 56
first lastSmall i
27
unknown items
14 41 56 31 9 22 8 14 53 99 11 2 24
partition 1: all items <= pivot
partition 2: all items > pivot
Result of the 3rd loop
iteration(i==4)

The following array shows no swap was made
in the array since a[i] <= a[first] was false
 lastSmall does NOT get incremented
 i gets incremented to reference 31
first lastSmall i
27
unknown items
14 41 56 31 9 22 8 14 53 99 11 2 24
partition 1: all items <= pivot
partition 2: all items > pivot
Result of the 4th loop
iteration(i==5)

The following array shows no swap was made
in the array since a[i] <= a[first] was false
 lastSmall does NOT get incremented
 i gets incremented to reference 9
first lastSmall
27
14 41 56 31
i
unknown items
9 22 8 14 53 99 11 2 24
partition 1: all items <= pivot
partition 2: all items > pivot
Result of the 5th loop
iteration(i==6)
 The following array shows a swap was made in
the array since a[i] <= a[first] was true (9 < 27)
 a[i] (9) is swapped with a[lastSmall+1] (41)
 lastSmall gets incremented to point to the last
element in partition 1
 i++ points to the first unknown (22)
first lastSmall
27
14
i
unknown items
9 56 31 41 22 8 14 53 99 11 2 24
partition 1: all items <= pivot
partition 2: all items > pivot
i == 7
first lastSmall
27
14
i
9 22 31 41 56
partition 1: all items <= pivot
unknown items
8 14 53 99 11 2 24
partition 2: all items > pivot
i == 8
first lastSmall
27
14
9 22 8
i
41 56 31
partition 1: all items <= pivot
unknown
14 53 99 11 2 24
partition 2: all items > pivot
i == 9
first lastSmall
27
14
i
unknown
9 22 8 14 56 31 41 53 99 11 2 24
partition 1: all items <= pivot
partition 2: all items > pivot
i == 10
first lastSmall
27
14
i
unknown
9 22 8 14 56 31 41 53 99 11 2 24
partition 1: all items <= pivot
partition 2: all items > pivot
i == 11
first lastSmall
27
14
i
unknown
9 22 8 14 56 31 41 53 99 11 2 24
partition 1: all items <= pivot
partition 2: all items > pivot
i == 12
first lastSmall
27
14
i
unknown
9 22 8 14 11 31 41 53 99 56 2 24
partition 1: all items <= pivot
partition 2: all items > pivot
i == 13
first lastSmall
27
14
i
unknown
9 22 8 14 11 2 41 53 99 56 31 24
partition 1: all items <= pivot
partition 2: all items > pivot
Result of the 14th loop
iteration(i==14)

The following array shows what happens after
traversing the entire array with this loop (i>last):
for (i = first + 1; i <= last; i++) {
if(a[i] <= a[first] ) {
lastSmall++;
swapElements(a, lastSmall, i);
}
}
first
27
lastSmall
14
9 22
8 14 11
partition 1: all items <= pivot
2 24
i
53 99 56 31 41
partition 2: all items > pivot
Post Loop Detail
 Now place the pivot into where we expect the
pivot to be: in-between the two partitions
swapElements( a, first, lastSmall );
 Then we can return lastSmall for the next call
return lastSmall;
first
24
lastSmall (pivot position)
14
9 22
8 14 11
partition 1: all items <= pivot
2 27
53 99 56 31 41
partition 2: all items > pivot
quickSort is called like this:
quickSort(a, 0, n-1)
void quickSort(int a[], int first, int last) {
// precondition: a is an array to be sorted from
// a[first]..a[last]
if(first >= last)
return; // Done: we have an empty array
// The difficult algorithm is in partition
int split = partition ( a, first, last );
// Recursively Quicksort left, then right
quickSort(a, first, split-1); // sort left
quickSort(a, split+1, last);
// sort right
// post: the array a is sorted
}
Analyzing Quicksort
 The critical statement happens in the comparison
of the for loop of the partition function
if(a[i] <= a[first])


So how many times is partition called?
And what are the values for first and last (#
comparisons)?
 If the pivot element is near the mode, we don't
have many calls to QuickSort, it is O(log n)
The best of Quicksort,
the worst of Quicksort
 In the best case (1st element is always middle
value) with 7 elements, call partition 3 times
first == 0, last == 6
first == 0, last == 2
first == 4, last == 6
// 6 comparisons
// 2 comparisons
// 2 comparisons
 In the worst case, (sorted array), with 7 elements,
partition is called
first
first
first
first
first
first
==
==
==
==
==
==
0,
1,
2,
3,
4,
5,
last
last
last
last
last
last
==
==
==
==
==
==
6
6
6
6
6
6
//
//
//
//
//
//
6
5
4
3
2
1
comparisons
comparisons
comparisons
comparisons
comparisons
comparison
Best Case:
[ 4, 1, 3, 2, 6, 5, 7 ]
[ 2, 1, 3, 4, 6, 5, 7 ]
[ 2, 1, 3]
[ 6, 5, 7 ]
[ 1, 2, 3]
[ 5, 6, 7 ]
[1]
[3]
[5]
[7]
Worst Case
[ 1, 2, 3, 4, 5, 6, 7]
[]
[2, 3, 4, 5, 6, 7]
[]
[3, 4, 5, 6, 7]
[]
[4, 5, 6, 7]
[]
[5, 6, 7]
[]
[6, 7]
[]
[7]
[]
[]
The Best and Worst continued
 So in the worst case, partition is called n-1
times:
(n-1)+(n-2)+ ... + 1 comparisons = O(n2)
 The worst case of Quicksort may be the same
as Selection Sort, which is O(n2)
 Quicksort is used because of its best and
average cases