AP CSA: Sorts, Searches, Abstract, Interfaces

Searches

Linear Search

The Linear Search searches through a list, one element at a time to look for a match.

The index position of a match is returned if found
Otherwise, -1 is returned

Traits:

Works on unsorted data (the data doesn’t have to be sorted)
Simple to implement
No extra memory needed
In the worst case, it may need to check every element
- In the best case (the value is in the first position), it finds it immediately

// Primitives
int linearSearch(int[] stuff, int target) //sends in a array, and the target
{
 for (int i = 0; i< stuff.length; i++)
{
   if (stuff [i] == target) // if test to see if any of the values equal the target in the array
    {
        return i; // if so, returns their index
    } 
}
    return -1; //otherwise, returns -1 if not found
}

// Objects
int linearSearch(Comparable[] stuff, Comparable item) // takes an array of Comparable objects and a target item
{
    for (int i = 0; i < stuff.length; i++)
    {
        if (stuff[i].compareTo(item) == 0) // compare current object with target using compareTo instead just ==
        {
            return i; // if they are equal, return the index
        }
    }
    return -1; //otherwise, return -1 if not found
}

Examples

Integer[] numbers = {5, 12, 8, 20, 3};

int result = linearSearch(numbers, 20);

Your target amount is 20, and your array is {5, 12, 8, 20, 3};

The Linear Search is going to run like this:
- numbers[0] (5) = 20 ❌
- numbers[1] (12) = 20 ❌
- numbers[2] (8) = 20 ❌
- numbers [3] (20) = 20 ✅

The number returned would be 3, since 20 was found at index 3.

Integer[] numbers = {5, 12, 8, 20, 3};

int result = linearSearch(numbers, 7);

The Linear Search is going to run like this:
- numbers[0] (5) = 7 ❌
- numbers[1] (12) = 7 ❌
- numbers[2] (8) = 7 ❌
- numbers [3] (20) = 7 ❌
- numbers [4] (3) = 7 ❌

Since none of the values were 7, the compiler returns a -1.

Binary Search

Binary Search finds a value by repeatedly diving a sorted list in half and checking the middle element

The list must be sorted for Binary Search to work
The index position of a match is returned if found
- Otherwise, -1 is returned

// Primitives
int binarySearch(int[] stuff, int target)
{
    int low = 0;
    int high = stuff.length - 1;

    while (low <= high)
    {
        int mid = (low + high) / 2; // mid divides the whole array in half and saves it

        if (stuff[mid] == target)
        {
            return mid; // found target
        }
        else if (stuff[mid] < target) // the < would be > if the thing passed was in DESCENDING order (e.g., {20, 18, 16, 14, 12....})
        {
            low = mid + 1; // search right half
        }
        else
        {
            high = mid - 1; // search left half
        }
    }

    return -1; // not found
}

int binarySearch(Comparable[] stuff, Comparable item)
{
    int low = 0;
    int high = stuff.length - 1;

    while (low <= high)
    {
        int mid = (low + high) / 2;

        if (stuff[mid].compareTo(item) == 0)
        {
            return mid; // found target
        }
        else if (stuff[mid].compareTo(item) < 0)
        {
            low = mid + 1; // search right half
        }
        else
        {
            high = mid - 1; // search left half
        }
    }

    return -1; // not found
}

Examples

Integer[] numbers = {3, 5, 8, 12, 20};

int result = binarySearch(numbers, 20);

The Binary Search is going to run like this:
- Start with the entire array: {3, 5, 8, 12, 20}.
- Calculate the middle index: mid = (0 + 4) / 2 = 2, looking at numbers[2] = 8.
- Since 20 > 8, discard the left half and focus on the right half: {12, 20}.
- Recalculate middle index for the new subarray: mid = (3 + 4) / 2 = 3, checking numbers[3] = 12.
- Since 20 > 12, discard the 12 and focus only on the last element: {20}.
- Again calculate the middle index: mid = (4 + 4) / 2 = 4, checking numbers[4] = 20.
- Since we found the target, return the index 4.

Sorts

Selection Search

Selection Sort is a sorting algorithm that repeatedly finds the smallest (or largest) element in the unsorted part of the array and moves it to the correct position.
The list becomes sorted by building it from the left to the right

Traits:

Works on unsorted data
Repeatedly selects minimum value (or maximum if sorting descending)
Simple but takes very long for large datasets
# of swaps is typically smaller compared to the # of comparisons

//Primitives - Ascending
void selectionSort(int[] arr)
{
    for (int i = 0; i < arr.length - 1; i++)
    {
        int minIndex = i; 
        // IMPORTANT: assumes first unsorted element is smallest

        for (int j = i + 1; j < arr.length; j++)
        {
            if (arr[j] < arr[minIndex]) // would be > if descending
            // IMPORTANT: finds smaller value in unsorted section
            {
                minIndex = j;
            }
        }

        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
        // IMPORTANT: swap puts smallest value in correct position
    }
}

Insertion Search

Insertion Sort builds a sorted list by taking each element and inserting it into its correct position in the already sorted part of the array.

Traits:

Works on unsorted data
Builds the sorted section from left to right
Efficient for small or nearly sorted arrays
In-place sorting (no extra memory needed)
Stable sorting algorithm (keeps equal items in order)

