Transcript Arrays, part 2

Arrays, part 2
Array applications
• Arrays are useful whenever a relatively
large amount of data must be kept
available in memory for processing
• We will look at several examples of array
applications, and see how arrays can be
used as arguments to methods and as
method return values
Application 1: frequency counter
• A common programming problem involves
counting the number of times particular
values are found in a data set, or particular
events occur while a program is running
• An array can be used as a frequency
counter, keeping track of the frequency of
occurrence of several events at a time
Example: are the dice fair?
• For our first example, consider the dice
game craps:
– The game involves rolling two six-sided dice
– Both dice have a pattern of dots on each of
their sides; each has a side with 1, 2, 3, 4, 5
and 6 dots
– When the dice are rolled, whichever sides
land up determine the score for the roll; for
example, if the dice read 3 and 4, the player
rolled a 7
Are the dice fair?
• The possible dice combinations are these
(repeat combinations are not shown):
Determining fairness
• With fair dice, the most common roll should be 7,
since there are more combinations (two each of
1-6, 2-5, and 3-4) that add up to 7 than any
other combination
• We should see a 7 come up one-sixth of the
time
• A Java program that plays craps would use a
random number generator to simulate the roll of
the dice
• We can use an array as a frequency counter to
determine if the simulated dice are fair
Testing dice fairness
• First, we’ll write a method that produces a
random number between 1 and 6
• To test the fairness of our method, we will call it
from within a loop that runs several thousand
times; each time we roll (by calling the method
twice, once for each die), we will record the
score by incrementing an index in a frequencycounting array
• When the loop is finished, we’ll examine the
array to see how often we rolled a 7
Code for example 1
import java.util.*;
public class DiceGame {
private Random rg; // generates random # to represent roll
public DiceGame () { // initialize random number generator
rg = new Random();
}
public int rollDice () { // return a number between 1 and 6
int cube = rg.nextInt();
cube = Math.abs(cube);
cube = cube % 6 + 1;
return cube;
}
Code for example 1
public boolean testDice () {
boolean fair = false;
int [] diceCounter = new int [13];
for (int x=0; x<13; x++)
diceCounter[x] = 0;
int die1, die2;
for (int y=0; y<100000; y++)
{
die1=rollDice();
die2=rollDice();
diceCounter[die1+die2]++;
}
System.out.println ("After rolling dice 100,000 times, we have:");
for (int z=2; z<13; z++)
System.out.println (z + ":\t" + diceCounter[z]);
if (diceCounter[7] >= (1.0/6.0))
fair = true;
return fair;
}
Code for example 1
public static void main (String [] args) {
DiceGame dg = new DiceGame();
System.out.println ("Testing dice ...");
boolean areFair = dg.testDice();
if (areFair)
System.out.println ("Dice are fair - we can play");
else
System.out.println ("These dice are loaded!");
}
}
Sample output from example 1
Testing dice ...
After rolling dice 100,000 times, we have:
2:
2806
3:
5511
4:
8377
5:
11094
6:
13958
7:
16593
8:
13803
9:
11230
10:
8230
11:
5603
12:
2795
Dice are fair - we can play
Application 2: sorting algorithms
• Sorting is one of the most basic operations
of computers; the need to sort data was
one of the motivating factors for the
invention of automatic computing
machines
• We will take a brief look at a few of the
many sorting algorithms that have been
developed over the years, using an array
of random integers as our data set
A testbed for sorting algorithms
• The next slide presents some of the
methods of a class that is designed to test
various sorting algorithms
• The class contains an array of random
integers and the means to copy and print
this array, as well as implementations of a
few well-known sorting algorithms
Sorter class – private members,
default constructor, utility methods
import java.util.*;
public class Sorter {
private int [] numbers;
private Random rg;
public Sorter () {
numbers = new int [100];
rg = new Random();
for (int x = 0; x<100; x++)
{
int tmp = rg.nextInt();
tmp = Math.abs(tmp);
tmp = tmp % 100 + 1;
numbers[x] = tmp;
}
}
public int [] copyArray () {
int [] sorted = new int [numbers.length];
for (int x=0; x < numbers.length; x++)
sorted[x] = numbers[x];
return sorted;
}
public static void printArray (int [] array) {
for (int x=0; x<array.length; x++)
{
if (x % 10 == 0)
System.out.print("\n");
System.out.print (array[x] + "\t");
}
}
Selectionsort
• Goal of the algorithm is to sort a list of
values (for example, integers in an array)
from smallest to largest
• The method employed comes directly from
this statement of the problem
– find smallest value and place at front of array
– find next-smallest value and place in second
position
– find next-next-smallest and place in third
position
– and so on ...
Selectionsort
• The mechanics of the algorithm are
simple: swap the smallest element with
whatever is in the first position, then move
to the second position and perform a
similar swap, etc.
• In the process, a sorted subarray grows
from the front, while the remaining
unsorted subarray shrinks toward the back
Sorting an Array of Integers
• The picture
shows an
array of six
integers
that we
want to sort
from
smallest to
largest
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Selectionsort Algorithm
• Start by
finding the
smallest
entry.
• Swap the
smallest
entry with
the first
entry.
70
70
60
60
50
50
40
40
30
30
20
20
10
10
00
[1]
[1]
[0]
[2]
[2]
[1]
[3]
[3]
[2]
[4]
[4]
[3]
[5]
[5]
[4]
[6]
[6]
[5]
The Selectionsort Algorithm
Sorted side
Unsorted side
70
• Part of the
array is
now sorted.
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Selectionsort Algorithm
Sorted side
• Find the
smallest
element in
the
unsorted
side.
Unsorted side
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Selectionsort Algorithm
Sorted side
• Swap with
the front of
the
unsorted
side.
Unsorted side
70
70
60
60
50
50
40
40
30
30
20
20
10
10
00
[1]
[1]
[0]
[2]
[2]
[1]
[3]
[3]
[2]
[4]
[4]
[3]
[5]
[5]
[4]
[6]
[6]
[5]
The Selectionsort Algorithm
Sorted side
• We have
increased
the size of
the sorted
side by one
element.
Unsorted side
70
70
60
60
50
50
40
40
30
30
20
20
10
10
00
[1]
[1]
[0]
[2]
[2]
[1]
[3]
[3]
[2]
[4]
[4]
[3]
[5]
[5]
[4]
[6]
[6]
[5]
The Selectionsort Algorithm
Sorted side
Unsorted side
70
• The
process
continues...
60
Smallest
from
unsorted
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Selectionsort Algorithm
Sorted side
Unsorted side
70
• The
process
continues...
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Selectionsort Algorithm
Sorted side
is bigger
Sorted side
Unsorted side
70
• The
process
continues...
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Selectionsort Algorithm
• The process
keeps adding
one more
number to the
sorted side.
• The sorted
side has the
smallest
numbers,
arranged from
small to large.
Sorted side
Unsorted side
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Selectionsort Algorithm
• We can stop
when the
unsorted side
has just one
number, since
that number
must be the
largest
number.
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Selectionsort Algorithm
• The array is
now sorted.
• We repeatedly
selected the
smallest
element, and
moved this
element to the
front of the
unsorted side.
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
Implementation of Selectionsort
public void selectionSort () {
int mindex, len, tmp;
len = numbers.length;
for (int x = 0; x <= len-2; x++)
{
mindex = x;
for (int y = x+1; y <= len-1; y++)
if (numbers[y] < numbers[mindex])
mindex = y;
tmp = numbers[x];
numbers[x] = numbers[mindex];
numbers[mindex] = tmp;
}
}
Sample output
Before sort:
59
35
32
78
7
14
66
88
10
66
20
21
71
77
99
77
71
51
51
64
51
89
99
29
63
53
86
38
34
60
38
64
90
81
3
4
37
64
80
66
65
34
13
51
92
62
86
16
33
9
75
76
26
21
99
19
56
28
16
7
36
12
76
55
48
15
76
50
34
19
91
93
47
79
91
20
54
23
17
61
4
48
44
83
40
55
19
22
79
62
65
82
83
21
87
4
36
8
16
28
4
14
20
32
38
51
62
71
79
89
4
15
21
33
40
53
63
71
80
90
4
16
21
34
44
54
64
75
81
91
7
16
21
34
47
55
64
76
82
91
7
16
22
34
48
55
64
76
83
92
8
17
23
35
48
56
65
76
83
93
9
19
26
36
50
59
65
77
86
99
10
19
28
36
51
60
66
77
86
99
12
19
28
37
51
61
66
78
87
99
After sort:
3
13
20
29
38
51
62
66
79
88
Insertionsort
• Although based on the same principle as
Selectionsort (sorting a portion of the array,
adding one element at a time to the sorted
portion), Insertionsort takes a slightly
different approach
• Instead of selecting the smallest element
from the unsorted side, Insertionsort simply
takes the first element and inserts it in place
on the sorted side so that the sorted side is
always in order
Insertionsort algorithm
• Designate first element as sorted
• Take first element from unsorted side and
insert in correct location on sorted side:
– copy new element
– shift elements from end of sorted side to the
right (as necessary) to make space for new
element
Insertionsort algorithm
• Correct location for new element found
when:
– front of array is reached or
– next element to shift is <= new element
• Continue process until last element has
been put into place
The Insertionsort Algorithm
• The
Insertionsort
algorithm
also views
the array as
having a
sorted side
and an
unsorted
side.
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Insertionsort Algorithm
Sorted side
• The sorted
side starts
with just the
first element,
which is not
necessarily
the smallest
element.
Unsorted side
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Insertionsort Algorithm
Sorted side
• The sorted
side grows
by taking
the front
element
from the
unsorted
side...
Unsorted side
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Insertionsort Algorithm
Sorted side
• ...and
inserting it
in the place
that keeps
the sorted
side
arranged
from small
to large.
Unsorted side
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Insertionsort Algorithm
Sorted side
• In this
example, the
new element
goes in front
of the
element that
was already
in the sorted
side.
Unsorted side
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Insertionsort Algorithm
Sorted side
• Sometimes
we are
lucky and
the new
inserted
item
doesn't
need to
move at all.
Unsorted side
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
The Insertionsort Algorithm
Sorted side
• Sometimes
we are
lucky twice
in a row.
Unsorted side
70
60
50
40
30
20
10
0
[1]
[0]
[2]
[1]
[3]
[2]
[4]
[3]
[5]
[4]
[6]
[5]
Implementation of
Insertionsort
public void insertionSort () {
int x, y, tmp;
for (x=1; x<numbers.length; x++)
{
tmp = numbers[x];
for (y=x; y>0 && numbers[y-1] > tmp; y--)
numbers[y] = numbers[y-1];
numbers[y] = tmp;
}
}
Passing Arrays to Methods
• Arrays and objects are reference data
types, so the rules for passing an object to a
method and returning an object from a
method apply to arrays.
• Consider an example method that returns
the index of the smallest element in an array
of real numbers
Passing Arrays to Methods
public int searchMinimum(double[] number) {
int indexOfMinimum = 0;
for (int i = 1; i < number.length; i++){
if (number[i] < number[indexOfMinimum]) {
//found a smaller element
indexOfMinimum = i;
}
}
return indexOfMinimum;
}
Passing Arrays to Methods
double[] arrayOne;
//create and assign values to arrayOne
...
//get the index of the smallest element of arrayOne
int minOne = searchMinimum(arrayOne);
//output the result
System.out.print(“Minimum value in Array One is ”);
System.out.print(arrayOne[minOne] + “at position ” +
minOne);
...
Passing Arrays to Methods
• Remember that when an array is passed to
a method, only its reference is passed.
• A copy of the array is not created in the
method.
Passing Arrays to Methods
• Next we will consider an example in which
we return an array from a method.
• This method inputs double values and
returns the values as an array of double.
Passing Arrays to Methods
public double[] readDoubles() {
double[] number;
int N = Integer.ParseInt(
JOptionPane.showInputDialog(null,
“How many input values?”));
number = new double[N];
for (int i = 0; i<N; i++){
number[i] = Double.parseDouble(
JOptionPane.showInputDialog(null, “Number ” + i));
}
return number;
}
Passing Arrays to Methods
• The readDoubles method is called:
double[] arrayOne;
//assign values to arrayOne
arrayOne = readDoubles();
• Because a new array is created by the
method, we do not have to create an array
from the calling side. Doing so will not
cause an error, but it is a wasteful
operation.
The effect of creating a local array
and not returning it
The effect of creating a local array
and not returning it
The effect of creating a local array
and not returning it
The effect of creating a local array
and not returning it
Two-Dimensional Arrays
• In Java, data may be organized in a twodimensional array.
• A table is an example of a two-dimensional
array.
• In a two-dimensional array, two indices (in
a table, one for the row and one for the
column) are used to refer to the array
element.
Two-Dimensional Arrays
• To declare our example array, we state:
double[][] payScaleTable;
or
double payScaleTable[][];
and create the array as
payScaleTable = new double[4][5];
Examples of information
represented as tables.
Two-Dimensional Arrays
• To refer to an element at the second
column (column 1) of the third row (row 2),
we say
payScaleTable[2][1]
• Nested-for loops are useful for
manipulating two-dimensional arrays.
Accessing an element of a twodimensional array
Two-Dimensional Arrays
• The concept of the two-dimensional array
in Java is just that: a concept. There is no
explicit structure called the “twodimensional array” in Java.
• The two-dimensional array concept is
implemented by using an array of arrays.
Two-Dimensional Arrays
• The sample array creation
payScaleTable = new double[4][5];
is a shorthand for
payScaleTable = new double [4][ ];
payScaleTable[0] = new double [5];
payScaleTable[1] = new double [5];
payScaleTable[2] = new double [5];
and so on.
Statements on the left in sequence
create array of arrays on the right
Continued from previous slide
Two-Dimensional Arrays
• The expression
payScaleTable.length
refers to the length of the array itself.
Two-Dimensional Arrays
• The expression
payScaleTable[1].length
refers to the length of the array stored at row
1 of payScaleTable.
Two-Dimensional Arrays
• An array that is part of another array is
called a subarray.
• An array of arrays may be initialized when
it is created.
Two-Dimensional Arrays
• Subarrays may be different lengths.
• Executing this code:
triangularArray = new double[4][ ];
for (int i = 0; i < 4; i++)
triangularArray[i] = new double [i + 1];
results in an
array that
looks like: