Transcript ppt - AD Book Enterprises

11/30: Sorting and Searching Arrays
•
•
•
•
Look at PassArray.java
Sorting arrays: the bubble sort method
Searching arrays: the linear search
Searching arrays: the binary search
PassArray.java -- pt. 1
//Fig 7.10: PassArray.java
//Passing arrays and individual elements to methods
import java.awt.Container;
import javax.swing.*;
public class PassArray extends JApplet {
JTextArea outputArea;
String output;
public void init()
{
outputArea = new JTextArea();
Container c = getContentPane();
c.add( outputArea );
PassArray.java -- pt. 2
int a[] = { 1, 2, 3, 4, 5 };
output = "Effects of passing entire " +
"array call-by-reference:\n" +
"The values of the original array are:\n";
for ( int i = 0; i < a.length ; i++ )
output += " " + a[ i ];
modifyArray ( a ); //passing the whole array
output+="\n\nValues of the modified array are:\n";
PassArray.java -- pt. 3
for ( int i = 0; i < a.length ; i++ )
output += " " + a[ i ];
output += "\n\nEffects of passing array " +
"element call-by-value:\n" +
"a[3] before modifyElement: " + a[ 3 ];
modifyElement ( a [ 3 ] );
}
output += "\na[3] after modifyElement: " + a [ 3 ];
outputArea.setText ( output );
PassArray.java -- pt. 4
public void modifyArray ( int b[] )
{
for ( int j = 0 ; j < b.length; j++ )
b [ j ] *= 2;
}
}
public void modifyElement ( int e )
{
e *= 2;
}
Sorting Arrays using Bubble Sort
• Reorganizing an array in some
order (low to high, etc.)
• Bubble Sort compares two
values, switches them in the
array positions if appropriate,
and checks the next two values.
3619
3619
3169
3169
Sorting Arrays using Bubble Sort
• In this case, 3 & 6 are compared,
and NOT switched.
• Then, 6 & 1 are compared, then
switched.
• Then 6 & 9 are compared and
NOT switched.
• This is ONLY ONE PASS
through the array.
3619
3619
3169
3169
Sorting Arrays using Bubble Sort
• Core of sorting: an if structure.
• This is nested inside a for loop
to look at each pair of values in
the array.
• This loop in nested inside
another loop to make multiple
passes through the array.
• Look at SortThem & its source
code.
3619
3619
3169
3169
Searching Arrays: Linear Search
• How do you find a particular element value in an
array?
• One way: a linear search.
• The core structure: an if statement in a for loop.
• The for loop gives movement through the array
• The if structure looks for a matching value in the
elements.
Searching Arrays: Linear Search
• The for loop gives movement through the array
• The if structure looks for a matching value in the
elements.
for ( int n = 0 ; n < array.length ; n++ ) {
if ( array [ n ] == key )
return n ;
}
Searching Arrays: Binary Sort
• Go to the middle of the array.
• See if the number you are looking for is higher or
lower, and go to the middle of that side.
• Repeat until found.
• Note that the array must already be sorted!
Searching Arrays: Linear vs. Binary
• A linear search works well for smaller arrays, and
is simpler to understand and troubleshoot.
• A binary search is better for a large array. It is
more efficient in its searching.
1st Program of the Day: BinarySearch
• pg. 291 BinarySearch.java
• Once you get it to work, figure out how it works.
Multiple-Subscripted Arrays
• About BinarySearch.java
• Multiple-Subscripted Arrays
• Program of the Day
BinarySearch.java pt.1
//fig. 7.13: BinarySearch.java: binary search of an array
import java.awt.*;
import java.awt.event.*;
import java.text.*;
import javax.swing.*;
public class BinarySearch extends JApplet
implements ActionListener {
JLabel enterLabel, resultLabel;
JTextField enter, result;
JTextArea output;
int a[];
String display = "";
BinarySearch.java pt.2
public void init ()
{
Container c = getContentPane();
c.setLayout ( new FlowLayout() );
enterLabel = new JLabel ( "Enter key" );
c.add( enterLabel );
enter = new JTextField( 5 );
enter.addActionListener( this );
c.add( enter );
resultLabel = new JLabel ( "Result" );
c.add( resultLabel );
BinarySearch.java pt.3
result = new JTextField( 22 );
result.setEditable( false );
c.add( result );
output = new JTextArea( 6, 60 );
output.setFont(new Font("Courier",Font.PLAIN,12 ) );
c.add( output );
//create array and fill it with even numbers 0-28
a = new int[ 15 ];
}
for ( int i = 0; i < a.length; i++ )
a[ i ] = 2 * i;
BinarySearch.java pt.4
public void actionPerformed ( ActionEvent e )
{
String searchKey = e.getActionCommand();
//initialize display string for new search
display = "Portions of array searched\n";
//perform the binary search
int element = binarySearch ( a, Integer.parseInt (
searchKey ) );
output.setText( display );
}
if ( element != -1 )
result.setText( "Found it in slot " + element );
else
result.setText( "Value not found" );
BinarySearch.java pt.5
//binary search method
public int binarySearch ( int array[], int key )
{
int low = 0;
//low subscript
int high = array.length - 1;//high subscript
int middle;
//middle subscript
while ( low <= high ) {
middle = ( low + high ) / 2;
//The next line displays the part of the array still
//available for searching through for the key.
buildOutput ( low, middle, high );
BinarySearch.java pt.6
if ( key == array[middle] ) //a match
return middle;
else if ( key < array[middle] )
high = middle - 1; //search lower array
else
low = middle + 1;
}
}
return -1;
//searchKey not found
BinarySearch.java pt.7
//build 1 row of output w/ part of the array being processed.
void buildOutput ( int low, int mid, int high )
{
DecimalFormat twoDigits = new DecimalFormat ( "00" );
for ( int i = 0; i < a.length; i++ ) {
if ( i < low || i > high )
display += " ";
else if ( i == mid ) //mark middle element in output
display += twoDigits.format ( a [ i ] ) + "* ";
else
display += twoDigits.format ( a [ i ] ) + " ";
}
}
}
display += "\n";
Multiple-Subscripted Arrays
• Used to represent a table of values, not just a row.
• By convention, the 1st number = row number,
and the 2nd number = column number.
• EX: int sample[] [] = new int [ 4 ] [ 2 ];
might have values like this:
col 0
col 1
row 0
3
1
row 1
2
0
row 2
6
8
row 3
7
5
Multiple-Subscripted Arrays
• Another way to remember: “first the row, then the
position”
• int sample [] [] = { {3,1},{2,0},{6,8},{7,5} };
col 0
col 1
row 0
3
1
row 1
2
0
row 2
6
8
row 3
7
5
Multiple-Subscripted Arrays
• EX: int sample[] [] = new int [ 4 ] [ 2 ];
col 0
col 1
row 0
3
1
row 1
2
0
row 2
6
8
row 3
7
5
sample [3][0] = 7
sample [1][1] = 0
sample [0][1] = ?
sample [2][0] = ?
Multiple-Subscripted Arrays
• But how do you use them?
• Think of them as arrays of arrays (lists of lists).
for ( int i = 0; i < id.length; i++ ) {
for ( int j = 0; j < id[i].length ; j++ ){
g.drawString(“ “ + (id[ i ][ j ]),x,y);
}
}
see StringArray.java
2nd Program of the Day
• pg. 297 DoubleArray.java