Data Structure and Algorithms 3

Sorting Algorithms

• Bubble sort
  • From left to right, if the item is not in the right position, swap it with the right item;
  • after each iteration, the next largest item bubbles up and moves to its correct position
  • Time complexity:

public class BubbleSort {
  public void sort(int[] array) {
    boolean isSorted;
    for (var i = 0; i < array.length; i++) {
      isSorted = true;
      for (var j = 1; j < array.length - i; j++)
        if (array[j] < array[j - 1]) {
          swap(array, j, j - 1);
          isSorted = false;
        }
      if (isSorted)
        return;
    }
  }

  private void swap(int[] array, int index1, int index2) {
    var temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
  }

}

• Selection sort
  • In each pass, find the next smallest item and move it to the correct position
  • Time complexity: O(n²), no comparison in each pass

• Insertion sort
  • Each pass, select one item in the unsorted part and insert it into the sorted part. Instead of swapping, shift the items that larger than the current inserting item to make space for it

• Merge Sort
  • divide and conquer
  • need to allocate additional space

• Quick sort
  • Partition: select a pivot, arrange all the items smaller than the pivot on the left, and other items that greater than the pivot on the right. After each partition, the current pivot is in the right position.
  • In each pass, the size of the partitions are narrowed down.
• Partitioning:
  • pivot selection:
    • last item
    • pick randomly
    • use the middle index
    • average of the first, middle and last item
  • one pointer to iterate the array
  • one pointer to mark the boundary of the left and right partitions, the end of left partition, initial value is -1
  • if the item is smaller than pivot, increase the boundary pointer and swap the item
  • after each pass, move the pivot after the boundary pointer

• Counting Sort
  • Comparison sorts: bubble sort, selection sort, insertion sort, merge sort and quick sort
  • non-comparison sorts: counting sort, Bucket sort, Radix sort
  • range [0, K], count the occurrences of items in the input array
  • Space complexity: O(k), k is maximum value
  • Time complexity:
    • populate counts: O(n)
    • iterate counts: O(k)
    • total: O(n + k)
    • Time-memory trade-off
• Bucket sort
  • Distribute the items into buckets, sort in each bucket using another algorithm, and then combine them

Searching Algorithms

• Linear search
  • Time complexity: Best O(1), Worst O(n)
• Binary search
  • only works with sorted lists
  • Time complexity: O(log(n))
  • Space complexity: O(log(n)) -> recursive, O(1) -> iterative
• Ternary search
  • two middle pointers and divided into 3 partitions
    • partitionSize = (right – left) / 3
    • mid1 = left + partitionSize
    • mid2 = right – partitionSize
  • not more efficient than binary search
• Jump search
  • Improvement of linear search, but not faster than binary search
  • Divided into blocks, and jump into the blocks and do linear search within this block
  • ideal block size = square root of the n, n is the number of the items in the array
  • time complexity: O(√n)
• Exponential search
  • set a bound initial as 1, then double the bound when target larger than the item at the bound, otherwise, do linear search in range [bound/2, bound]