Chapter 6 Study Sheet
(by Emily Niekrasz, 2011)

Array- simple, but powerful way to organize data, especially when a large amount of information is involved.
            *an array may use integers or Strings, but never both 

How to Declare an Array:

            int [ ] joe = new int [18]; 

Array Element- the types of values that arrays hold  

Use for loops with arrays because the number of the position of the array is constant

            for (int index = 0; index < joe.length; index ++)
                        System.out.println (joe[index])  

Automatic Bounds Checking- the index operator performs this to make sure that the index is within the range that the array allowed

-ArrayIndexOutOfBoundsException- this error is thrown when the index is not valid

      -off-by-one error- created because the user is off by one because position begins at 0  

How to make an Initializer List:

            Int [ ] joe = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}; 

Creating String Arrays: 

            String [ ] joe = new String [18];
            *this is only setting up the array that will hold the strings 

Example:          

                        String [ ] grades = {“A”, “A-“, “B+”, “B”, “B-“};           

                        int [ ] numbers = {95, 90, 87, 83, 80};           

                        for (int level = 0; level< numbers.length; level ++)
                                    System.out.println  (grades[level] + “ ” + numbers [level]);

 Searching 

the most basic search is the linear/sequential search- look at each elements starting at the first until the element is reaches 

binary search - when searching for an element, start at the middle value. if less, the eliminate the upper half. keep dividing in half until the element is found

*for this search to occur, the data in the array must be sorted 

Sorting- the process of arranging a list of items in order 

Selection Sort

1.      Scan the list to find smallest value
2.      Swap that value with the value in the first position
3.      Continue to scan and swap until the values are in ascending order

a.       2 8 7 5

b.      2 8 7 5

c.       2 5 7 8

d.      2 5 7 8

e.       2 5 7 8

 Insertion Sort

1.      “Sorted” list contains only one value

2.      Keep picking up single values and insert them in the proper places

a.       8 2 7 5

b.      2 8 7 5

c.       2 7 8 5

d.      2 5 7 8
 

Merge Sort

1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
2. Divide the unsorted list into two sublists of about half the size.
3. Sort each sublist recursively by re-applying the merge sort.
4. Merge the two sublists back into one sorted list.

Efficiency of Algorithms

-         Space Efficiency- the amount of space an algorithm uses

-         Time Efficiency- how long it takes for an algorithm to run

Insertion & Selection Sorts: O($$n^2) – the “O” stands for optimization [all three sorts above have O(n^2)]
Merge Sort has: O($$$$n log n) -- so faster than Selection & Insertion.

Hashing- technique used to store and retrieve data in an array

-         this type of array is called a hash table

-         each item in the array has a hash code, tells where the in the array the data should be stored

-         using the hash function, hash code is calculated from the data

-         *Calculate hash code to find the cell where a piece of data should be stored

Example:

Hash Function is ( year + month + year) % 10 will map dates to valid spaces of the array 

            July 4, 1776 (7 + 4 + 1776 %1 0) = 7 this date hashes 7.

Two- Dimensional Arrays

Rows * Columns

            Int [ ][ ] joe = new int [3][6];

            Three rows and six columns

The ArrayList Class (import java.util.*)

ArrayList names = new ArrayList();
with 1.5 Generics: ArrayList<String> names = new ArrayList<String>();

Boolean add (Object obj)

    Adds the object to the end of the list 

Void add (int index, Object obj)

    Inserts the given object into this list at the given index 

Object set (int index, object obj)

    Sets the list element at the index to the object, and returns the object that was  previously in that index 

Object get (int index)

    Returns the object of the index 

Object remove (int index)

    Removes the object at the index from this list and returns it 

Int size size ( )

    Returns the number of elements to this list