Algorithms

What is an algorithm? An algorithm is a set of processes and calculations done by a computer to solve some problem. For the AP exam, the only algorithms you need to know are searching algorithms - algorithms that traverse a data structure to find a particular value - and sorting algorithms - algorithms that sort a data structure.

Big O Notation

In math, you define a function as f(x) = ... . Big O is a type of function used to determine the efficiency of an algorithm. It is written as O(...). In the parentheses, it is written in terms of n, the size of the data set. So linear search has an efficiency of O(n) as the search proportionally depends on how large the data set is. O(1) indicates that n doesn't matter; the efficiency is always the same.

Searching Algorithms

Linear/Sequential

A linear (or sequential) algorithm iterates through each item in a list to find a certain item. Linear search is the most useful in unsorted lists because you don't know where the item is.

Binary

Binary search searches through a sorted list. It divides the list into half, then dividing that half into another half. It repeats this process till it finds the desired item.

Sorting Algorithms

Selection Sort

Selection sort iterates over the list, finding the smallest value and sending it to its appropriate place in the list. It's O(n^2).

Insertion Sort

Insertion sort iterates over each item in the list. It then moves each item into its appropriate place in the list by determining if it is greater than its previous element and smaller than the element right after it. It's O(n^2).

Bubble (Sinking) Sort

This algorithm makes the largest values in the array rise to the end of the array like bubbles. It's O(n^2). Here is the code for bubble sort:

public static void bubbleSort(int[] numArray) {

    int n = numArray.length;

    int temp = 0;

    for (int i = 0; i < n; i++) {

        for (int j = 1; j < (n - i); j++) {

            if (numArray[j - 1] > numArray[j]) {

                temp = numArray[j - 1];

                numArray[j - 1] = numArray[j];

                numArray[j] = temp;

            }

        }

    }

}

Merge Sort

Merge sort is like binary search - it has a divide and conquer strategy and halves the list and sorts each sublist. It is O(nlogn).