Arrays Study Guide
Study guide for array data structures.
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
Java provides an Arrays class with the following functionality:
- equals(A,B) - boolean, true iff
- 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 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 is the simplest (not fastest) way to look for something. Simplest possible imaginable algorithm. Runs in time.
for i in range 1 to length(A): if A[i] equals target: return i return -1
Binary search is a much faster and more sophisticated way to searching things in 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
ArraysPart of Computer Science Notes
Series on Data Structures
Categories: Category:Python Arrays
Flags · Template:ArraysFlagBase · e