Skip to main content

[Java] Java371 Lecture 4

Arrays and More Data Structures

info

This document is a class note about Java Programming taughted by Mr.Lu.

Arrays​

A array is an object which stores multiple values of the same type.

// Assume that T is any type and the size is known.
T[] A = new T[size];

Stage1: Array Creation​

  • One array is allocated in the heap by invoking the new operator followed by T and [] surrounding its size,
  • Then its starting address is returned and should be cached.
  • Note that the size cannot be changed after allcation.

Stage2: Reference​

  • We then declare one variable, say A in this case, to store the starting address of the array.
  • A is not the array, but the reference to the array!
  • To understand the type correctly, one should read the type from right to left
  • For example, A is the reference to an array whose elements are of the T type.
  • Note that the array type is declared like T[] but without the size.

Indexing​

  • We access any array element by using its index, which starts from 0 but not 1.
  • When the index is out of range, the program will fail due to the runtime exception ArrayIndexOutOfBoundsException.

Memory Allocation for Arrays​

  • An array is allocated contiguously in the memory.
  • To fetch the second element, jump to the address stored by A and shift by 1 unit size of T, denoted by A[1].
  • ex.

Array initialization​

  • Every array is initialized implicitly once the array is created.
  • A array can also be created by enumerating all elements without using the new operator, for example,
int[] A = { 10, 20, 30}; // Syntax sugar.

Arrays & Loops​

We often use loops to process array elements.

// Create an integer array of size 5.
int[] A = new int [5];

// Generate 5 random integers ranging from 0 to 99.
for (int i = 0; i < A.length; ++i) {
    A[i] = (int) (Math.random() * 100);
}

// Display all elements of A; O(n).
for (int i = 0; i < A.length; ++i) {
    System.out.prinf("%d", A[i]);
}
System.out.println();
  • To show all the elements, we need to iterate over the array by loops instead of simply printing A, because we will print out the reference address.
int max = A[0];
int min = A[0];
for (int i = 1; i < A.length; ++i) {
    if (max < A[i]) max = A[i];
    if (min > A[i]) min = A[i];
}
  • How about the locations of extreme values?
  • Can you find the 2nd max of A?
  • Can you record the first k max of A?
// Sum of A: O(n).
int sum = 0;
for (int i = 0; i < A.length; ++i) {
    sum += A[i];
}
  • Calculate the following descriptive statistics:
    • the mean of A
    • the median of A
    • the mode of A

Alternative Way: for-each Loops​

T[] A = { ... };
for (T element : A) {
    // Loop body.
}

Example:

// for loop
int s = 0;
for (int i = 0; i < A.length; ++i) {
    s += A[i];
}
// for-each loop
for (int element:A) {
    s += element;
}
  • Using for-each loop if you iterate over all elements and the order of iteration is irrelevant.

More usage​

Cloning Arrays​

shallow copy:

int x = 1;
int y = x; // You can say that y copies the value of x.
x = 2;
System.out.println(y); // Output 1.

int[] A = { 10, ... }; // Ignore the rest of elements.
int[] B = A;
A[0] = 100;
System.out.println(B[0]); // Output? 100

To clone an array, you should create a new array and use loops to copy every element, one by one. deep copy:

// Let A be an array to be copied.
int[] B = new int[A.length];
for (int i = 0; i < A.length; ++i) {
    B[i] = A[i];
}

System.arraycopy():

// Assume that B is ready.
System.copy(A, 0, B, 0, A.length);

Shuffle Algorithm​

