Linear Sort

There are sorting algorithms that run faster than time but they require special assumptions about the input sequence to be sort. Examples of sorting algorithms that run in linear time , are counting sort, radix sort and bucket sort. Counting sort and radix sort assume that the input consists of integers in a small range. Whereas, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval.

Since we already know that the best comparison-based sorting can to is . It is not difficult to figure out that linear-time sorting algorithms use operations other than comparisons to determine the sorted order.

Bucket Sort

Think

• Setup n buckets (n is the range of elements value)
• Put elements in each bucket
• Space consuming

Solution

public void bucketSort(int[] arr){
    // step 1: find range
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < arr.length; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }

    // step 2: setup bucket
    int[] bucket = new int[max - min + 1];
    for(int i = 0; i < arr.length; i++){
        bucket[arr[i] - min]++; 
    }

    // step 3: output the sort 
    int idx = 0;
    for(int i = 0; i < bucket.length; i++){
        while(bucket[i] > 0) {
            arr[idx++] = min + i;
            bucket[i]--;
        }
    }
}

Radix Sort

Think

Solution