Sorting and Searching

Author: Jacob Park

Insertion Sort ($O(n^2)$)

In [1]:
package sorting.insertion_sort;

class InsertionSort {

    public static void insertionSort(int[] S) {
        // For every element,
        for (int index = 0; index < S.length; index++) {
            /*
             * Sink the element leftwards to the head 
             * such that the array is sorted.
             */
            for (int subIndex = index;
                 subIndex > 0 && S[subIndex] < S[subIndex - 1];
                 subIndex--) {
                final int temporary = S[subIndex];
                S[subIndex] = S[subIndex - 1];
                S[subIndex - 1] = temporary;
            }
        }
    }

}
Out[1]:
sorting.insertion_sort.InsertionSort
In [2]:
package sorting.insertion_sort;

import java.util.Arrays;

final int[] S = new int[] {7, 5, 0, 1, 6, 2, 4, 2};

InsertionSort.insertionSort(S);

System.out.println(Arrays.toString(S));

[0, 1, 2, 2, 4, 5, 6, 7]
Out[2]:
null

Merge Sort ($O(n\log(n))$)

In [3]:
package sorting.merge_sort;

class MergeSort {
    
    public static void mergeSort(
            int[] S, 
            int[] buffer, 
            int headIndex, 
            int tailIndex) {
        if (headIndex >= tailIndex) {
            return;
        }
        
        final int medianIndex = headIndex + (tailIndex - headIndex) / 2;
        mergeSort(S, buffer, headIndex, medianIndex);
        mergeSort(S, buffer, medianIndex + 1, tailIndex);
        merge(S, buffer, headIndex, medianIndex, tailIndex);
    }
    
    private static void merge(
            int[] S, 
            int[] buffer, 
            int headIndex, 
            int medianIndex, 
            int tailIndex) {
        // Copy the left and the right slices into buffer.
        for (int index = headIndex; index <= tailIndex; index++) {
            buffer[index] = S[index];
        }
        
        int lowerIndex = headIndex;
        int upperIndex = medianIndex + 1;
        int index = headIndex;
        
        /*
         * Take the minimum of the left and the right slice 
         * until one is empty.
         */
        while (lowerIndex <= medianIndex && upperIndex <= tailIndex) {
            if (buffer[lowerIndex] <= buffer[upperIndex]) {
                S[index++] = buffer[lowerIndex++];
            } else {
                S[index++] = buffer[upperIndex++];
            }
        }
        
        // Flush the left slice.
        while (lowerIndex <= medianIndex) {
            S[index++] = buffer[lowerIndex++];
        }
        
        // Flush the right slice.
        while (upperIndex <= tailIndex) {
            S[index++] = buffer[upperIndex++];
        }
    }
    
}
Out[3]:
sorting.merge_sort.MergeSort
In [4]:
package sorting.merge_sort;

import java.util.Arrays;

final int[] S = new int[] {7, 5, 0, 1, 6, 2, 4, 2};
final int[] buffer = new int[S.length];

MergeSort.mergeSort(S, buffer, 0, S.length - 1);

System.out.println(Arrays.toString(S));

[0, 1, 2, 2, 4, 5, 6, 7]
Out[4]:
null

Quick Sort ($O(n\log(n))$)

In [5]:
package sorting.quick_sort;

class QuickSort {
    
    public static void quickSort(int[] S, int headIndex, int tailIndex) {
        if (headIndex >= tailIndex) {
            return;
        }
        
        final int pivotIndex = partition(S, headIndex, tailIndex);
        quickSort(S, headIndex, pivotIndex - 1);
        quickSort(S, pivotIndex + 1, tailIndex);
    }
    