//Primitives
void insertionSort(int[] arr)
{
    for (int i = 1; i < arr.length; i++)
    {
        int key = arr[i];
        // IMPORTANT: value to be inserted into sorted section

        int j = i - 1;

        while (j >= 0 && arr[j] > key) // < would make it descending
        // IMPORTANT: shifts larger values to the right
        {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
        // IMPORTANT: inserts key into correct position
    }
}

Bubble Sort

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

Larger values “bubble” to the end of the array each pass.

Traits:

Works on unsorted data
Repeatedly compares adjacent elements
Simple but very inefficient for large datasets
In-place sorting (no extra memory needed)
Stable sorting algorithm (keeps equal elements in order)

void bubbleSort(int[] arr)
{
    for (int i = 0; i < arr.length - 1; i++)
    // IMPORTANT: controls number of passes (n - 1 passes)
    {
        for (int j = 0; j < arr.length - 1 - i; j++)
        // IMPORTANT: each pass ignores last sorted elements
        {
            if (arr[j] > arr[j + 1]) // < descending
            // IMPORTANT: swap if left is greater (ascending)
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                // IMPORTANT: swaps adjacent elements
            }
        }
    }
}

Quick Sort

Quick Sort is a divide-and-conquer sorting algorithm that works by selecting a pivot and partitioning the array into two halves:

Values less than the pivot
Values greater than the pivot

It then recursively sorts the two halves.

Traits:

Picks a pivot element

Partitions array into left (smaller) and right (larger)
Very fast for large datasets
Not stable (order of equal elements may change

int partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    // IMPORTANT: choosing last element as pivot (common choice)

    int i = low - 1;
    // IMPORTANT: tracks position for smaller elements

    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot) // > : descending
        // IMPORTANT: elements smaller than pivot go left
        {
            i++;

            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            // swap
        }
    }

    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    // IMPORTANT: place pivot in correct position

    return i + 1;
}

Merge Sort

Merge Sort is a divide-and-conquer algorithm that repeatedly splits the array into smaller halves until each part has only one element.

The left side is created by taking the first half of the array.

Key Idea:

You split the array using the middle index:

int mid = (low + high) / 2;

Left side → from low to mid
Right side → from mid + 1 to high

void mergeSort(int[] arr, int low, int high)
{
    if (low < high)
    // IMPORTANT: base case (stop when 1 element)
    {
        int mid = (low + high) / 2;

        mergeSort(arr, low, mid);
        // IMPORTANT: LEFT HALF

        mergeSort(arr, mid + 1, high);
        // RIGHT HALF

        merge(arr, low, mid, high);
        // combines both halves
    }
}

Abstract/Interfaces

Abstract Classes

An abstract class in Java is a class that cannot be instantiated and is meant to be inherited.
It can contain:
- Abstract methods (no body, must be implemented in subclasses)
- Concrete methods (with implementation)
- Variables and constructors

Key Points

Declared using the abstract keyword.
You cannot create objects of an abstract class.
Subclasses must implement all abstract methods or also be declared abstract.
Supports code reuse and provides a common structure for related classes.

Purpose

Used to define a common template for related classes while allowing specific behavior to be implemented by subclasses.

Simple Idea

An abstract class is like a partially defined blueprint, it sets rules and provides some implementation, but leaves details to child classes.

// Abstract class: cannot be instantiated directly
abstract class Animal {

    // Abstract method: no body, must be implemented by subclasses
    abstract void makeSound();

    // Concrete method: already implemented, shared by all subclasses
    void sleep() {
        System.out.println("Animal is sleeping...");
    }
}

// Dog is a subclass of Animal
class Dog extends Animal {

    // Providing implementation for abstract method
    @Override
    void makeSound() {
        System.out.println("Dog barks");
    }
}

// Cat is another subclass of Animal
class Cat extends Animal {

    // Each subclass defines its own version of makeSound()
    @Override
    void makeSound() {
        System.out.println("Cat meows");
    }
}

// Main class to run the program
public class Main {
    public static void main(String[] args) {

        // Cannot do: Animal a = new Animal(); ❌ (abstract class)

        // Using polymorphism: parent reference, child object
        Animal a1 = new Dog();
        Animal a2 = new Cat();

        // Calls Dog's version of makeSound()
        a1.makeSound();
        a1.sleep(); // inherited concrete method

        // Calls Cat's version of makeSound()
        a2.makeSound();
        a2.sleep(); // same shared method
    }
}

An interface in Java is a blueprint/contract that defines what a class should do, but not how it does it.

Interfaces

Key Features

Declared using the interface keyword.
Contains abstract methods by default (no method body).
Variables are public, static, and final (constants).
Cannot be instantiated (no objects can be created).
Implemented using the implements keyword.

Syntax Idea

interface Animal {
    void makeSound(); // abstract method
}

Implementation

A class must implement all methods of the interface.
Otherwise, the class must be declared abstract.

class Dog implements Animal {
    public void makeSound() {
        System.out.println("Bark");
    }
}

Important Rules

All methods are public by default.
No constructors allowed.
No instance variables (only constants).
A class can implement multiple interfaces → supports multiple inheritance.

Advantages

Achieves abstraction
Supports multiple inheritance
Provides loose coupling
Improves code flexibility and maintainability