Big O notation

Searching

Finding the index of an element requires O(n) time if an array is unsorted as we need to traverse. However, if sorted we can use Binary sort to more quickly find an element

Binary Search

  • The Precondition is that the array is sorted
  • Plays higher or lower until finding the target index
  • Time-Complexity Olog(n)
  • Java has a built-in function: Arrays.binarySearch()

Here is an implementation from AP Classroom

Copy

public static int bSearch(int[] arr, int left, int right, int x){
    if (right >= left){
        int mid = (left + right) / 2;
        if (arr[mid] == x){
            return mid;
        }
        else if (arr[mid] > x){
        return bSearch(arr, left, mid - 1, x);
        }
        else{
            return bSearch(arr, mid + 1, right, x);
        }
    }
    return -1;
}

Sorting

Two important sorting algorithms: Selection and Merge

Selection Sort

Here is an implementation from AP Classroom

Copy

public static void selectionSort(int[] elements){
    for (int j = 0; j < elements.length - 1; j++){
        int minIndex = j;
        for (int k = j + 1; k < elements.length; k++){
            if (elements[k] < elements[minIndex]){  
                minIndex = k;
            }
        }
        if (j != minIndex){
            int temp = elements[j];
            elements[j] = elements[minIndex];
            elements[minIndex] = temp;
        }
    }
}

Merge Sort

This is the implementation from ap clasroom. Merge() is not shown

Copy

public static void mergeSortHelper(int[] elements,int from,int to,int[] temp){
    if (from<to){  
        int middle=(from+to)/2
        mergeSortHelper(arr,from,middle,temp);
        mergeSortHelper(arr,middle+1,to,temp);
        merge(arr,from,middle,to,temp);
    }
}

Group Sorting Presentation

Me and Mitchel decided on Radix Sort

Here is the code I made to sort postal codes

Copy

/*
Author: George Postica and Mitchell Levitt
Teacher: Ms. Krasteva
Description: MSD radix sort used https://www.geeksforgeeks.org/msd-most-significant-digit-radix-sort/ for help
*/
import java.io.*;
import java.lang.*;
import java.util.*;
class postalCodeSort {
    public static void main(String[] args)
    {
        String[] postalCodes={"M3H","L4J","M5A","L5M","M3J","L6Y","M5H","L4X","M3H"};
        int n=postalCodes.length;
        System.out.print("Unsorted Array: ");
        printArray(postalCodes);
        MSD_sort(postalCodes,0,n-1,0);
        System.out.println("Sorted Array: ");
        printArray(postalCodes);
    }
    private static void printArray(String arr[]){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    public static intchar_at(String x,int d){
        if(Character.isDigit(x.charAt(d))){
            return ((int) x.charAt(d))-49;
        }else{
            return ((int) x.charAt(d))-65+9;
        }
    }
    public static void MSD_sort(String[] arr, int lo,int hi,int d){ 
        if (hi <= lo || d>=3) {
            return;
        }
        int count[] = new int[35+1];
        HashMap temp = new HashMap<>();
        for(int i=lo;i<=hi;i++){
            int c = char_at(arr[i],d);
            count[c+2]++;
        }
        for (int r = 0; r < 35; r++){
            count[r + 1] += count[r];
        }
        for (int i = lo; i <= hi; i++) {
            int c = char_at(arr[i], d);
            temp.put(count[c + 1]++, arr[i]);
        }
        for (int i = lo; i <= hi; i++){
            arr[i] = temp.get(i - lo);
        }
        for (int r = 0; r < 35; r++){
            MSD_sort(arr, lo + count[r], lo + count[r + 1] - 1, d + 1);
        }
    }
}