One Dimensional Arrays
Large Amounts of Data
An array is a collection of data storage locations, each of which holds the same type of
data. Think of an array as a "box" drawn in memory with a series of subdivisions,
called elements, to store the data. The box below could represent an array of 10 integers.
7 6 5 8 3 9 2 6 10 2
While this array contains only 10 elements, arrays are traditionally used to handle large
amounts of data. It is important to remember that all of the elements in an array must contain
the same type of data.
Let's consider a programming situation "with" and "without" the use of an array:
Without an Array Memory
Suppose you must calculate the average of 3 values:
score1 = [Link]("Enter score one" ); score1 score2 score3
score2 = [Link]("Enter score two");
score3 = [Link]("Enter score three");
average = ( score1 + score2 + score3 ) / 3; Looking good! But what if there were 50
scores? You would need 50 separate
variable names with 50 lines of input.
Yeek!
OK! If you have to deal with a large number of scores, you could use a loop.
sum = 0; score
for ( i = 1; i <= 50; i++ )
{
score = [Link]("Enter score"); Still looking good! But what if, after
sum = sum + score; finding the average, you need to find how
} many scores were above/below the
average = sum / 50.0;
average? Yeek! The only score entered by
the user that is left in memory is the last
one.
With an Array
You can see that dealing with large amounts of data can present potential problems, as
shown above. With an array, however, only one variable name is needed and all entries
will remain in the memory for future use. Here we have an array named scores (one
name, not 50 separate names) with 50 cells to hold the entries. All entries will remain in
the memory for future use. (Not all 50 cells are shown in the array below.)
scores
...
scores is the name of a 50 element (cell) array. The elements are like mailboxes in a
large apartment complex. The "name of the array" is the address of the apartment
complex where all of the mailboxes reside.
Mantra:
The name of the array is the address of the first element of
the array!
Declaring Arrays
Let's declare an array of 10 integer values. Warning!
Array
subscripts start
with the
number 0
(not 1).
This declaration declares an array named num that contains 10
integers. When the compiler encounters this declaration, it
immediately sets aside enough memory to hold all 10 elements.
The square brackets ([ ]) after the "type" indicate that num is going
to be an array of type int rather than a single instance of an int.
Since the new operator creates (defines) the array, it must know the
type and size of the array. The new operator locates a block of
memory large enough to contain the array and associates the array Mantra:
name, num, with this memory block. The name of
the array is the
address of the
first element of
the array.
A program can access each of the array elements (the individual
cells) by referring to the name of the array followed by the
subscript denoting the element (cell). For example, the third
element is denoted num[2].
The subscripts of array elements begin with zero.
The first subscript is always zero and the last subscript's value is
(length - 1), where length designates the number of elements within the array (which is set
when the array is declared).
Consider the following possible (?) subscripts for our array:
num [ 0 ] always OK
num [ 9 ] OK (given the above declaration)
num [ 10 ] illegal (no such cell from this declaration)
num [ -1 ] always NO! (illegal)
num [ 3.5 ] always NO! (illegal)
If the value of an index for an array element is negative, a decimal, or greater than or equal
to the length of the array (remember that the last subscript is array length - 1), an error
message will be ArrayIndexOutOfBoundsException.
If you see this message, immediately check to see how your array is being utilized.
Array Length: When dealing with arrays, it is advantageous to know the number
of elements contained within the array, or the array's "length". This length can be obtained
by using the array name followed by .length. If an array named numbers contains 10
values, the code [Link] will be 10. ** You must remember that the length of
an array is the number of elements in the array, which is one more than the largest
subscript.
[Link] [Link]( )
is used to find the is a method used to find the length
length of an array of a String namedvalue(not an
named value. array)
Initializing Arrays Warning!
Using the assignment operator (=) to initialize an Array subscripts
array (the "drudge" method): start with the
int [ ] temps = new int [ 3 ];
number 0
temps[0] = 78; //filling one element at a time (not 1).
temps[1] = 88;
temps[2] = 53;
Works fine until the array needs to contain a large amount of
data.
Using a for loop and user input to initialize an
array:
int [ ] nums = new int [ 8 ];
for(int ctr = 0; ctr < 8; ctr++)
{
//fill one element at a time
nums[ctr] = [Link]("Please enter a number:");
Initialize at time of declaration - filling by list.
It is possible to fill an array at the time of declaration.
double [ ] temperature = { 13.5, 18.4, 19.6, 21.4};
The array length (size) will be automatically set to the minimum that will hold the given
values. The statement above is equivalent to the following statements:
double [ ] temperature = new double [4];
temperature[0] = 13.5;
temperature[1] = 18.4;
temperature[2] = 19.6;
temperature[3] = 21.4;
Declare an array of strings:
String [ ] list = new String [ 2000];
for ( i = 0; i < 2000; i++)
{
list [ i ] = [Link]("Enter string: " );
}
Parallel Arrays
The following arrays represent the data from a dog show. Notice
that the arrays do not all contain the same "type" of data. It is
often necessary to represent data in a "table" form, as shown
below. Such data, can be stored using parallel arrays. Parallel
arrays are several arrays with the same number of elements that
work in tandem to organize data.
dogname
Wally Skeeter Corky Jessie Sadie
round1
18 22 12 17 15
round2
20 25 16 18 17
**The true beauty of parallel arrays, is that each array
may be of a different data type.
In the data represented above, the first array is the dog's name, the second array is the dog's
score in round 1 of the competition, and the third array is the dog's score in round 2 of the
competition. The arrays are parallel, in that the dog in the first element of the first array has
the scores represented in the first elements of the second and third arrays.
//Printing the dog competition information:
for(int index = 0; index < [Link]; index++)
{
[Link](dogname[index]);
[Link](round1[index]);
[Link](round2[index]);
}
Searching for a Specific Value- Selection Sort
***Definition: A key is a value that you are looking for in an array.
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.
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 search(int [ ] numbers, int key) If the key value is found, the index
{ (subscript) of the location is
for (int index = 0; index < [Link]; index++)
returned. This tells us that the
{ return value x, will be the first
if ( numbers[index] = = key ) integer found such that
return index; //We found it!!!
} numbers [ x ] = key.
// If we get to the end of the loop, a value has not yet There may be
// been returned. We did not find the key in this array. additional keylocations in this
return -1; array beyond this location.
}
Now, suppose you are searching for
the number of times
a specific key value is included in an array:
//Find the number of times the name "Jones" appears in an array of name
public static void main(String[] args)
{
String key = "Jones";
String[ ] list = new String [100]; // instantiate the array
for ( int i=0; i<100; i++) // fill the array
list [ i ]=[Link]("Enter name: ");
int count = search (list, key); // invoke the method
[Link]("Count = " + count);
}
public static int search(String [ ] list, String key) //method to find "Jones"
{
int i, count = 0;
for( i = 0; i< [Link]; i++)
{
if (list [ i ].equals( key ))
count = count+1;
}
return (count);
}
Here is yet another manner of searching:
Searching with BREAK and boolean:
// Search for the number 31 in a set of integers
// This search takes place in main.
// This search could also have been placed in a method.
public class BreakBooleanDemo
{
public static void main(String[ ] args)
{
int[ ] numbers = { 12, 13, 2, 33, 23, 31, 22, 6, 87, 16 };
int key = 31;
int i = 0;
boolean found = false; // set the boolean value to false until the key is found
for ( i = 0; i < [Link]; i++)
{
if (numbers[ i ] == key)
{
found = true;
break;
}
}
if (found) //When found is true, the index of the location of key will be printed.
{
[Link]("Found " + key + " at index " + i + ".");
}
else
{
[Link](key + "is not in this array.");
}
}
}
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.
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").
Consider the following array of integers:
Array of integers, named num, arranged in "ascending order"!!
13 24 34 46 52 63 77 89 91 100
num[0] num[1] num[2] num[3] num[4] num[5] num[6] num[7] num[8] num[9]
We will be searching for the integer 77:
First, find the middle of the array by adding the array subscript of the first value to the
subscript of the last value and dividing by two: (0 + 9) / 2 = 4 Integer division is
used to arrive at the 4th subscript as the middle. (The actual mathematical middle
would be between the 4th and 5th subscripts, but we must work with integer
subscripts.)
The 4th subscript holds the integer 52, which comes before 77. 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
The 7th subscript holds the integer 89, which comes after 77. Now find the middle of
the portion of the array to the right of 52, but to the left of 89. (5 + 6) / 2 = 5
The 5th subscript holds the integer 63, which comes before 77, so we subdivide again
(6 + 6) / 2 = 6 and the 6th subscript holds the integer 77.
Remember: You must start with a pre-sorted array!!!
import [Link].*;
import BreezyGUI.*;
public class BinarySearchExample Binary search method:
{ binarySearch (num, 0, 9, key);
public static void main(String[] args) The arguments/parameters are:
{
array - the name of a sorted array
int key = 77;
int[ ] num = new int [10]; lowerbound - subscript (index) of first
// Fill the array element to search, array[0]
for (int i = 0; i < 10; i++) upperbound - subscript (index) of
num[ i ]=[Link]("Enter integer: "); last element to search, array[9]
//The binary search method
key: item we wish to find.
binarySearch (num, 0, 9, key);
}
//Binary Search Method
// This method accepts a pre-sorted array, the subscript of the starting element for the search,
// the subscript of the ending element for the search,
// and the key number for which we are searching.
public static void binarySearch(int[ ] array, int lowerbound, int upperbound, int key)
{
int position;
int comparisonCount = 1; // counting the number of comparisons (optional)
// To start, find the subscript of the middle position.
position = ( lowerbound + upperbound) / 2;
while((array[position] != key) && (lowerbound <= upperbound))
{
comparisonCount++;
if (array[position] > key) // If the number is > key, ..
{ // decrease position by one.
upperbound = position - 1;
}
else
{
lowerbound = position + 1; // Else, increase position by one.
}
position = (lowerbound + upperbound) / 2;
}
if (lowerbound <= upperbound)
{
[Link]("The number was found in array subscript" + position);
[Link]("The binary search found the number after " + comparisonCount +
"comparisons.");
// printing the number of comparisons is optional
}
else
[Link]("Sorry, the number is not in this array. The binary search made "
+comparisonCount + " comparisons.");
}
}
This method simply prints the result of the search. You may wish to return the result of the
binary search to be used in further investigations. To do so, return the "position" if the value
is found and return a negative number (for example) if the result is not found.
Bubble Sort
In the bubble sort, as elements are sorted they gradually "bubble" (or
rise) to their proper location in the array, like bubbles rising in a glass
of soda. The bubble sort repeatedly compares adjacent elements of
an array. The first and second elements are compared and swapped if
out of order. Then the second and third elements are compared and
swapped if out of order. This sorting process continues until the last
two elements of the array are compared and swapped if out of order.
When this first pass through the array is complete, the bubble sort returns to elements one
and two and starts the process all over again. So, when does it stop? The bubble sort
knows that it is finished when it examines the entire array and no "swaps" are needed
(thus the list is in proper order). The bubble sort keeps track of the occurring swaps by the
use of a flag.
The table below follows an array of numbers before, during, and after a bubble sort
for descending order. A "pass" is defined as one full trip through the array comparing and if
necessary, swapping, adjacent elements. Several passes have to be made through the array
before it is finally sorted.
Array at beginning: 84 69 76 86 94 91
After Pass #1: 84 76 86 94 91 69
After Pass #2: 84 86 94 91 76 69
After Pass #3: 86 94 91 84 76 69
After Pass #4: 94 91 86 84 76 69
After Pass #5 (done): 94 91 86 84 76 69
The bubble sort is an easy algorithm to program, but it is slower than many other sorts. With
a bubble sort, it is always necessary to make one final "pass" through the array to check to see
that no swaps are made to ensure that the process is finished. In actuality, the process is
finished before this last pass is made.
// Bubble Sort Method for Descending Order
public static void BubbleSort( int [ ] num )
{
int j;
boolean flag = true; // set flag to true to begin first pass
int temp; //holding variable
while ( flag )
{
flag= false; //set flag to false awaiting a possible swap
for( j=0; j < [Link] -1; j++ )
{
if ( num[ j ] < num[j+1] ) // change to > for ascending sort
{
temp = num[ j ]; //swap elements
num[ j ] = num[ j+1 ];
num[ j+1 ] = temp;
flag = true; //shows a swap occurred
}
}
}
}
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.
Let's look at our same table of elements using a selection sort
for descending order. Remember, a "pass" is defined as one
full trip through the array comparing and if necessary,
swapping elements.
Array at beginning: 84 69 76 86 94 91
After Pass #1: 84 91 76 86 94 69
After Pass #2: 84 91 94 86 76 69
After Pass #3: 86 91 94 84 76 69
After Pass #4: 94 91 86 84 76 69
After Pass #5 (done): 94 91 86 84 76 69
While being an easy sort to program, the selection sort is one of the least efficient. The
algorithm offers no way to end the sort early, even if it begins with an already sorted list.
// Selection Sort Method for Descending Order
public static void SelectionSort ( int [ ] num )
{
int i, j, first, temp;
for ( i = [Link] - 1; i > 0; i - - )
{
first = 0; //initialize to subscript of first element
for(j = 1; j <= i; j ++) //locate smallest element between positions 1 and i.
{
if( num[ j ] < num[ first ] )
first = j;
}
temp = num[ first ]; //swap smallest found with element in position i.
num[ first ] = num[ i ];
num[ i ] = temp;
}
}