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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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.
• Start with a reference to the last sorted element
• 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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
• Start with your array, your target, and your lo and hi index; at each step, compute a mid index
• 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)
		return not found
	mid = (lo+hi)/2
	if( A[mid] > target ) 
		return private_binary_search(array, target, lo, mid-1)
	else if( A[mid] < target ) 
		return private_binary_search(array, target, mid+1, hi)
	else
		return mid