An array is a fundamental datastructure category, and a building block for more complex datastructures. In this second part of my Java 101 introduction to datastructures and algorithms, you will learn how arrays are understood and used in Java programming. I introduce the concept of an array and how arrays are represented in the Java language. Then you'll learn about onedimensional arrays and the three ways that you can introduce them to your Java programs. Finally, we'll explore five algorithms used to search and sort onedimensional arrays.
Note that this article builds on Datastructures and algorithms, Part 1, which introduced the theoretical side of datastructures and the algorithms associated with them. That article includes an indepth discussion of algorithms and how to use space and time complexity factors to evaluate and select the most efficient algorithm for your Java program. This article will be much more handson, and assumes you have already read and digested Part 1.
What is an array?
An array is a sequence of elements where each element is associated with at least one index. An element is a group of memory locations that store a single data item. An index is a nonnegative integer, which in this case is used to uniquely identify an element. This relationship is similar to how a box number uniquely identifies a house on a given street.
The number of indexes associated with any element is the array's dimension. In this article, we'll be talking about onedimensional arrays. The next article in this series introduces multidimensional arrays.
Java supports arrays. Each element occupies the same number of bytes, and the exact number depends on the type of the element's data item. Furthermore, all elements share the same type.
Onedimensional arrays
The simplest kind of array has one dimension. A onedimensional array associates each element with one index. Onedimensional arrays are used to store lists of data items. There are three techniques for creating onedimensional arrays in Java:
 Use only an initializer
 Use only keyword
new
 Use keyword
new
with an initializer
Creating a onedimensional array with only an initializer
Here is the syntax to create a onedimensional array using just an initializer:
'{' [expr (',' expr)*] '}'
This syntax states that a onedimensional array is an optional, commaseparated list of expressions appearing between open and close brace characters. Furthermore, all expressions must evaluate to compatible types. For example, in a twoelement onedimensional array of double
s, both elements might be of type double
, or one element might be a double
while the other element is a float
or an integer type (such as int
).
Example:
{ 'J', 'a', 'v', 'a' }
Creating a onedimensional array with the keyword new
The keyword new
allocates memory for an array and returns its reference. Here's the syntax for this approach:
'new' type '[' int_expr ']'
This syntax states that a onedimensional array is a region of (positive) int_expr
elements that share the same type
. Furthermore, all elements are zeroed, and are interpreted as 0
, 0L
, 0.0F
, 0.0
, false
, null
, or '\u0000'
.
Example:
new char[4]
Creating a onedimensional array with the keyword new and an initializer
Here is the syntax to create a onedimensional array using the keyword new
with an initializer. As you see, it blends the syntax from the previous two approaches:
'new' type '[' ']' '{' [expr (',' expr)*] '}'
In this case, because the number of elements can be determined from the commaseparated list of expressions, it isn't necessary (or allowed) to provide an int_expr
between the square brackets.
Example:
new char[] { 'J', 'a', 'v', 'a' }
Something to note is that the syntax for creating an array with only an initializer is no different in effect from the syntax using an initializer and a keyword. The initializeronly syntax is an example of syntactic sugar, which means syntax that makes the language sweeter, or easier, to use.
Array variables
By itself, a newlycreated onedimensional array is useless. Its reference must be assigned to an array variable of a compatible type, either directly or via a method call. The following two lines of syntax show how you would declare this variable:
type var_name '[' ']'
type '[' ']' var_name
Each syntax declares an array variable that stores a reference to a onedimensional array. Although you can use either syntax, placing the square brackets after type
is preferred.
Examples:
char[] name1 = { 'J', 'a', 'v', 'a' };
char[] name2 = new char[4];
char[] name3 = new char[] { 'J', 'a', 'v', 'a' };
output(new char[] { 2, 3 }); // output({ 2, 3 }); results in a compiler error
static void output(char[] name)
{
// ...
}
In the examples, name1
, name2
, name3
, and name
are array variables. The single pair of square brackets states that each stores references to onedimensional arrays.
Keyword char
indicates that each element must store a value of char
type. However, you can specify a nonchar
value if Java can convert it to a char
. For example, char[] chars = { 'A', 10 };
is legal because 10
is a small enough positive int
(meaning that it fits into the char
range of 0 through 65535) to be converted to a char
. In contrast, char[] chars = { 'A', 80000 };
would be illegal.
An array variable is associated with a .length
property that returns the length of the associated onedimensional array as a positive int
; for example, name1.length
returns 4.
Given an array variable, you can access any element in a onedimensional array by specifying an expression that agrees with the following syntax:
array_var '[' index ']'
Here, index
is a positive int
that ranges from 0 (Java arrays are zerobased) to one less than the value returned from the .length
property.
Examples:
char ch = names[0]; // Get value.
names[1] = 'A'; // Set value.
If you specify a negative index or an index that is greater than or equal to the value returned by the array variable's .length
property, Java creates and throws a java.lang.ArrayIndexOutOfBoundsException
object.
Algorithms for searching and sorting
It is a very common task to search onedimensional arrays for specific data items, and there are a variety of algorithms for doing it. One of the most popular search algorithms is called Linear Search. Another option is Binary Search, which is usually more performant but also more demanding: in order to use Binary Search, the array's data items must first be sorted, or ordered. Although not very performant, Bubble Sort, Selection Sort, and Insertion Sort are all simple algorithms for sorting a onedimensional array. Each works well enough for shorter arrays.
The next sections introduce each of these algorithms for searching and sorting onedimensional arrays.
Linear Search
Linear Search searches a onedimensional array of n data items for a specific one. It functions by comparing data items from the lowest index to the highest until it finds the specified data item, or until there are no more data items to compare.
The following pseudocode expresses Linear Search used for a onedimensional array of integers:
DECLARE INTEGER i, srch = ...
DECLARE INTEGER x[] = [ ... ]
FOR i = 0 TO LENGTH(x)  1
IF x[i] EQ srch THEN
PRINT "Found ", srch
END
END IF
NEXT i
PRINT "Not found", srch
END
Consider a onedimensional unordered array of five integers [ 1, 4, 3, 2, 6 ], where integer 1 is located at index 0 and integer 6 is located at index 4. The pseudocode performs the following tasks to find integer 3 in this array:
 Compare the integer at index 0 (1) with 3.
 Because there's no match, compare the integer at index 1 (4) with 3.
 Because there's still no match, compare the integer at index 2 (3) with 3.
 Because there's a match, print Found 3 and exit.