for (int i = 0; i < A.length; ++i) {

    // Choose a random integer j.
    int j = (int) (Math.random() * A.length);

    // Swap A[i] and A[j].
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

However, this naive algorithm is fundamentally broken!

Exercise:

info

Write a program to deal the first 5 cards from a deck of 52 shuffled cards.

String[] suits = { "Club", "Diamond", "Heart", "Spade" };
String[] ranks = { "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A", "2"};

int size = 52;
int[] deck = new int[size];
for (int i = 0; i < deck.length; i++)
    deck[i] = i;

// shuffle algorithm: correct version.
for (int i = 0; i < size - 1; i++) {
    int j = (int) (Math.random() * (size - i)) + i;
    int z = deck[i];
    deck[i] = deck[j];
    deck[j] = z;
}

for (int i = 0; i < 5; i++) {
    String suit = suits[deck[i] / 13];
    String rank = ranks[deck[i] % 13];
    System.out.printf("%2s %-7s\n", rank, suit);
}

Sorting Problem​

  • In CS, a sorting algorithm is an algorithm that puts elements of a list in a certain order.
  • You may call Arrays.sort(A) to rearrange A in ascending order, for example,
import java.util.Arrays;

int[] A = { 5, 2, 8};
Arrays.sort(A); // Becomes { 2, 5, 8 }.

String[] B = { "www", "csie", "ntu", "edu", "tw" };
Arrays.sort(B); // Result? { "csie", "edu", "ntu", "tw", "www"}
  • Note that we sort strings in lexicographical (dictionary) order for most cases.

Bubble Sort

// Bubble sort: O(n ^ 2).
boolean swapped;
do {
    swapped = false;
    for (int i = 0; i < A.length - 1; i++) {
        if (A[i] > A[i + 1]) {
            int tmp = A[i];
            A[i] = A[i + 1];
            A[i + 1] = tmp;
            swapped = true;
        }
    }
} while (swapped);

Selection Sort

Insertion Sort

Searching Problem​

  • It is often to query one key for its corresponding value.
  • For example, the program plans to find one client's credit and number.
  • In this case, the client name is the query key and his/her credit card number is the value associated.

Linear Search

  • linear search compares the query key with all elements in sequential order.
// Linear search: O(n).
int[] A = { ... };
int founds = 0;
for (int i = 0; i < A.length; i++) {
    if (A[i] == key) {
        System.out.printf("%d ", i);
        founds++;
    }
}
System.out.println("\nFounds: " + founds);

Binary Search

int idx = -1; // Why?
int high = A.length - 1, low = 0, mid;
while (high > low && idx < 0) {
    mid = low + (high - low) / 2; // why?
    if (A[mid] < key)
        low = mid + 1;
    else if (A[mid] > key)
        high = mid - 1;
    else
        idx = mid;
}

if (idx > -1)
    System.out.printf("%d: %d\n", key, idx);
else
    System.out.printf("%d: not found\n", key);
  • It can be shown that binary search runs in O(log n) time.
  • However, binary search works only for ordered data!

Discussions

  • Assume that the data is immutable (unchangeable).
  • We sort the data once for all and the binary search works well.
  • What if the data may be changed all the time?

Short intro to Data Structures​

  • A data structure is a particular way of organizing data in a program so that it can perform efficiently.
  • The choice for data structures depends on applications.
  • As an alternative to arrays, linked lists are used to store data in the way different from arrays.
  • You will see plenty of data structures in the future.
    • For example, trees, graphs, tables, and more.

Beyond 1D Arrays​

  • We can create 2D T-type arrays simply by adding one more [] with its size.
  • ex.
int rows = 4; // Row size.
int cols = 3; // Column size.
T[][] M = new T[rows][cols];

Example: 2D Arrays & Loops​

int[][] A = { { 10, 20, 30 }, { 40, 50 }, { 60 } };

// Conventional for loop.
for (int i = 0; i < A.length; i++) {
    for (int j = 0; j < A[i].length; j++)
        System.out.printf("%3d", A[i][j]);
    System.out.println();
}

// For-each loop.
for (int[] row : A) {
    for (int item : row)
        System.out.printf("%3d", item);
    System.out.println();
}

Digression(題外話): ArrayList​

int[] A = new int[3]; // The size should be known in advance.
A[0] = 100;
A[1] = 200;
A[2] = 300;
for (int item : A)
    System.out.printf("%d ", item);
System.out.println();

ArrayList<Integer> B = new ArrayList<>(); // Size?
B.add(100);
B.add(200);
B.add(300);
System.out.println(B); // Short and sweet!
  • An array is the most essential and simplest data structure, but not convenient to use.
    • For example, how to resize the array when it is full?
  • In practice, you should use ArrayList, where in < > is the type parameter (variable).
  • In particular, the symbol with angle brackets < > is called the generics, which is wildly used in data structures, like Stack, Map, Graph, etc.
  • In this case, we replace < > with Integer, which is the wrapper class for int values.
  • Note that you can replace the type parameters by only non-primitive types.

Case Study: Reversing​

  • Write a program to arrange the array in reverse order.
  • Let A be an integer array as input.
  • The first attempt is to create another array with same size and copy each element from A to B.
int[] A = { 1, 2, 3, 4, 5 };
int[] B = new int[A.length];
for (int i = 0; i < A.length; i++) {
    B[A.length - 1 - i] = A[i];
}
A = B; // Why?

Another Attempt

int[] A = { 1, 2, 3, 4, 5 };
for (int i = 0; i < A.length / 2; i++) {
    int j = A.length - 1 - j;
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

  • The second is better, both in time and space.
  • It is an in-place algorithm.