Topic 3 of 13 · Lecture 3

Arrays, Sorting & Searching

Storing many values in one array, 2-D and jagged arrays, how arrays live in memory, and the classic sorting and searching algorithms.

Start All topics

← → move between slides · F full screen · M slide list

Before we start

Why this matters

A class has 60 students. Do you really need 60 separate variables to store their marks?

An array stores many values of the same type under one name, each reached by an index. Once marks sit in an array, one loop can find the highest, the average or sort them.

You will also see a surprise: arrays are objects, so copying an array variable does not copy the array.

Outline · Lecture 3

Topics in this chapter

Select a topic to jump to the slide that explains it.

Arrays: declaration, creation, length
Array references and copying
Multidimensional arrays
Sorting: bubble, selection, insertion
Searching: linear and binary

Concept 1 of 5

Declaring and creating arrays

The variable holds a reference; the array object with its elements lives on the heap.

Declaring and creating arrays

int[] marks = new int[5];         // 5 zeros
marks[0] = 78;
marks[4] = 91;

double[] cgpa = {3.5, 3.9, 2.8};  // initializer
String[] days = new String[7];    // 7 nulls

System.out.println(marks.length); // 5
System.out.println(cgpa[2]);      // 2.8
marks[5] = 10;  // ArrayIndexOutOfBoundsException!

Indexes run from 0 to length − 1.
New arrays are filled with default values: 0, 0.0, false or null.
length is a field, not a method — no brackets.

Step through the code

Trace: finding the highest mark

The loop compares every element with the best value so far. Watch max change only when a larger mark appears.

Step through the code

Trace: finding the highest mark (cont.)

Concept 2 of 5

Arrays are objects: copying a reference

int[] b = a; copies the reference, not the elements. a.clone() makes a real copy.

Arrays are objects: copying a reference

b = a → both names refer to the same array (aliases). A change through b is visible through a.
a.clone() or Arrays.copyOf(a, a.length) creates a new array with the same values.
a == b compares references. Use Arrays.equals(a, b) to compare contents.

Step through the code

Trace: aliases and copies

Colour-matched arrows show which variables share an array. The last step creates a new array for a — does b change?

Step through the code

Trace: aliases and copies (cont.)

Concept 3 of 5

Multidimensional and jagged arrays

A 2-D array is an array of row arrays: m[i] is a whole row.

Concept 3 of 5

Multidimensional and jagged arrays

Rows can have different lengths (a jagged array).

Multidimensional and jagged arrays

int[][] m = { {1, 2, 3}, {4, 5, 6} };      // 2 rows × 3 columns
System.out.println(m.length + " " + m[0].length);   // 2 3
int[][] t = new int[3][];                  // rows created later
t[0] = new int[1];  t[1] = new int[2];  t[2] = new int[3];

Interactive

2-D array explorer

Concept 4 of 5

Sorting algorithms

Algorithm	Idea	Comparisons (worst)
Bubble sort	Compare neighbours and swap if out of order. After pass k, the k largest values are in place at the end.	n(n−1)/2
Selection sort	Find the minimum of the unsorted part and swap it to the front.	n(n−1)/2, but at most n−1 swaps
Insertion sort	Take the next value and shift larger values right until its place is found — like sorting playing cards.	n(n−1)/2; almost linear on nearly-sorted data

// bubble sort
for (int pass = 0; pass < a.length - 1; pass++)
    for (int j = 0; j < a.length - 1 - pass; j++)
        if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; }

Library: In real programs use Arrays.sort(a), which is fast (O(n log n)).

Step through the code

Trace: bubble sort, swap by swap

Watch each pair being compared. The highlighted cells are the two neighbours; after every pass one more value is in its final place.

Step through the code

Trace: bubble sort, swap by swap (cont.)

Interactive

Sorting visualizer

Concept 5 of 5

Searching

static int linear(int[] a, int key) {
    for (int i = 0; i < a.length; i++)
        if (a[i] == key) return i;
    return -1;                     // not found
}