Linear Search has a time complexity of O(n), which is pronounced "Big Oh of n." For n data items, this algorithm requires a maximum of n comparisons. On average, it performs n/2 comparisons. Linear Search offers linear performance.
Explore Linear Search
To let you experiment with Linear Search, I've created the LinearSearch
Java application in Listing 1.
Listing 1. LinearSearch.java
{
public static void main(String[] args)
{
// Validate command line arguments count.
if (args.length != 2)
{
System.err.println("usage: java LinearSearch integers integer");
return;
}
// Read integers from first commandline argument. Return if integers
// could not be read.
int[] ints = readIntegers(args[0]);
if (ints == null)
return;
// Read search integer; NumberFormatException is thrown if the integer
// isn't valid.
int srchint = Integer.parseInt(args[1]);
// Perform the search and output the result.
System.out.println(srchint + (search(ints, srchint) ? " found"
: " not found"));
}
private static int[] readIntegers(String s)
{
String[] tokens = s.split(",");
int[] integers = new int[tokens.length];
for (int i = 0; i < tokens.length; i++)
integers[i] = Integer.parseInt(tokens[i]);
return integers;
}
private static boolean search(int[] x, int srchint)
{
for (int i = 0; i < x.length; i++)
if (srchint == x[i])
return true;
return false;
}
}
The LinearSearch
application reads a commaseparated list of integers from its first commandline argument. It searches the array for the integer identified by the second commandline argument, and outputs a found/not found message.
To experiment with this application, start by compiling Listing 1:
javac LinearSearch.java
Next, run the resulting application as follows:
java LinearSearch "4,5,8" 5
You should observe the following output:
5 found
Run the resulting application a second time, as follows:
java LinearSearch "4,5,8" 15
You should observe the following output:
15 not found
Binary Search
The Binary Search algorithm searches an ordered onedimensional array of n data items for a specific data item. This algorithm consists of the following steps:
 Set low and high index variables to the indexes of the array's first and last data items, respectively.
 Terminate if the low index is greater than the high index. The searchedfor data item is not in the array.
 Calculate the middle index by summing the low and high indexes and dividing the sum by 2.
 Compare the searchedfor data item with the middleindexed data item. Terminate if they are the same. The searchedfor data item has been found.
 If the searchedfor data item is greater than the middleindexed data item, set the low index to the middle index plus one and transfer execution to Step 2. Binary Search repeats the search in the upper half of the array.
 The searchedfor data item must be smaller than the middleindexed data item, so set the high index to the middle index minus one and transfer execution to Step 2. Binary Search repeats the search in the lower half of the array.
