A+ Computer Science - Sorting & Searching Study Notes

A+ Computer Science - Sorting & Searching

Overview

Topic: Sorting and Searching Algorithms in Java
Source: www.apluscompsci.com

String and List Search Methods

Commonly Used Search Methods in Java:
  - indexOf(x): Returns -1 if not found or the index of x if found.
  - contains(x): Returns true if the list contains x, false otherwise.
  - equals(x): Returns true if this list is equal to x.

Example Implementations:

String s = "apluscompsci.com";
System.out.println(s.indexOf(".com")); // OUTPUT 12
System.out.println(s.contains("comp")); // OUTPUT true
System.out.println(s.indexOf("p")); // OUTPUT 1
System.out.println(s.indexOf("x")); // OUTPUT -1
System.out.println(s.equals("x")); // OUTPUT false

Array Lists and Their Search Methods

Java List Example Using ArrayList:

ArrayList<Integer> ray;
ray = new ArrayList<Integer>();
ray.add(21);
ray.add(14);
ray.add(0, 13);
ray.add(25);
System.out.println(ray.indexOf(21)); // OUTPUT 1
System.out.println(ray.indexOf(17)); // OUTPUT -1
System.out.println(ray.contains(25)); // OUTPUT true
System.out.println(ray.contains(63)); // OUTPUT false

Arrays Methods

Frequently Used Array Methods in Java:
  - sort(x): Sorts items in x in ascending order.
  - binarySearch(x, y): Searches x for the location of y.
  - equals(x, y): Checks if x and y have the same values.
  - fill(x, y): Fills all spots in x with value y.

Example Implementations:

int[] stuff = {3, 4, 5, 6, 11, 18, 91};
System.out.println(Arrays.binarySearch(stuff, 5)); // OUTPUT 2
System.out.println(Arrays.binarySearch(stuff, 15)); // OUTPUT -6

Array Sorting

Example of Sorting an Array:

int[] ray = {13, 6, 17, 18, 2, -5};
Arrays.sort(ray);
for(int i = 0; i < ray.length; i++) {
    System.out.println(ray[i]);
}
// OUTPUT -5, 2, 6, 13, 17, 18

List Sorting with Collections

Example Using ArrayList to Sort:

ArrayList<Integer> ray;
ray = new ArrayList<Integer>();
ray.add(21);
ray.add(2);
ray.add(13);
ray.add(-1);
ray.add(3);
Collections.sort(ray);
for(int num : ray) {
    System.out.println(num);
}
// OUTPUT -1, 2, 3, 13, 21

Search Algorithms

Linear Search:
- Searches through a list one element at a time and returns the index of a match or -1 if not found.
- Example Implementation:

  int linearSearch(int[] stuff, int val) {
      for(int i = 0; i < stuff.length; i++) {
          if (stuff[i] == val)
              return i;
      }
      return -1; // returns -1 if not found
  }
&nbsp;&nbsp;```

- **Binary Search:**
&nbsp;&nbsp;- Works best with sorted lists by repeatedly dividing the list in half.
&nbsp;&nbsp;- Example Implementation:

java
int binarySearch(int[] stuff, int val) {
int bot = 0, top = stuff.length - 1;
while (bot

Sorting Algorithms

Selection Sort

Description: Makes a complete pass to find the next smallest item to swap it once per pass.
Example Implementation:

void selectionSort(int[] stuff) {
    for(int i = 0; i < stuff.length - 1; i++){
        int min = i;
        for(int j = i + 1; j < stuff.length; j++) {
            if(stuff[j] < stuff[min])
                min = j;
        }
        if(min != i) {
            int temp = stuff[min];
            stuff[min] = stuff[i];
            stuff[i] = temp;
        }
    }
}

Insertion Sort

Description: Moves items based on comparisons to maintain sorted order.
Example Implementation:

void insertionSort(int[] stuff) {
    for(int i = 1; i < stuff.length; ++i) {
        int val = stuff[i];
        int j = i;
        while(j > 0 && val < stuff[j - 1]) {
            stuff[j] = stuff[j - 1];
            j--;
        }
        stuff[j] = val;
    }
}

Quick Sort

Description: Selects a pivot to partition the elements recursively.
Implementation for Quick Sort:

void quickSort(Comparable[] stuff, int low, int high) {
    if (low < high) {
        int spot = partition(stuff, low, high);
        quickSort(stuff, low, spot);
        quickSort(stuff, spot + 1, high);
    }
}

Partition Method Implementation:

public static int partition(Comparable[] stuff, int bot, int top) {
    Comparable pivot = stuff[(bot + top) / 2];
    while (bot < top) {
        while (stuff[top].compareTo(pivot) > 0 && bot < top)
            top--;
        while (stuff[bot].compareTo(pivot) < 0 && bot < top)
            bot++;
        Comparable temp = stuff[bot];
        stuff[bot] = stuff[top];
        stuff[top] = temp;
    }
    return top;
}

Merge Sort

Description: Recursively splits the list into smaller sections and merges them in sorted order.
Implementation of Merge Sort:

void mergeSort(Comparable[] stuff, int front, int back) {
    int mid = (front + back) / 2;
    if(mid == front) return;
    mergeSort(stuff, front, mid);
    mergeSort(stuff, mid, back);
    merge(stuff, front, back);
}

Merge Method Example:

public static void merge(Comparable[] stuff, int front, int back) {
    int dif = back - front;
    Comparable[] temp = new Comparable[dif];
    int beg = front, mid = (front + back) / 2, saveMid = mid;
    while(beg < saveMid && mid < back) {
        if(stuff[beg].compareTo(stuff[mid]) < 0)
            temp[spot++] = stuff[beg++];
        else
            temp[spot++] = stuff[mid++];
    }
    while(beg < saveMid)
        temp[spot++] = stuff[beg++];
    while(mid < back)
        temp[spot++] = stuff[mid++];
    for(int i = 0; i < dif; ++i)
        stuff[front + i] = temp[i];
}

Runtime Analysis for Different Algorithms

Searching Algorithms Complexity:
  - Linear/Sequential Search:
    - Best Case: O(1)
    - Average Case: O(N)
    - Worst Case: O(N)
  - Binary Search:
    - Best Case: O(1)
    - Average Case: O(log₂ N)
    - Worst Case: O(log₂ N)
Sorting Algorithms Complexity:
  - Selection Sort: O(N²)
  - Insertion Sort: O(N) if sorted, O(N²) otherwise.
  - Merge Sort: O(N log₂ N)
  - QuickSort: O(N log₂ N) average, O(N²) worst case.

Summary

Sorting and searching algorithms are critical for efficient data handling in programming.
Understanding the time complexity and implementation of various algorithms is essential for effective software development.