What We Will Cover
Continuations
Homework Questions?
^ top
8.1: Programming With Arrays
Objectives
At the end of the lesson the student will be able to:
- Test array equality
- Compute statistics on arrays of data
- Search an array
- Sort an array
- Choose the best algorithm for searching an array
|
^ top
8.1.1: Using Arrays Interactively
Run-Time Dimensioning
- An entered value can be used to allocate space for an array
- Size of an array is known as its dimension
- Sizing an array at run time is referred to as run-time dimensioning
Example
For Example
- Consider the case of reading user input into an array
- Note that there is no automatic mechanism to detect how many items have been entered
- Programmer must keep track of the progress
import javax.swing.*;
class ArrayInput {
public static void main(String [] args) {
String input = JOptionPane.showInputDialog(
"How many items? ");
int numItems = Integer.parseInt(input);
int[] data = new int[numItems];
fillUp(data);
showArray(data);
System.exit(0);
}
// Fills an array with values from the keyboard
static void fillUp(int data[]) {
String input, msg = "Enter number ";
for (int i = 0; i < data.length; i++) {
input = JOptionPane.showInputDialog(msg
+ (i + 1));
data[i] = (int) Double.parseDouble(input);
}
}
// Displays an array to the screen
static void showArray(int[] values) {
String msg = "You entered " + values.length
+ " numbers:\n";
for (int i = 0; i < values.length; i++) {
msg += values[i] + "\n";
}
JOptionPane.showMessageDialog(null, msg);
}
}
Check Yourself
- When is the size of the array decided?
- What does the
data array contain before the user enters any values?
- What is the value of
data.length after one item has been entered?
- How do we know how many items have been entered by the user?
^ top
8.1.2: Testing Array Equality
Using == With Array Names
- Remember that arrays are objects
- Thus, array variables are reference types
- Tests using
== checks if the memory addresses are the same
if (a == b)
For example, what does the following code print?
public class ArrayChecker {
public static void main(String[] args) {
int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
if (a == b) {
System.out.println("a == b");
} else {
System.out.println("a != b");
}
}
}
Both arrays have the same elements
However, they are stored at different locations in memory
Thus, they do not have the same memory address
Testing Array Elements for Equality
- To test array elements for equality, need to check each element
- Define an equals method that returns true if and only if all the array elements are equal
- Arrays must also be the same length
- Updating our original code:
public class ArrayTester {
public static void main(String[] args) {
int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
if (a == b) {
System.out.println("a == b");
} else {
System.out.println("a != b");
}
if (equals(a, b) == true) {
System.out.println("a equals b: ");
} else {
System.out.println("a not equal to b");
}
}
public static boolean equals(int[] a, int[] b) {
boolean match = true; //tentatively
if (a.length != b.length) {
match = false;
} else {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) match = false;
}
}
return match;
}
}
^ top
8.1.3: Calculating Statistics on Arrays
- Can use a loop to access every item in an array
public class ArraySum {
public static void main(String [] args) {
int[] data = {1, 2, 3, 4, 5};
int sum = 0;
for (int i = 0; i < data.length; i++) {
sum = sum + data[i];
System.out.print(data[i] + ", ");
}
System.out.println("\nsum = " + sum);
}
}
What code would we add to show the average of the array values?
What would we change to find the maximum array value?
How would we find the minimum array value?
What is the easiest way to initialize minimum and maximum values?
Restricting the Range
- We can choose to calculate statistics over a portion of an array
- For example, the following finds a minimum between
start and end
- Note that it does not return a value, but rather an array index
- You use the array index to look up the minimum value
static int findMin(int[] data, int start, int end) {
int indexOfMin = start;
for (int i = start + 1; i <= end; i++) {
if (data[i] < data[indexOfMin]) {
indexOfMin = i;
}
}
return indexOfMin;
}
^ top
8.1.4: Searching an Array
- Many techniques for searching an array for a particular value
- Sequential search:
- Start at the beginning of the array
- Compare each value in sequence
- If value is found, then exit
- Continue until you reach the end of the array
public class Array9Finder {
public static void main(String [] args) {
int[] data = {12, -3, 9, -5, 10};
final int valueToFind = 9;
boolean found = false;
int count = 0;
while ((!found) && (count < data.length)) {
if (valueToFind == data[count]) {
found = true;
}
count++;
}
if (found) {
System.out.print("Found ");
} else {
System.out.print("Did not find ");
}
System.out.println(valueToFind + " in "
+ count + " comparisons");
}
}
Would it be any faster to start searching at the end of an array?
If an array is sorted, then we can program faster methods -- binary search
^ top
8.1.5: Sorting an Array
- Sorting is a common task for computers, for example:
- Sort numbers in ascending order
- Sort numbers in descending order
- Sort strings in alphabetic order
- Many different algorithms for sorting, including:
- Bubble sort - move item up until in right place
- Insertion sort - add elements to list one at a time
- Selection sort - pick 1st, then 2nd, etc.
- Quick sort - divide and conquer
Selection Sort
- Selection sort is one of the easiest -- but not the most efficient
- General algorithm:
- Find the smallest element
- Swap with the first element
- Find the smallest element in the rest of the list
- Swap with the first element of the rest of the list
- Repeat until the list is sorted
| Pass |
a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
a[5] |
a[6] |
| Original |
10 |
7 |
29 |
14 |
-4 |
-12 |
21 |
| First |
-12 |
7 |
29 |
14 |
-4 |
10 |
21 |
| Second |
-12 |
-4 |
29 |
14 |
7 |
10 |
21 |
| Third |
-12 |
-4 |
7 |
14 |
29 |
10 |
21 |
| Fourth |
-12 |
-4 |
7 |
10 |
29 |
14 |
21 |
| Fifth |
-12 |
-4 |
7 |
10 |
14 |
29 |
21 |
| Sixth |
-12 |
-4 |
7 |
10 |
14 |
21 |
29 |
- How many passes were needed for a seven element array?
Selection Sort Code
- Following is selection sort code
- Have added some statements to show action for each pass
public class SelectionSort {
public static void main(String [] args) {
int[] a = {10, 7, 29, 14, -4, -12, 21};
System.out.print("Original array: ");
showArray(a);
sort(a);
System.out.print("\nSorted array: ");
showArray(a);
}
public static void showArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + ", ");
}
System.out.println();
}
static void sort(int[] a) {
int index, indexOfMin;
for (index = 0; index < a.length - 1; index++) {
indexOfMin = findMin(a, index, a.length - 1);
swap(a, index, indexOfMin);
System.out.print("Pass#" + index + ": ");
showArray(a);
}
}
static int findMin(int[] a, int start, int end) {
int indexOfMin = start;
for (int i = start + 1; i <= end; i++) {
if (a[i] < a[indexOfMin]) {
indexOfMin = i;
}
}
return indexOfMin;
}
static void swap(int[] a, int first, int second) {
System.out.println("\nSwapping " + a[first]
+ " with " + a[second]);
int temp = a[first];
a[first] = a[second];
a[second] = temp;
}
}
- Note that every element in the array must have a value
- Can the array have duplicate items?
- Also note that the larger task was broken into smaller tasks using methods
- Helps to organize program and improve clarity
What About Bubble Sort?
- Another sorting algorithm that is easy to understand and use
- General algorithm:
- Make
array.length passes through the array
- For each pass, compare each array element with the next element
- If the current element is larger than the next one, swap them
- Not an efficient sorting algorithm
- Sometimes simple algorithms perform poorly
- Simple algorithms still useful because: easy to program and understand
- If better performance is needed, can replace with a better algorithm
- More information: Sorting Algorithms
- Includes Java source code
^ top
8.1.6: Binary Search
- Once an array is sorted, can use binary search to find an item
- Binary search is much faster than sequential search
Binary Search Algorithm
- A key value is searched for among the values stored in the array.
- Two index variables
lowIdx and highIdx are used to limit the scope of the search.
- The search proceeds until the element searched for is found or the scope between
lowIdx and highIdx is exhausted.
- The index
middleIdx is computed as
(lowIdx + highIdx) / 2.
- If
key = data[middleIdx] the search is successful.
- If
key < data[middleIdx], highIdx is lowered to middleIdx.
If key > data[middleIdx], lowIdx is raised to middleIdx. - If the scope between
lowIdx and highIdx is exhausted, the search is unsuccessful.
- Demonstration applet: BinarySearch
Binary Search Code
public class BinarySearch {
public static void main(String [] args) {
int[] a = {-12, -4, 7, 10, 14, 21, 29};
int key = 14;
System.out.print("Searching array: ");
showArray(a);
int index = binarySearch(a, key);
System.out.println("Index of " + key
+ " = " + index);
}
static void showArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + ", ");
}
System.out.println();
}
// find the index of key in array a
// return -1 if key is not found
static int binarySearch(int[] a, int key) {
int step = 0;
int lowIdx = 0;
int highIdx = a.length - 1;
int middleIdx;
while (lowIdx <= highIdx) {
step++;
middleIdx = (lowIdx + highIdx) / 2;
System.out.println("Step#" + step
+ " lowIdx=" + lowIdx
+ " highIdx=" + highIdx
+ " middleIdx=" + middleIdx);
if (a[middleIdx] == key) {
return middleIdx; // just right
} else if (a[middleIdx] < key) {
lowIdx = middleIdx + 1; // too small
} else {
highIdx = middleIdx - 1; // too big
}
}
return -1; // not found
}
}
How Much Faster is Binary Search?
- Given the sorted array:
| a[0] |
a[1] |
a[2] |
a[3] |
a[4] |
a[5] |
a[6] |
| -12 |
-4 |
7 |
10 |
14 |
21 |
29 |
- How many steps to find the value of 14 using sequential search?
- How many steps to find the value of 14 using binary search?
- On average for an array of n elements:
- Sequential search takes n / 2 steps
- Binary search takes 2 * log2(n) + 2 steps maximum
- Translating to some array sizes:
| Array Size |
floor(log2(n)) + 1 |
| 1 |
1 |
| 10 |
4 |
| 100 |
7 |
| 1000 |
10 |
| 10,000 |
14 |
- Binary search quickly becomes worth the effort of its implementation
- Binary search is one algorithm a programming professional should know!
^ top
8.1.7: Summary
- You can easily enter values into an array for later processing
- A "partially filled array" is one in which values are stored in an initial segment of the array
- Arrays work well with loops to sum data and calculate other statistics
- Can search arrays sequentially to find a value
- Sorting algorithms can sort an array into ascending or descending order
- If an array is sorted, can use binary search to speed the search process
^ top
Exercise 8.1
- Start a text file named exercise8.txt.
- Prepare the exercise header as described in the HowTo on submitting exercises
- Label this exercise: Exercise 8.1
- Submit all exercises for this lesson in one file unless instructed otherwise
- Complete the following and record the answers to any questions in exercise8.txt.
Specifications
Show the contents of the following array after each pass of SelectionSort. Record the results in exercise8.txt.
int[] array = {9, 21, -7, 2, 87, -19, 47}
^ top
8.2: Midterm Preparation
Objectives
At the end of the lesson the student will be able to:
- Discuss how to prepare for the first midterm exam
- Describe how to take the first midterm exam
|
^ top
8.2.1: About the Exam
- You must attend the exam or you will receive a score of zero (0)
- Except by prior arrangement with the instructor
- I am using WebCT to administer the test
- The exam is closed books and closed notes
- However, you may have one 3" x 5" card of notes for the exam
- You must turn in your 3" x 5" card after the exam
- You may use your computer, but only to take the exam in WebCT
- You may have a sheet of blank scratch paper
- You may NOT use the computer to compile or run programs
- You may NOT use the computer to view documents on the Internet
- You may NOT use a calculator or other electronic device
- You may NOT communicate with anyone but the instructor during the exam
^ top
8.2.2: Recommended Preparation
- Work through the Practice Midterm Exam questions in WebCT
- Working the problems in groups is encouraged
- Get explanations for anything you do not understand
- Review your notes and prepare your 3" x 5" card
- Review your homework assignments and solutions
- Review your CodeLab exercises
- You should be prepared to write short programs
- Mathematical expressions
- Conditional statements
- Ask-first loops
- Counter-controlled loops
- Sentinel-controlled loops
- Method definitions
- User I/O
- A few more tips:
- I avoid using true/false questions
- I try to use questions containing actual code
- More quiz tips: TAKING MULTIPLE –CHOICE TESTS
^ top
8.2.3: Exam Taking Tips
- Save after every answer -- you can always choose another answer
- If you get stuck on a question, make your best guess and return later
- If you are equally uncertain between two choices, go with first impression
- You do not need to comment code for tests and exams
- Unless specifically instructed to in the exam question
- Use the full time available
- More quiz tips: Basic Rules For Taking a Multiple-Choice Test
^ top
8.2.4: Questions and Answers
^ top
Wrap Up
^ top
Home
| WebCT
| Announcements
| Schedule
| Expectations
| Course info
Help
| FAQ's
| HowTo's
| Links
Last Updated: October 23 2004 @21:51:14
|
