Java Tutorial: Sorting and Searching


Posted 2020/06/02

Time Complexity

Time complexity is how many steps are required to complete an algorithm. When measuring time complexity, we make an average, best, and worst time complexities. The average time complexity is roughly how many steps are performed on average. The best and worst time complexities are how many steps it takes in the algorithm’s best and worst-case scenarios. Time complexity is expressed using Big-O notation, where n represents the input size or array length. For example a time complexity of O(n) means that the algorithm will take the same amount of steps as the array size.

Sorting

Sorting is the process of putting items of a list in a certain order. Most times, sorting is done to order a list in numerical or lexicographical order. There are many different algorithms for sorting with varying levels of simplicity and efficiency.

Bubble Sort

Bubble sort is one of the simplest sorting algorithms. This algorithm looks at adjacent values in the list and compares them and swaps if that pair is in the wrong order. It repeats this until the list is sorted.

Time Complexity

Worst-case: O(n2)
Average: O(n2)
Best-case: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public static void bubbleSort(int[] arr) {
    boolean sorted = false;
    int temp; //temporary variable for swaps
    while (!sorted) {
        sorted = true;
        for (int i = 0; i < arr.length - 1; i++) { //iterate through list
            if (arr[i] > arr[i+1]) { //compare adjacent items
                temp = arr[i]; //if not in order swap
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                sorted = false; //if swap made then array is not sorted, run another rotation
            }
        }
    }
}

Insertion Sort

Insertion sort builds the sorted list one item at a time. It creates two sublists and takes the next item of the unsorted sublist and inserts it in its proper position in the sorted sublist. It repeats until all items have been placed in their proper position in the sorted sublist.

Time Complexity

Worst-case: O(n2)
Average: O(n2)
Best-case: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public static void insertionSort(int arr[]) {
    for (int i = 1; i < arr.length; ++i) { //iterate through loop
        int key = arr[i]; //value to move
        int j = i - 1; //sorted sublist

        while (j >= 0 && arr[j] > key) { //shift elements
                arr[j + 1] = arr[j];
                j = j - 1;
        }
        arr[j + 1] = key; //insert
    }
}

Selection Sort

Selection sort also builds the sorted list one item at a time. It creates two sublists and scans the unsorted sublist for the next item to place at the end of the sorted sublist. It repeats until all items have been moved from the unsorted sublist to the sorted sublist.

Time Complexity

Worst-case: O(n2)
Average: O(n2)
Best-case: O(n2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public static void selectionSort(int[] arr){
    int n = arr.length;
    int min = 0;
        for(int i=0; i < n-1; i++){ //size of sorted subarray
            min = i;
            for(int j=i; j < n; j++){ //scan unsorted subarray
                if(arr[min] > arr[j]){ //if smaller set as min
                    min = j;
                }
                if(min != i){ //swap min to end of sorted
                    int temp=arr[min]; //write min to temporary var
                    arr[min]=arr[i]; //write index i to min index
                    arr[i]=temp; //write temp var to index i
                }
        }
    }
}

Merge Sort

Merge sort is a divide and conquer sorting algorithm. The algorithm splits the list into sublists of just one element each and merges the sorted sublists together to make the final sorted list. This algorithm is a recursive algorithm.

Time Complexity

Worst-case: O(n log n)
Average: O(n log n)
Best-case: O(n log n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static void mergeSort(int[] arr, int n) {
    if (n < 2) { // subarray has one element it is sorted
        return;
    }
    int mid = n / 2; //half of array
    int[] l = new int[mid]; //first half subarray
    int[] r = new int[n - mid]; //second half subarray

    for (int i = 0; i < mid; i++) { //copy first half
        l[i] = arr[i];
    }
    for (int i = mid; i < n; i++) { //copy second half
        r[i - mid] = a[i];
    }
    mergeSort(l, mid); //sort first half
    mergeSort(r, n - mid); //sort second half

    merge(arr, l, r, mid, n - mid); //put halves together
}

public static void merge(int[] a, int[] l, int[] r, int left, int right) {

    int i = 0, j = 0, k = 0; //pointers on left, right, and merge arrays
    while (i < left && j < right) { //while both arrays being compared
        if (l[i] <= r[j]) { //if left pointer value smaller than right
            a[k++] = l[i++]; //add left to merged array
        }
        else {
            a[k++] = r[j++];
        }
    }
    while (i < left) { 
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }
}

Searching

Searching is the process of fetching data stored in data structures like arrays or lists. Most search algorithms are used to find the location of an item in a data structure.

Linear/Sequential Search

Linear or sequential search is a brute-force algorithm that scans the list or array looking for a match to the search term. This search algorithm is not time efficient and is very slow when used on large lists.

Time Complexity

Worst-case: O(n)
Average: O(n)
Best-case: O(1)

1
2
3
4
5
6
public static int linearSearch(int[] arr, int search){
    for(int i=0; i < arr.length; i++){ //loop through items
        if(arr[i] == search) return i; //return index if matches
    }
    return -1;
}

Binary/Logarithmic Search

Binary or logarithmic search is a divide and conquer algorithm that requires the data structure to be already sorted. The algorithm splits the data set in half and compares the search term with the item in the middle. Using this comparison it knows which half to search for the item. It then repeats this process on the half until the item has been found.

Time Complexity

Worst-case: O( log n)
Average: O( log n)
Best-case: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public static int binarySearch(int arr[], int search) {
    int firstIndex = 0;
    int lastIndex = arr.length - 1;

    while(firstIndex <= lastIndex) { //termination condition (can't be found)
        int middleIndex = (firstIndex + lastIndex) / 2;
        if (arr[middleIndex] == search) { //if middle is element then return index
            return middleIndex;
        }

        else if (arr[middleIndex] < search) firstIndex = middleIndex + 1; //if middle is smaller go to second half


        else if (arr[middleIndex] > search) lastIndex = middleIndex - 1; //if middle is larger go to first half
    }
    return -1;
}