Here is pseudocode representing the Binary Search algorithm for a onedimensional array of integers:
DECLARE INTEGER x[] = [ ... ]
DECLARE INTEGER loIndex = 0
DECLARE INTEGER hiIndex = LENGTH(x)  1
DECLARE INTEGER midIndex, srch = ...
WHILE loIndex LE hiIndex
midIndex = (loIndex + hiIndex) / 2
IF srch GT x[midIndex] THEN
loIndex = midIndex + 1
ELSE
IF srch LT x[midIndex] THEN
hiIndex = midIndex  1
ELSE
EXIT WHILE
END IF
END WHILE
IF loIndex GT hiIndex THEN
PRINT srch, " not found"
ELSE
PRINT srch, " found"
END IF
END
Binary Search isn't hard to understand. For example, consider a onedimensional ordered array of six integers [ 3, 4, 5, 6, 7, 8 ], where integer 3 is located at index 0 and integer 8 is located at index 5. The pseudocode does the following to find integer 6 in this array:
 Obtain the low index (0) and high index (5).
 Calculate the middle index: (0+5)/2 = 2.
 Because the integer at index 2 (5) is less than 6, set the low index to 2+1 = 3.
 Calculate the middle index: (3+5)/2 = 4.
 Because the integer at index 4 (7) is greater than 6, set the high index to 41 = 3.
 Calculate the middle index: (3+3)/2 = 3.
 Because the integer at index 3 (6) equals 6, print 3 found and exit.
