2020-04-23

LeetCode - Algorithms - 912. Sort an Array

Problem

Given an array of integers nums, sort the array in ascending order.

Java

Insertion sort

class Solution {
    public int[] sortArray(int[] nums) {
        int temp;
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp;
                }
            }
        }
        return nums;
    }
}

Submission Detail

10 / 10 test cases passed.
Runtime: 1323 ms, faster than 5.01% of Java online submissions for Sort an Array.
Memory Usage: 47.2 MB, less than 6.12% of Java online submissions for Sort an Array.

Mergesort

bottom-up mergesort

This method requires even less code than the standard recursive implementation.

class Solution {
    private void merge(int[] a, int[] aux, int lo, int mid, int hi) {
        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (aux[j] < aux[i]) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    public int[] sortArray(int[] nums) {
        final int N = nums.length;
        int[] aux = new int[N];
        for (int len = 1; len < N; len *= 2) {
            for (int lo = 0; lo < N - len; lo += len + len) {
                int mid = lo + len - 1;
                int hi = Math.min(lo + len + len - 1, N - 1);
                merge(nums, aux, lo, mid, hi);
            }
        }
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 7 ms, faster than 34.85% of Java online submissions for Sort an Array.
Memory Usage: 46.7 MB, less than 12.67% of Java online submissions for Sort an Array.

Top-down mergesort

recursive method

class Solution {
    private void merge(int[] a, int[] aux, int lo, int mid, int hi) {
        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (aux[j] < aux[i]) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    private void sort(int[] a, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    public int[] sortArray(int[] nums) {
        final int N = nums.length;
        int[] aux = new int[N];
        sort(nums, aux, 0, N - 1);
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 6 ms, faster than 57.85% of Java online submissions for Sort an Array.
Memory Usage: 46.3 MB, less than 14.62% of Java online submissions for Sort an Array.

Shellsort

Example of simple idea leading to substantial performance gains.

class Solution {
    public int[] sortArray(int[] nums) {
        final int N = nums.length;
        int h = 1;
        for (; h < N / 3; h = 3 * h + 1) ;
        int temp;
        for (; h >= 1; h /= 3) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h; j -= h) {
                    if (nums[j] < nums[j - h]) {
                        temp = nums[j];
                        nums[j] = nums[j - h];
                        nums[j - h] = temp;
                    }
                }
            }
        }
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 1865 ms, faster than 5.04% of Java online submissions for Sort an Array.
Memory Usage: 46.2 MB, less than 18.92% of Java online submissions for Sort an Array.

Quicksort

1

class Solution {
    public int[] sortArray(int[] nums) {
        qsort(0,nums.length-1, nums);
        return nums;        
    }
    
    /**
     * Quicksort
     * Programming Pearls
     * @author John Bentley
     * @param l
     * @param u
     * @param inArr
     */
    private void qsort(int l, int u, int[] inArr) {
        if (l>=u) return;
        int m=l;
        for(int i=l+1;i<=u; i++)
            if (inArr[i]<inArr[l])
                swap(inArr, ++m, i);
        swap(inArr, l, m);
        qsort(l,m-1,inArr);
        qsort(m+1,u,inArr);
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }    
}

Submission Detail

10 / 10 test cases passed.
Runtime: 4 ms, faster than 91.33% of Java online submissions for Sort an Array.
Memory Usage: 46.8 MB, less than 6.12% of Java online submissions for Sort an Array.

quicksort with 3-way partitioning

class Solution {
    private void exch(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private void sort(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, gt = hi;
        int v = a[lo];
        int i = lo + 1;
        while (i <= gt) {
            if (a[i] < v) exch(a, lt++, i++);
            else if (a[i] > v) exch(a, i, gt--);
            else i++;
        }

        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }

    public int[] sortArray(int[] nums) {
        final int N = nums.length;
        sort(nums, 0, N - 1);
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 4 ms, faster than 89.87% of Java online submissions for Sort an Array.
Memory Usage: 46.9 MB, less than 12.99% of Java online submissions for Sort an Array.

selection sort

class Solution {
    public int[] sortArray(int[] nums) {
        final int N = nums.length;
        int temp;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (nums[j] < nums[min])
                    min = j;
            }
            temp = nums[min];
            nums[min] = nums[i];
            nums[i] = temp;
        }
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 1169 ms, faster than 5.10% of Java online submissions for Sort an Array.
Memory Usage: 46.3 MB, less than 86.77% of Java online submissions for Sort an Array.

heap sort

iterative

Heapsort breaks into two phases: heap construction, where we reorganize the original array into a heap, and the sortdown, where we pull the items out of the heap in decreasing order to build the sorted result.

Q. Why not use a[0] in the heap representation?

A. Doing so simplifies the arithmetic a bit. It is not difficult to implement the heap methods based on a 0-based heap where the children of a[0] are a[1] and a[2], the children of a[1] are a[3] and a[4], the children of a[2] are a[5] and a[6], and so forth, but most programmers prefer the simpler arithmetic that we use. Also, using a[0] as a sentinel value (in the parent of a[1]) is useful in some heap applications.

class Solution {
    private void exch(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private void sink(int[] pq, int k, int n) {
        while (2 * k <= (n - 1)) {
            int j = 2 * k;
            if (j < (n - 1) && pq[j] < pq[j + 1]) j++;
            if (!(pq[k] < pq[j])) break;
            exch(pq, k, j);
            k = j;
        }
    }

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        for (int k = (n - 1) / 2; k >= 0; k--)
            sink(nums, k, n);
        for (int k = n - 1; k > 0; k--) {
            exch(nums, 0, k);
            sink(nums, 0, k);
        }
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 6 ms, faster than 53.50% of Java online submissions for Sort an Array.
Memory Usage: 46.6 MB, less than 48.27% of Java online submissions for Sort an Array.

recursion

class Solution {
    private void exch(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private void sink(int[] pq, int k, int n) {
        int largest = k;
        int l = 2 * k + 1;
        int r = 2 * k + 2;
        if (l < n && pq[l] > pq[largest])
            largest = l;
        if (r < n && pq[r] > pq[largest])
            largest = r;
        if (largest != k) {
            exch(pq, k, largest);
            sink(pq, largest, n);
        }
    }

    public int[] sortArray(int[] nums) {
        int n = nums.length;
        for (int k = n / 2 - 1; k >= 0; k--)
            sink(nums, k, n);
        for (int k = n - 1; k > 0; k--) {
            exch(nums, 0, k);
            sink(nums, 0, k);
        }
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 7 ms, faster than 30.29% of Java online submissions for Sort an Array.
Memory Usage: 46.7 MB, less than 32.93% of Java online submissions for Sort an Array.

jdk PriorityQueue

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int[] sortArray(int[] nums) {
        Queue<Integer> q = new PriorityQueue<Integer>();
        for (int num : nums) {
            q.add(num);
        }
        int i = 0;
        while (q.size() > 0)
            nums[i++] = q.poll();
        return nums;
    }
}

Submission Detail

11 / 11 test cases passed.
Runtime: 18 ms, faster than 16.69% of Java online submissions for Sort an Array.
Memory Usage: 47.7 MB, less than 11.36% of Java online submissions for Sort an Array.