Arrays Study Guide

Study guide for array data structures.

Definitions

array - a contiguous block of memory that is fixed in size and that can be randomly accessed using integer indices

null - a reference to nothing, or to a non-existent memory location

Abstract Data Types/Interfaces

General

(None)

Java

Java provides an Arrays class with the following functionality:

• equals(A,B) - boolean, true iff $ A_i = B_i \quad \forall i $
• fill(A,x) - fills A with values x
• copyOf(A,n) - returns an array of size n, copied from A
• copyOfRange(A,s,t) - returns an array of size t-s, copied from corresponding indices of A
• toString(A) - string representation of A
• sort(A) - sort A using a tuned quicksort (see Java API Docs for implementation reference)
• sort(A, comp) - sort A using the specified Comparator object
• binarySearch(A,x) - perform binary search for x in A

Principal Operations and Algorithms

Important algorithms include:

• fisher-yates shuffle
• insertion sort
• sequential search
• binary search

Fisher Yates Shuffle

Fisher Yates shuffle is a technique for shuffling arrays.

• Pointer that starts and end and moves to front
• Randomly swap the pointer with an item between it and the front

for i in range (n-1) to (0):
    j = random number between 0 and i
    swap array[i], array[j]
    decrement i