    /*
     * Partition the array with the sentinel as the pivot.
     * All elements before the sentinel should be less 
     * than the sentinel.
     * All elements after the sentinel should be greater 
     * than the sentinel.
     */
    private static int partition(int[] S, int headIndex, int tailIndex) {
        // Choose the head as the sentinel.
        final int sentinel = S[headIndex];

        int lowerIndex = headIndex;
        int upperIndex = tailIndex + 1;
        while (true) {
            /*
             * Find the first element starting up from lower index 
             * that is greater than the sentinel.
             */
            while (S[++lowerIndex] < sentinel && lowerIndex < tailIndex);
            
            /*
             * Find the first element starting down from upper index 
             * that is lesser than the sentinel.
             */
            while (S[--upperIndex] > sentinel && upperIndex > headIndex);
            
            if (lowerIndex >= upperIndex) {
                break;
            }
            
            /*
             * Swap an element lesser than the sentinel with 
             * an element greater than the sentinel.
             */
            final int temporary = S[lowerIndex];
            S[lowerIndex] = S[upperIndex];
            S[upperIndex] = temporary;
        }
        
        // Swap sentinel to its pivot location.
        S[headIndex] = S[upperIndex];
        S[upperIndex] = sentinel;
        
        return upperIndex;
    }
    
}
Out[5]:
sorting.quick_sort.QuickSort
In [6]:
package sorting.quick_sort;

import java.util.Arrays;

final int[] S = new int[] {7, 5, 0, 1, 6, 2, 4, 2};

QuickSort.quickSort(S, 0, S.length - 1);

System.out.println(Arrays.toString(S));

[0, 1, 2, 2, 4, 5, 6, 7]
Out[6]:
null

Counting Sort ($O(n)$)

In [7]:
package sorting.counting_sort;

class CountingSort {
    
    public static void countingSort(int[] S, int cardinality) {
        final int[] counts = new int[cardinality];
        final int[] buffer = new int[S.length];
        
        // Count all distinct elements in S.
        for (int index = 0; index < S.length; index++) {
            counts[S[index]]++;
        }
        
        /*
         * Inductively, augment counts to contain the sorted positions.
         *
         * Intuition: You can only be inserted into the sorted array,
         * until after all values smaller than you have been inserted.
         */
        for (int index = 1; index < cardinality; index++) {
            counts[index] += counts[index - 1];
        }
        
        // Map S to its sorted positions into buffer.
        for (int index = 0; index < S.length; index++) {
            /*
             * Decrement because counts start from 1, 
             * and array indices start from 0.
             */
            buffer[--counts[S[index]]] = S[index];
        }
        
        // Flush the buffer into S.
        for (int index = 0; index < S.length; index++) {
            S[index] = buffer[index];
        }
    }
    
}
Out[7]:
sorting.counting_sort.CountingSort
In [8]:
package sorting.counting_sort;

import java.util.Arrays;

final int[] S = new int[] {7, 5, 0, 1, 6, 2, 4, 2};

CountingSort.countingSort(S, 8);

System.out.println(Arrays.toString(S));

[0, 1, 2, 2, 4, 5, 6, 7]
Out[8]:
null

Radix Sort ($O(n)$)

In [9]:
package sorting.radix_sort;

import java.util.Arrays;
import java.util.Collections;

class RadixSort {
    
    /*
     * Because counting sort is stable, 
     * we can sort S by digits of 10 from 1s to 10...0s.
     */
    public static void radixSort(int[] S) {
        int maximum = S[0];
        
        for (int index = 0; index < S.length; index++) {
            if (maximum < S[index]) {
                maximum = S[index];
            }
        }
        
        for (int exp = 1; (maximum / exp) > 0; exp *= 10) {
            countingSort(S, exp);
        }
    }
    
    private static void countingSort(int[] S, int exp) {
        final int[] counts = new int[10];
        final int[] buffer = new int[S.length];
        
        for (int index = 0; index < S.length; index++) {
            counts[(S[index] / exp) % 10]++;
        }
        
        for (int index = 1; index < 10; index++) {
            counts[index] += counts[index - 1];
        }
        
        for (int index = 0; index < S.length; index++) {
            buffer[--counts[(S[index] / exp) % 10]] = S[index];
        }
        
        for (int index = 0; index < S.length; index++) {
            S[index] = buffer[index];
        }
    }
    
}
Out[9]:
sorting.radix_sort.RadixSort
In [10]:
package sorting.radix_sort;

import java.util.Arrays;

final int[] S = new int[] {7, 5, 0, 1, 6, 2, 4, 2};

RadixSort.radixSort(S);

System.out.println(Arrays.toString(S));

[0, 1, 2, 2, 4, 5, 6, 7]
Out[10]:
null

Binary Search ($O\log(n)$)

