[Leetcode]Sorting

Overview

bigO cheat sheet

Algorithm	Time Complexity
QuickSort	O(n^2)
MergeSort	O(n(logn))
HeapSort	O(n(logn))
BubbleSort	O(n^2)
InsertionSort	O(n^2)
SelectionSort	O(n^2)
BucketSort	O(n^2)
RadixSort	O(nk)
CountingSort	O(n+k)

Need to use Java Comparable Interface. It has a compareTo() method (return negative if A.compareTo(B) when A < B)

When calculating time complexity, we need to count the number of comparisons and number of swaps.

// Sorting apples by weight
public class Apple implements Comparable<Apple> {
    private String variety;
    private Color color;
    private int weight;
    @Override
    public int compareTo(Apple other) {
        if (this.weight < other.weight) {
            return -1;
        }
        if (this.weight == other.weight) {
            return 0;
        }
        return 1;
    }
}

// Sorting by multiple variables

public class Apple implements Comparable {
    private String variety;
    private Color color;
    private int weight;
    @Override
    public int compareTo(Apple other) {
      int result = this.variety.compareTo(other.variety);
      if (result == 0) {
            result = this.color.compareTo(other.color);
       }
      if (result == 0) {
            result = Integer.compare(this.weight, other.weight);
       }
      return result;
    }
}

Selection Sort

Video Introduction: https://www.youtube.com/watch?v=xWBP4lzkoyM

Logic: Array is considered into two parts: unsorted and sorted.(initially the whole array is unsorted)

Selection 1. Select the lowest element in the remaining array
Swap 2. Bring it to the starting position
Counter Shift 3. Change the counter for unsorted array by one

Time Complexity: O(n^2) (n^2/2 comparisons and n swaps)

public static int[] selectionSort(int[] arr) {
        int minIndex = Integer.MIN_VALUE;

        for (int i = 0; i < arr.length; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = min;
            arr[minIndex] = temp;
        }
        return arr;
    }

4. Median of Two Sorted Arrays

Leetcode: https://leetcode.com/problems/median-of-two-sorted-arrays/description/

[Solution] Merge two sorted array and select the median according to if the big array’s length is odd or even.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Selection sort and return
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0 && n == 0) return 0;
        int index = 0;
        int[] arr = new int[m+n];
        boolean odd = (m + n) % 2 == 1 ? true : false;
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                arr[index] = nums1[i];
                i++;
                index++;
            } else if (nums1[i] > nums2[j]) {
                arr[index] = nums2[j];
                j++;
                index++;
            } else {
                arr[index] = nums1[i];
                index++;
                i++;
                arr[index] = nums2[j];
                j++;
                index++;
            }
            if (index == (n+m)/2 + 1) break;

        }
        while (i < m) {
                arr[index] = nums1[i];
                i++;
                index++;
                if (index == (n+m)/2 + 1) break;
            }
        while (j < n) {
            arr[index] = nums2[j];
            j++;
            index++;
            if (index == (n+m)/2 + 1) break;
        }
        if (odd) {
            return (float)(arr[(n+m)/2]);
        } else {
            return (float)(arr[(n+m)/2 - 1] + arr[(n+m)/2]) / 2.0;
        }
    }
}

Bubble Sort

Vido: https://www.youtube.com/watch?v=nmhjrI-aW5o&ab_channel=GeeksforGeeks

Time Complexity: O(N^2), (slow)
Space Complexity: O(1)

Very inefficient
Keep Swapping adjacent elements.