static int binary(int[] a, int key) {  // a must be sorted
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

	Linear	Binary
Needs sorted data?	No	Yes
Worst case, n = 1,000,000	1,000,000 checks	20 checks
Growth	O(n)	O(log n)

Interactive

Linear vs binary search

Step through the code

Trace: binary search halves the range

Pick a key. The highlighted cells are the part of the array that can still contain it; it halves on every look.

Step through the code

Trace: binary search halves the range (cont.)

Code example

Useful java.util.Arrays methods

import java.util.Arrays;

int[] a = {42, 7, 19, 3};
Arrays.sort(a);
System.out.println(Arrays.toString(a));
System.out.println(Arrays.binarySearch(a, 19));
int[] b = Arrays.copyOf(a, 6);
System.out.println(Arrays.toString(b));
Arrays.fill(b, 1);
System.out.println(Arrays.toString(b));
System.out.println(Arrays.equals(a, new int[]{3, 7, 19, 42}));

Output

[3, 7, 19, 42]
2
[3, 7, 19, 42, 0, 0]
[1, 1, 1, 1, 1, 1]
true

Worked example 1 of 3

Worked example 1

Reverse an array in place.

Show the solution

for (int i = 0, j = a.length - 1; i < j; i++, j--) {
    int t = a[i]; a[i] = a[j]; a[j] = t;
}

Swap the two ends and move inwards; stop when the indexes meet. Only n/2 swaps.

Worked example 2 of 3

Worked example 2

Show the array after each pass of bubble sort on {5, 1, 4, 2}.

Show the solution

Pass 1: {1, 4, 2, 5}
Pass 2: {1, 2, 4, 5}
Pass 3: {1, 2, 4, 5} (no swaps — already sorted)

Worked example 3 of 3

Worked example 3

Binary search for 23 in {2, 5, 8, 12, 16, 23, 38, 56}. List lo, hi, mid for each step.

Show the solution

lo=0, hi=7, mid=3 → 12 < 23 → lo = 4
lo=4, hi=7, mid=5 → 23 found at index 5

Only 2 comparisons, against up to 6 for a linear search.

Practice

Practice (1 of 2)

Try each one on paper first, then check your answer.

1. Write code to compute the average of a double[].

Show the answer

double s = 0;
for (double v : a) s += v;
double avg = s / a.length;

2. What is printed? int[] a = {1,2,3}; int[] b = a; b[1] = 9; System.out.println(a[1]);

Show the answer

9 — a and b refer to the same array.

3. Find the sum of each row of int[][] m.

Show the answer

for (int i = 0; i < m.length; i++) {
    int s = 0;
    for (int j = 0; j < m[i].length; j++) s += m[i][j];
    System.out.println("Row " + i + ": " + s);
}

Practice

Practice (2 of 2)

Try each one on paper first, then check your answer.

4. Show selection sort on {29, 10, 14, 37, 13} pass by pass.

Show the answer

{10, 29, 14, 37, 13} → {10, 13, 14, 37, 29} → {10, 13, 14, 37, 29} → {10, 13, 14, 29, 37}.

5. What is the maximum number of comparisons binary search needs for 1,000 sorted elements?

Show the answer

10, because 2¹⁰ = 1024 ≥ 1000.

6. Why does int[] a = new int[3]; System.out.println(a); print something like [I@1b6d3586?

Show the answer

Printing an array prints its type and hash code, not its elements. Use Arrays.toString(a).

Check yourself

Quiz

Summary

An array stores a fixed number of same-typed values; indexes go from 0 to length − 1.
Array variables hold references: assignment creates aliases; clone() or Arrays.copyOf makes copies.
A 2-D array is an array of arrays; rows may differ in length (jagged).
Bubble, selection and insertion sort all take about n²/2 comparisons; use Arrays.sort in practice.
Linear search works on any array (O(n)); binary search needs sorted data but is O(log n).

Next: Classes, Objects & Encapsulation More practice Quick reference All topics