Binary Search has a time complexity of O(log_{2}n), which is pronounced "Big Oh of log n to the base 2." For n data items, Binary Search requires a maximum of 1+log_{2}n comparisons, making this algorithm vastly more efficient than Linear Search, in most cases. The algorithm offers logarithmic performance (for more about logarithmic performance, see Figure 3 in Part 1 of this series).
Listing 2 is a BinarySearch
Java application that lets you experiment with Binary Search.
Listing 2. BinarySearch.java
{
public static void main(String[] args)
{
// Validate command line arguments count.
if (args.length != 2)
{
System.err.println("usage: java BinarySearch integers integer");
return;
}
// Read integers from first commandline argument. Return if integers
// could not be read.
int[] ints = readIntegers(args[0]);
if (ints == null)
return;
// Read search integer; NumberFormatException is thrown if the integer
// isn't valid.
int srchint = Integer.parseInt(args[1]);
// Perform the search and output the result.
System.out.println(srchint + (search(ints, srchint) ? " found"
: " not found"));
}
private static int[] readIntegers(String s)
{
String[] tokens = s.split(",");
int[] integers = new int[tokens.length];
for (int i = 0; i < tokens.length; i++)
integers[i] = Integer.parseInt(tokens[i]);
return integers;
}
private static boolean search(int[] x, int srchint)
{
int hiIndex = x.length  1, loIndex = 0, midIndex;
while (loIndex <= hiIndex)
{
midIndex = (loIndex + hiIndex) / 2;
if (srchint > x[midIndex])
loIndex = midIndex + 1;
else
if (srchint < x[midIndex])
hiIndex = midIndex  1;
else
return true;
}
return false;
}
}
The BinarySearch
application reads a commaseparated list of integers from its first commandline argument. It searches the array for the integer identified by the second commandline argument, and outputs a found/not found message.
To explore the Binary Search algorithm, do the following:
Compile the code in Listing 2 as follows:
javac BinarySearch.java
Run the resulting application as follows:
java BinarySearch "4,5,8" 5
You should observe the following output:
5 found
Run the resulting application a second time, as follows:
java BinarySearch "4,5,8" 15
You should observe the following output:
15 not found
Bubble Sort
The Bubble Sort algorithm orders a onedimensional array of n data items into ascending or descending order. An outer loop makes n1 passes over the array. Each pass uses an inner loop to exchange data items such that the next smallest (ascending sort) or largest (descending sort) data item "bubbles" toward the beginning of the array.
The "bubbling" action occurs in the inner loop, where each iteration compares the passnumbered data item with each successive data item. If a successor data item is smaller (ascending sort) or larger (descending sort) than the passnumbered data item, the successor data item is exchanged with the passnumbered data item.
Here is pseudocode representing Bubble Sort in a onedimensional array of integers/ascending sort context:
DECLARE INTEGER i, pass
DECLARE INTEGER x[] = [ ... ]
FOR pass = 0 TO LENGTH(x)  2
FOR i = LENGTH(x)  1 DOWNTO pass + 1
IF x[i] LT x[pass] THEN // switch to > for descending sort
EXCHANGE x[i], x[pass]
END IF
NEXT i
NEXT pass
END
Bubble Sort is fairly easy to understand. For example, consider a onedimensional, unordered array of four integers: [ 18, 16, 90, 3 ], where integer 18 is located at index 0 and integer 3 is located at index 3. When requested to sort this array into ascending order, Bubble Sort would execute as follows:
Pass 0 Pass 1 Pass 2
====== ====== ======
18 16 90 3 3 16 90 18 3 16 90 18
^ ^ ^ ^ ^ ^
     
  
3 16 90 18 3 16 90 18 3 16 18 90
^ ^ ^ ^
   
 
3 16 90 18 3 16 90 18
^ ^
 