public static int[] bubbleSort(int[] arr) {
    boolean isSorted = false;
    int lastSorted = arr.length - 1;
    while(!isSorted) {
        isSorted = true;
        for (int i = 0; i < lastSorted; i++) {
            if (arr[i] > arr[i + 1]) {
                isSorted = false;
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        lastSorted--;
    }
    return arr;
}

Insertion Sort

Video Introduction: https://www.youtube.com/watch?v=lCzQvQr8Utw

Start from the second element cur in the array. Compare it with all of the elements before it, if the cur is smaller than element prev, insert it before prev and shift the elements backwards until reach to cur‘s original position.

Time Complexity: O(N^2)
Space Complexity: O(N)

public static void insertionSort(int[] arr) {
    if (arr.length < 2) return;
    for (int i = 1; i < arr.length; i++) {
        int j = i - 1;
        // find the insertion point
        while (j >= 0 && arr[i] < arr[j]) j--;
        j++;

        System.out.println("Compare: " + arr[i] + " and "  +arr[j]);
        // shifting
        int temp = arr[i];
        for (int k = i; k > j; k--) {
            arr[k] = arr[k - 1];
        }
        // insrting
        arr[j] = temp;
        System.out.println("Finish Swapping: " + Arrays.toString(arr));
    }
}

147. Insertion Sort List

Leetcode: https://leetcode.com/problems/insertion-sort-list/description/

[Solution]

1. Create a dummy node as head of the list
2. Use pointer i to go through the list and use pointer j to compare i and the list before j to find the insertion point
3. Insert i to desired point

// O(n^2)
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        // dummy node
        ListNode prev = new ListNode(0);
        prev.next = head;
        head = prev;

        ListNode j = head.next;
        ListNode i = j.next;

        while (i != null) {
            // find the insertion point
            ListNode next = i.next;
            while (j.val < i.val){
                prev = j;
                j = j.next;
            }
            if (i.val <= j.val) {
                prev.next = i;
                i.next = j;

                ListNode tailj = j;
                while (tailj.next != i) tailj = tailj.next;               
                tailj.next = next;
            }
            i = next;
            j = head.next;
            prev = head;
        }
        return head.next;
    }
}

def insertionSortList(self, head: ListNode) -> ListNode:
    dummy = ListNode(-float('inf'))
    while head:
        nxt = head.next
        sted, prev = dummy, dummy
        while sted and sted.val < head.val:
            prev = sted
            sted = sted.next # insert head after prev, before sted
        prev.next = head
        head.next = sted
        head = nxt
    return dummy.next

Quick Sort

Video: https://www.youtube.com/watch?v=7h1s2SojIRw

More like a Two Pointers algorithm. Keep a head pointer, and a tail pointer.

Uses Divide and Conquer strategy, divide problems to subproblems and solve subproblems.

1. Pick a pivot
2. Two pointers from head and tail of the array, swap the element till every element smaller than the pivot is on left (doesn’t have to be before the pivot point), and every element larger than pivot in on the right side.
3. Repeat precess 1, 2 to left side and right side, until the array is sorted

Time Complexity O(Nlog(N)) average, O(N^2) worst

public static void quickSort(int[] arr, int head, int tail) {
        if (head > tail) return;
        if (head < tail) {
            int index = partition(arr, head, tail);
            quickSort(arr, head, index - 1);
            quickSort(arr, index + 1, tail);
        }
    }

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// return partition point
private static int partition(int[] arr, int head, int tail) {
    int i = head, j = tail;
    int pivot = arr[head];
    while (i < j) {
        // find first pair of numbers to swap
        while (i < arr.length && arr[i] <= pivot) i++;
        while (j >= 0 && arr[j] > pivot) j--;
        // swap
        if (i < j) swap(arr, i, j);
    }
    swap(arr, head, j);
    return j;
}

215. Kth Largest Element in an Array

Leetcode: https://leetcode.com/problems/kth-largest-element-in-an-array/

Kth largest element == (N - k + 1)th smallest element

1. Partition: select a random pivot_index, return a partition index
2. Select: recursively find the (N - k + 1)th smallest element
3. Note: in the select step, we compare (N - k + 1) with partition index and only go to one direction. Thus the time complexity can be O(n)

def findKthLargest(self, nums: List[int], k: int) -> int:
    p = len(nums) - k + 1 # Find p th smallest element
    def partition(left, right, pivot_index): # return partition point
        pivot = nums[pivot_index]
        nums[right], nums[pivot_index] = nums[pivot_index], nums[right]
        small = left
        for i in range(left, right):
            if nums[i] < pivot:
                nums[small], nums[i] = nums[i], nums[small]
                small += 1
        nums[right], nums[small] = nums[small], nums[right]
        return small
    
    def select(left, right):
        # return kth smallest element in left, right
        if left == right:
            return nums[left]
        pivot_index = random.randint(left, right)
        index = partition(left, right, pivot_index)
        if p == index + 1:
            return nums[index]
        elif p < index + 1:
            return select(left, index - 1)
        else:
            return select(index + 1, right)
    return select(0, len(nums) - 1)

