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

(None)

### Java

Java provides an Arrays class with the following functionality:

• equals(A,B) - boolean, true iff ${\displaystyle 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


### Insertion Sort

Insertion sort is a simple algorithm that involves two nested loops, and is therefore quadratic complexity.

• Stepping through the list one element at a time, such that everything before your pointer is sorted.
• Now have a walker element that points to the last sorted element
• Move it down one, and you're going to add the next (unsorted) element to the club of sorted elements
• Do this by scooting it forward, toward the front of the list, as many times as needed.
for i in range 1 to length(A):
j = i
while j>0 and A[j-1] > A[j]:
swap( A[j] , A[j-1] )
decrement j


### Sequential Search

Sequential search is the simplest (not fastest) way to look for something. Simplest possible imaginable algorithm. Runs in ${\displaystyle O(N)}$ time.

for i in range 1 to length(A):
if A[i] equals target:
return i

return -1


### Binary Search

Binary search is a much faster and more sophisticated way to searching things in ${\displaystyle O(\log N)}$ time. This requires a sorted array, and takes advantage of the sorted order to rule out half of the array it is considering at each step.

• Public/private method: public method takes no indices, private method takes 2 indices
• Base case: lo index passed hi index, return negative
• Recursive case: check which case: less than mid (call yourself with lo to mid-1), greater than mid (call yourself with mid+1 to hi), and equals (done)
def public_binary_search(array, target):
private_binary_search(array, target, 0, length(array)-1)

def private_binary_search(array, target, lo, hi):
if(lo>hi)