3 16 90 18
In terms of comparisons and also in terms of exchanges, Bubble Sort has a time complexity of O(n^{2}), which is pronounced "Big Oh of n squared." Bubble Sort offers quadratic performance, which isn't a problem for shorterlength arraysespecially when you consider that Bubble Sort is easy to code. (See Part 1 for more about quadratic performance.)
The BubbleSort
Java application in Listing lets you experiment with Bubble Sort.
Listing 3. BubbleSort.java
{
public static void main(String[] args)
{
// Validate command line arguments count.
if (args.length != 1)
{
System.err.println("usage: java BubbleSort integers");
return;
}
// Read integers from first commandline argument. Return if integers
// could not be read.
int[] ints = readIntegers(args[0]);
if (ints == null)
return;
// Output integer array's length and number of inversions statistics to
// standard output device.
System.out.println("N = " + ints.length);
int inversions = 0;
for (int i = 0; i < ints.length  1; i++)
for (int j = i + 1; j < ints.length; j++)
if (ints[i] > ints[j])
inversions++;
System.out.println("I = " + inversions);
// Output unsorted integer values to standard output, sort the array,
// and output sorted values to standard output.
dump(ints);
sort(ints);
dump(ints);
}
static void dump(int[] a)
{
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.print('\n');
}
static int[] readIntegers(String s)
{
String[] tokens = s.split(",");
int[] integers = new int[tokens.length];
for (int i = 0; i < tokens.length; i++)
integers[i] = Integer.parseInt(tokens[i]);
return integers;
}
static void sort(int[] x)
{
for (int pass = 0; pass < x.length  1; pass++)
for (int i = x.length  1; i > pass; i)
if (x[i] < x[pass])
{
int temp = x[i];
x[i] = x[pass];
x[pass] = temp;
}
}
}
BubbleSort
reads a commaseparated list of integers from its commandline argument. It outputs the array length, calculates and outputs the number of inversions (larger items to the left of smaller items in the unsorted array), outputs the unsorted array, sorts the array, and outputs the sorted array. (Selection Sort and Insertion Sort, which I'll introduce next, behave similarly.)
Compile Listing 3 as follows:
javac BubbleSort.java
Run the resulting application as follows:
java BubbleSort "18,16,90,3"
You should observe the following output:
N = 4
I = 4
18 16 90 3
3 16 18 90
Selection Sort
The Selection Sort algorithm orders a onedimensional array of n data items into ascending order or descending order. An outer loop makes n1 passes over the array. Each pass uses an inner loop to find the next smallest (ascending sort) or largest (descending sort) data item, which is exchanged with the passnumbered data item.
Selection Sort assumes that the data item at the passnumbered index is the smallest (ascending sort) or the largest (descending sort) of the remaining data items. It searches the rest of the array for a data item that's smaller/larger than this data item, and performs an exchange at the end of the search when a smaller/larger data item is found.
The following pseudocode expresses Selection Sort in a onedimensional array of integers/ascending sort context:
DECLARE INTEGER i, min, pass
DECLARE INTEGER x[] = [ ... ]
FOR pass = 0 TO LENGTH(x)  2
min = pass
FOR i = pass + 1 TO LENGTH(x)  1
IF x[i] LT x[min] THEN
min = i
END IF
NEXT i
IF min NE pass THEN
EXCHANGE x[min], x[pass]
END IF
NEXT pass
END
Selection Sort is fairly easy to understand. For example, consider a onedimensional unordered array of four integers: [ 18, 16, 90, 3 ], where integer 18 is located at index 0 and integer 3 is located at index 3. When requested to sort this array into ascending order, the Selection Sort pseudocode performs the sort as follows:
Pass 0 Pass 1 Pass 2
====== ====== ======
18 16 90 3 3 16 90 18 3 16 90 18
^ ^ ^
  
min = 0 min = 1 min = 2
18 16 90 3 3 16 90 18 3 16 90 18
^ ^ ^
  
16 < 18, min = 1 90 > 16, min = 1 18 < 90, min = 3
^ ^
18 16 90 3 3 16 90 18  
^ ^ 
  3 16 18 90
90 > 16, min = 1 18 > 16, min = 1
18 16 90 3
^

3 < 16 min = 3
^ ^
 

3 16 90 18
Selection Sort has a time complexity of O(n^{2}) comparisons and O(n) exchanges. The algorithm offers quadratic performance in terms of comparisons and linear performance in terms of exchanges, which makes it somewhat more efficient than Bubble Sort.
Listing 4 shows the SelectionSort
application in Java code.
Listing 4. SelectionSort.java
public final class SelectionSort
{
public static void main(String[] args)
{
// Validate command line arguments count.
if (args.length != 1)
{
System.err.println("usage: java SelectionSort integers");
return;
}
// Read integers from first commandline argument. Return if integers
// could not be read.
int[] ints = readIntegers(args[0]);
if (ints == null)
return;
// Output integer array's length and number of inversions statistics to
// standard output device.
System.out.println("N = " + ints.length);
int inversions = 0;
for (int i = 0; i < ints.length  1; i++)
for (int j = i + 1; j < ints.length; j++)
if (ints[i] > ints[j])
inversions++;
System.out.println("I = " + inversions);
// Output unsorted integer values to standard output, sort the array,
// and output sorted values to standard output.
dump(ints);
sort(ints);
dump(ints);
}
static void dump(int[] a)
{
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.print('\n');
}
static int[] readIntegers(String s)
{
String[] tokens = s.split(",");
int[] integers = new int[tokens.length];
for (int i = 0; i < tokens.length; i++)
integers[i] = Integer.parseInt(tokens[i]);
return integers;
}
static void sort(int[] x)
{
for (int pass = 0; pass < x.length  1; pass++)
{
int min = pass;
for (int i = pass + 1; i < x.length; i++)
if (x[i] < x[min])
min = i;
if (min != pass)
{
int temp = x[min];
x[min] = x[pass];
x[pass] = temp;
}
}
}
}
Compile Listing 4 as follows:
javac SelectionSort.java
Run the resulting application as follows:
java SelectionSort "18,16,90,3"
You should observe the following output:
N = 4
I = 4
18 16 90 3
3 16 18 90
Insertion Sort
The Insertion Sort algorithm orders a onedimensional array of n data items into ascending order or descending order. An outer loop makes n1 passes over the array. Each pass selects the next data item to be inserted into the appropriate position. It uses an inner loop to find this position, shifting data items to make room.
Insertion Sort begins by dividing the datastructure into sorted and unsorted sections. Initially, the sorted section contains the data item at index 0; the unsorted section contains all other data items. During the sort, each unsorted section data item is inserted into the proper position in the sorted section and the unsorted section shrinks by one data item.
Here is pseudocode for the Insertion Sort algorithm in a onedimensional array of integers, where you are doing an ascending sort:
DECLARE INTEGER a, i, j
DECLARE INTEGER x[] = [ ... ]
FOR i = 1 TO LENGTH(x)  1
a = x[i]
j = i
WHILE j GT 0 AND x[j  1] GT a
x[j] = x[j  1]
j = j  1
END WHILE
x[j] = a
NEXT i
END
Like Bubble Sort, Insertion Sort is fairly easy to understand. For example, consider a onedimensional unordered array of four integers: [ 18, 16, 90, 3 ], where integer 18 is located at index 0 and integer 3 is located at index 3. When instructed to sort this array into ascending order, the algorithm performs the sort as follows:
i = 1 i = 2 i = 3
===== ===== =====
18  16 90 3 16 18  90 3 16 18 90  3 3 16 18 90
^ ^ ^
  
a,j a,j a,j
The sorted section appears on the left and initially consists of [ 18 ]. The unsorted section appears on the right and initially consists of [ 16, 90, 3 ].
Insertion Sort has a time complexity of O(n) comparisons for the best case (data is already sorted or nearly sorted) and O(n^{2}) for the average and worst cases. The algorithm offers linear (best case) or quadratic (average/worst case) performance.
Listing 5 shows the source code for the InsertionSort
application.
Listing 5. InsertionSort.java
{
public static void main(String[] args)
{
// Validate command line arguments count.
if (args.length != 1)
{
System.err.println("usage: java InsertionSort integers");
return;
}
// Read integers from first commandline argument. Return if integers
// could not be read.
int[] ints = readIntegers(args[0]);
if (ints == null)
return;
// Output integer array's length and number of inversions statistics to
// standard output device.
System.out.println("N = " + ints.length);
int inversions = 0;
for (int i = 0; i < ints.length  1; i++)
for (int j = i + 1; j < ints.length; j++)
if (ints[i] > ints[j])
inversions++;
System.out.println("I = " + inversions);
// Output unsorted integer values to standard output, sort the array,
// and output sorted values to standard output.
dump(ints);
sort(ints);
dump(ints);
}
static void dump(int[] a)
{
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.print('\n');
}
static int[] readIntegers(String s)
{
String[] tokens = s.split(",");
int[] integers = new int[tokens.length];
for (int i = 0; i < tokens.length; i++)
integers[i] = Integer.parseInt(tokens[i]);
return integers;
}
static void sort(int[] x)
{
int j, a;
// For all integer values except the leftmost value ...
for (int i = 1; i < x.length; i++)
{
// Get integer value a.
a = x[i];
// Get index of a. This is the initial insert position, which is
// used if a is larger than all values in the sorted section.
j = i;
// While values exist to the left of a's insert position and the
// value immediately to the left of that insert position is
// numerically greater than a's value ...
while (j > 0 && x[j  1] > a)
{
// Shift left value  x[j  1]  one position to its right 
// x[j].
x[j] = x[j  1];
// Update insert position to shifted value's original position
// (one position to the left).
j;
}
// Insert a at insert position (which is either the initial insert
// position or the final insert position), where a is greater than
// or equal to all values to its left.
x[j] = a;
}
}
}
Compile Listing 5 as follows:
javac InsertionSort.java
Run the resulting application as follows:
java InsertionSort "18,16,90,3"
You should observe the following output:
N = 4
I = 4
18 16 90 3
3 16 18 90
In conclusion
This article has introduced onedimensional arrays, which are the simplest arrays. Part 3 explores more complex arrays, namely multidimensional arrays and ragged arrays. I also introduce the debate about whether an array is, or is not, a Java object. Read Part 3 now.