Merge Sort

Introduction: https://www.youtube.com/watch?v=TzeBrDU-JaY
Time Complexity Worst case: O(NlogN)

1. Divide and Conquer
2. Divide the array into left subarray and right subarray
3. Recursively sort each subarray till the length of subarray == 1, and merge subarray when return to the upper level of recursion

public static int[] mergeSort(int[] arr) {
    // System.out.println("arr: " + Arrays.toString(arr));
    if (arr.length == 1) return arr;

    int mid = arr.length / 2 - 1;

    int[] left = Arrays.copyOfRange(arr, 0, mid + 1);
    int[] right = Arrays.copyOfRange(arr, mid + 1, arr.length);
    left = mergeSort(left);
    right = mergeSort(right);
    return merge(left, right);
}

private static int[] merge (int[] left, int[] right) {
    // System.out.println("merge" + Arrays.toString(left) + " and " + Arrays.toString(right));
    int[] res = new int[left.length + right.length];
    int i = 0, j = 0, k = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            res[k] = left[i];
            i++;
        } else {
            res[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < left.length) {
        res[k] = left[i];
        i++;
        k++;
    }
    while (j < right.length) {
        res[k] = right[j];
        j++;
        k++;
    }
    return res;
}

148. Sort List

Leetcode: https://leetcode.com/problems/sort-list/description/

Video: https://www.youtube.com/watch?v=M1TwY0nsTZA

[Solution]: First use fast-slow pointers find the middle point of the list, then use mergeSort recursively sort the list.

[Solution 1]: Merge sort top down (recursive).
Time Complexity: O(nlogn)
Space Complexity: O(logn)

class Solution:
    def split(self, head):
        prev, slow, fast = head, head, head
        while fast and fast.next:
            prev = slow
            slow, fast = slow.next, fast.next.next
        prev.next = None
        return head, slow
    
    def merge(self, a, b):
        dummy = ListNode(0)
        cur = dummy
        while a and b:
            if a.val <= b.val:
                cur.next, a = a, a.next
            else:
                cur.next, b = b, b.next
            cur = cur.next
        cur.next = a or b
        return dummy.next
    
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        first, second = self.split(head)
        return self.merge(self.sortList(first), self.sortList(second))

315. Count of Smaller Numbers After Self

Leetcode: https://leetcode.com/problems/count-of-smaller-numbers-after-self/

My Merge Sort solution (correct but TLE)

def countSmaller(self, nums):
    nums = [(i, nums[i]) for i in range(len(nums))]
    res = [0] * len(nums)
    def sort(nums, res):
        if not nums:
            return []
        if len(nums) == 1:
            return [nums[0]]
        mid = len(nums) // 2
        left = sort(nums[:mid], res)
        right = sort(nums[mid:], res)
        temp = []
        l, r = 0, 0
        small = 0
        while l < len(left) and r < len(right):
            if left[l][1] <= right[r][1]:
                temp.append(left[l])
                l += 1
            else:
                temp.append(right[r])
                r += 1
                for tup in left[l:]:
                    res[tup[0]] += 1
        if l < len(left):
            temp += left[l:]
        if r < len(right):
            temp += right[r:]
        return temp
    s = sort(nums, res)
    return res

Stefan’s Merge Sort solution

def countSmaller(self, nums):
    res = [0] * len(nums)
    def sort(enum):
        mid = len(enum) // 2
        if mid: # if mid == 0, directly return enum
            left, right = sort(enum[:mid]), sort(enum[mid:])
            i, j = 0, 0
            while i < len(left) or j < len(right):
                if j == len(right) or (i < len(left) and left[i][1] <= right[j][1]):
                    enum[i + j] = left[i] # update sorted
                    res[left[i][0]] += j
                    i += 1
                else:
                    enum[i + j] = right[j]
                    j += 1
        return enum
    sort(list(enumerate(nums)))
    return res

Heap Sort

Video Intro: https://www.youtube.com/watch?v=MtQL_ll5KhQ
Code Intro: https://www.youtube.com/watch?v=B7hVxCmfPtM, from 31:00

Time Complexity O(NlogN)

A Heap is a binary tree T that stores a collection of entries at its nodes and that satisfies two additional properties:

1. Heap-order property: For every node v other than the root, the key stored at v is greater than or equal to the key stored at v‘s parent
   a. A path from the root to an external node of T is in nondecreasing order
   b. A minimum key is always stored at the root of T
2. Structural Property: it must complete
   a. We wish the heap T to have as small a height as possible

Max Heap: In a max heap, parent nodes are always greater than or equal to child nodes

Heap Sort

1. build_max_heap Build a Max Heap from the unordered array
2. Swap top node with the last node
3. Remove the last node
4. max_heapify Correct a single violation of the heap property in a subtree’s root.
   a. Assume that the trees rooted at left(i) and right(i) are Max Heaps
5. Repeat 3,4,5 steps till there’s only one node in the tree

   max_heapify(arr) {
     from i = n/2 down to 1: {from n/2+1 to n are all leaves}
       do max_heapify(arr, i)
   }

public static  void heapSort(int[] arr) {
    int n = arr.length;
    for (int i = n / 2; i >= 0; i--) {
        // put the largest element at the top of the array
        heapify(arr, n, i);
    }
    for (int i = n - 1; i >= 0; i--) {
        // swap the first and the last node
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // heapify subarray (len = n - 1)
        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int n, int i) {
    // given an array rooted at i, modify the array so that the largest element in the array is at the root
    // n is the size of the heap
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        // swap the root with the largest
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        // recursively heapify subtrees
        heapify(arr, n, largest);
    }
}

Bucket Sort

Bucket sort is mainly used when the input is uniformly distributed over a range. i.e, a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range.

1. Create n empty buckets (Or lists)
2. Do following for every array element arr[i]
   a. Insert arr[i] into bucket[n*array[i]]
3. Sort individual buckets using insertion sort
4. Concatenate all sorted buckets

public static void bucketSort(double[] arr) {
    int len = arr.length;
    ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>();
    // initialize bucketlist with empty linkedlist
    for (double a: arr) {
        bucketList.add(new LinkedList<Double>());
    }

    // Fill bucket with values
    for (double a: arr) {
        try {
            LinkedList cur = bucketList.get((int)Math.floor(a * 10));
            cur.add(a);
        } catch (Exception IndexOutOfBoundsException) {
            LinkedList<Double> temp = new LinkedList<Double>();
            temp.add(a);
            bucketList.add((int)Math.floor(a * 10), temp);
        }
    }

    int index = 0;
    LinkedList<Double> res = new LinkedList<Double>();

    // Sort each bucket
    for (LinkedList bucket: bucketList) {
        Collections.sort(bucket);
        res.addAll(bucket);
    }
    // Append the sorted bucket to the result
    for (int i = 0; i < len; i++) {
        arr[i] = res.get(i);
    }
    printBucket(bucketList);
}

private static void printBucket(ArrayList<LinkedList<Double>> bucketList) {
    for (LinkedList list: bucketList) {
        System.out.println("");
        for (Object ele: list) {
            System.out.print(ele + "-");
        }

    }
}

41. First Missing Positive

Leetcode: https://leetcode.com/problems/first-missing-positive/description/

[Solution] Put the positive elements to the right place.

class Solution {
    public int firstMissingPositive(int[] nums) {
        // Put the number at the right place
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] >= 1 && nums[i] <= nums.length && nums[i] != nums[nums[i]-1]) {
                // swap
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != j+1) return j+1;
        }
        return nums.length + 1;
    }
}

Counting Sort

Video Introduction: https://www.youtube.com/watch?v=TTnvXY82dtM
Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values. Then doing some arithmetic to calculate the position or each object in the output sequence.

This algorithm doesn’t require comparisons between items

1. Find the minimum and the maximum value: the range of the numbers
2. Create index array from min -> max
3. Create Count array to record the frequency of each item

               [5,2,3,1,2,6,7,9,2]
                ^
               -------------------
Index Array:    1,2,3,4,5,6,7,8,9 (from min to max)
                        ^
Count Array:   (1,3,1,0,1,1,1,0,1)
Increment:      1,4,5,5,6,7,8,8,9
                        ^ (put 5 to index = 6)
                        5 (change 6 -> 5)
               -------------------
resultIndex:    1,2,3,4,5,6,7,8,9 !(start from 1)
result:                   5