If an array is sorted, binary search can test whether an element exists in $O(\log(n)$ time.

In [11]:
package sorting.binary_search;

class BinarySearch {

    // Classic:
    public static int binarySearch(int[] S, int key) {
        int headIndex = 0;
        int tailIndex = S.length - 1;

        while (headIndex <= tailIndex) {
            final int medianIndex = headIndex + (tailIndex - headIndex) / 2;

            if (key < S[medianIndex]) {
                tailIndex = medianIndex - 1;
            } else if (key > S[medianIndex]) {
                headIndex = medianIndex + 1;
            } else {
                return medianIndex;
            }
        }

        return -1;
    }
    
    // Alternative:
    // Advantage: Returns where key should be inserted.
    public static int alternativeSearch(int[] S, int key) {
        int index = 0;
        
        for (int offset = S.length / 2; offset >= 1; offset /= 2) {
            while ((index + offset) < S.length && S[index + offset] <= key) {
                index += offset;
            }
        }
        
        return index;
    }

}
Out[11]:
sorting.binary_search.BinarySearch

Application: Uniqueness Testing

  1. Sort a collection by increasing order such that any repeated items will be adjacent to each other.
  2. Traverse through the collection testing if S[i - 1] == S[i] to find duplicates.
In [12]:
import java.util.Arrays;

final int[] S = new int[] {7, 5, 0, 1, 6, 2, 4, 2};

Arrays.sort(S);

for (int i = 1; i < S.length; i++) {
    if (S[i - 1] == S[i]) {
        System.out.println("Not Unique");
    }
}

Not Unique
Out[12]:
null

Applications: Deleting Duplicates

  1. Sort a collection by increasing order such that any repeated items will be adjacent to each other.
  2. Traverse through the collection testing if S[back] != S[i].
  3. If S[back] != S[i], increment back and copy S[i] to S[back].
In [13]:
import java.util.Arrays;

int[] S = new int[] {7, 5, 0, 1, 6, 2, 4, 2};

Arrays.sort(S);

int back = 0;
int length = S.length;

for (int i = 1; i < S.length; i++) {
    if (S[back] != S[i]) {
        back++;
        S[back] = S[i];
    } else {
        length--;
    }
}

S = Arrays.copyOf(S, length);

System.out.println(Arrays.toString(S));

[0, 1, 2, 4, 5, 6, 7]
Out[13]:
null

Applications: Prioritizing Events

  1. Sort the events by increasing deadlines.
    • Although a priority queue can be used, sorting is sufficient if the set of events does not change during execution.
In [14]:
package sorting.prioritizing_events;

class Event {
    final int date;
    final int item;
    
    public Event(int date, int item) {
        this.date = date;
        this.item = item;
    }
    
    @Override
    public String toString() {
        return String.format(
            "Event(date=%d,item=%d)", 
            this.date, 
            this.item
        );
    }
}
Out[14]:
sorting.prioritizing_events.Event
In [15]:
package sorting.prioritizing_events;

import java.lang.Integer;
import java.util.Comparator;

class EventDateComparator implements Comparator<Event> {
    
    @Override
    public int compare(Event o1, Event o2) {
        return Integer.compare(o1.date, o2.date);
    }
    
}
Out[15]:
sorting.prioritizing_events.EventDateComparator
In [16]:
package sorting.prioritizing_events;

import java.util.Arrays;

Event[] S = new Event[] {
    new Event(7, 5), 
    new Event(0, 1), 
    new Event(6, 2), 
    new Event(4, 2)
};

Arrays.sort(S, new EventDateComparator());

System.out.println(Arrays.toString(S));

[Event(date=0,item=1), Event(date=4,item=2), Event(date=6,item=2), Event(date=7,item=5)]
Out[16]:
null

Applications: Median/Selection

  1. Sort a collection by increasing order to retrieve the $k$th largest item.
In [17]:
import java.util.Arrays;

final int[] S = new int[] {7, 5, 0, 1, 6, 2, 4, 2};

Arrays.sort(S);

System.out.println(String.format("Minimum: %d", S[0]));
System.out.println(String.format("Maximum: %d", S[S.length - 1]));
System.out.println(String.format("Median: %d", S[S.length / 2]));

Minimum: 0
Maximum: 7
Median: 4
Out[17]:
null

Applications: Frequency Counting

  1. Sort a collection by increasing order such that any repeated items will be adjacent to each other.
  2. Traverse through the collection testing if S[i - 1] == S[i] to maintain a running count or frequency of the item until S[i - 1] != S[i].
In [18]:
import java.util.Arrays;

final int[] S = new int[] {4, 4, 1, 2, 0, 1, 3, 6, 5, 1, 0, 7, 1, 4, 1, 4};

Arrays.sort(S);

int frequency = 1;

for (int i = 1; i < S.length; i++) {
    if (S[i - 1] != S[i]) {
        System.out.println(
            String.format("Frequency of %d: %d", S[i - 1], frequency)
        );
        frequency = 1;
    } else {
        frequency++;
    }
}

System.out.println(
    String.format("Frequency of %d: %d", S[S.length - 1], frequency)
);

Frequency of 0: 2
Frequency of 1: 5
Frequency of 2: 1
Frequency of 3: 1
Frequency of 4: 4
Frequency of 5: 1
Frequency of 6: 1
Frequency of 7: 1
Out[18]:
null

Applications: Set Intersection/Union

  1. If both sets have been sorted, they can be merged by repeatedly taking the smaller of the two head elements, placing them into the new set if desired, and then deleting the head from the appropriate list.
In [19]:
import java.util.Arrays;

final int[] A = new int[] {7, 4, 5, 0, 6, 3};
final int[] B = new int[] {5, 0, 4, 1, 7, 2};
int[] C = new int[A.length + B.length];

Arrays.sort(A);
Arrays.sort(B);

int i = 0;
int j = 0;
int k = 0;

while (i < A.length && j < B.length) {
    if (A[i] < B[j]) {
        C[k++] = A[i++];
    } else if (A[i] > B[j]) {
        C[k++] = B[j++];
    } else {
        C[k++] = A[i];
        i++;
        j++;
    }
}

while (i < A.length) {
    C[k++] = A[i++];
}

while (i < B.length) {
    C[k++] = B[j++];
}

C = Arrays.copyOf(C, k);

System.out.println(String.format("Union: %s", Arrays.toString(C)));

Union: [0, 1, 2, 3, 4, 5, 6, 7]
Out[19]:
null
In [20]:
import java.lang.Math;
import java.util.Arrays;

final int[] A = new int[] {7, 4, 5, 0, 6, 3};
final int[] B = new int[] {5, 0, 4, 1, 7, 2};
int[] C = new int[Math.min(A.length, B.length)];

Arrays.sort(A);
Arrays.sort(B);

int i = 0;
int j = 0;
int k = 0;

while (i < A.length && j < B.length) {
    if (A[i] < B[j]) {
        i++;
    } else if (A[i] > B[j]) {
        j++;
    } else {
        C[k++] = A[i];
        i++;
        j++;
    }
}

C = Arrays.copyOf(C, k);

System.out.println(String.format("Intersection: %s", Arrays.toString(C)));

Intersection: [0, 4, 5, 7]
Out[20]:
null

Applications: Finding a Target Pair (x + y == z)

  1. Sort a collection by increasing order.
  2. Traverse through the collection.
  3. As S[i] increases with i, decrease j such that (S[i] + S[j]) == z.
In [21]:
import java.util.Arrays;

final int[] S = new int[] {7, 5, 0, 1, 6, 3, 4, 2};

Arrays.sort(S);

int i = 0;
int j = S.length - 1;
while (i < S.length && j >= 0) {
    if ((S[i] + S[j]) == 3) {
        System.out.println(String.format("%d + %d = 3", S[i], S[j]));
        break;
    } else if ((S[i] + S[j]) > 3) {
        j--;
    } else {
        i++;
    }
}

0 + 3 = 3
Out[21]:
null

Applications: Efficient Searching

  1. Sort a collection by increasing order.
  2. Use binary search to test whether an element exists.
In [22]:
import java.util.Arrays;

final int[] S = new int[] {7, 5, 0, 1, 6, 2, 4, 2};

Arrays.sort(S);

System.out.println(
    String.format("Exists: %b", S[Arrays.binarySearch(S, 1)] == S[1])
);

Exists: true
Out[22]:
null