public static int[] countingSort(int[] arr) {
   // find the min and max value
   int min = findMinMax(arr)[0];
   int max = findMinMax(arr)[1];
   int[] result = new int[arr.length];

   // Build Index array
   int[] index = new int[ max-min + 1];
   for (int i = 0; i < max-min + 1; i++) {
       index[i]= i + min;
   }

   // Counting map
   HashMap<Integer, Integer> map = count(arr, index);
   for (int j = 0; j < arr.length; j++) {
       int temp = map.get(arr[j]);
       result[temp-1] = arr[j];
       map.put(arr[j], temp-1);
   }
   return result;
}

private static int[] findMinMax(int[] arr) {
   int[] res = new int[2];
   res[0] = Integer.MAX_VALUE;
   res[1] = Integer.MIN_VALUE;
   for (int i: arr) {
       res[0] = Math.min(res[0], i);
       res[1] = Math.max(res[1], i);
   }
   return res;
}

private static HashMap<Integer, Integer> count(int[] arr, int[] index) {
   HashMap<Integer, Integer> cnt = new HashMap<Integer, Integer>();
   for (Integer i : arr) {
       Integer ch = cnt.get(i);
       if (ch == null) {
           cnt.put(i, 1);
       } else {
           cnt.put(i, ch+1);
       }
   }
   HashMap<Integer, Integer> res = new HashMap<Integer, Integer>();
   res.put(index[0], cnt.get(index[0]));
   for (int i = 1; i < index.length; i++) { // 1,2,3,4...
       Integer t = cnt.get(index[i]);
       if (t == null) res.put(index[i], res.get(index[i-1]));
       else res.put(index[i], res.get(index[i-1])+cnt.get(index[i]));
   }
   System.out.println(Arrays.asList(res));

   return res;
}

Radix Sort

Video: https://www.youtube.com/watch?v=YXFI4osELGU

This algorithm is only used to sort numbers

We sort the numbers from least significant digit to most significant digit. Counting Sort is used as a subroutine to sort.

We know there are 10 digits from 0 to 9 that are used to form any number. So we’ll need 10 buckets labeled 0 to 9 to sort the unsorted numbers.

1. Find the largest number L, remember the number of its digits.
2. Make all other numbers have the same number of digits as L
3. If there are N digits in the biggest number, we will need to perform N number of passes

          [50, 21, 36, 1, 205, 6, 78, 92, 23]
Transform [050 021 036 010 205 060 078 092 023] // S
             ^   ^   ^   ^   ^   ^   ^   ^   ^
Put into buckets by tail digit:
   0    1    2    3    4    5    6    7    8    9  
|050| |021| |092||023||  ||205| |036| | | |078| | |
|010| |   | |   ||   ||  ||   | |   | | | |   | | |
|060| |   | |   ||   ||  ||   | |   | | | |   | | |

Update the S array by popping out(FIFO) each bucket
Transform [050 010 060 021 092 023 205 036 078]
Repeat to the next tail...

public static int[] radixSort(int[] arr) {
  // Find the largest
   int max = arr[0];
   for (int num : arr) {
       max = Math.max(max, num);
   }
   String lar = String.valueOf(max);
   List<String> full = new ArrayList<String>();

   // Add 0 to all other numbers
   for (int n: arr) {
       String stn = String.valueOf(n);
       while (stn.length()<lar.length()) {
           stn = "0" + stn;
       }
       full.add(stn); // ["010,028..."]
   }

   // Indexing list from 0-9
   List<Queue<String>> bucketList = new ArrayList<Queue<String>>(9);

   // Initialize bucketList with 9 empty queues
   for (int j = 0; j < 10; j++) {
       bucketList.add(j, new LinkedList<String>());
   }

   for (int i = lar.length() - 1; i>=0; i--) {
       for (String item: full) {
           int position = Integer.valueOf(String.valueOf(item.charAt(i)));
           Queue<String> qq = bucketList.get(position);
           qq.add(item);
       }

       // Update full by poping from buckets
       int pos = 0;
       for (Queue<String> bucket : bucketList) {
           while (bucket.size() != 0) {
               full.set(pos, bucket.poll());
               pos++;
           }
       }
   }
   // Transform full back to integer array
   for (int k = 0; k < arr.length; k ++) {
       arr[k] = Integer.valueOf(full.get(k));
   }
   return arr;
}