Yu's Coding Garden : leetcode Question: Maximum Gap
For this specific problem, bucket sort is not a good option because it usually works well on uniform distributions. Otherwise, in each bucket, the insertion sort may cause heavy burden on time complexity. Counting sort, has time complexity O(n + k), where k is the range of the elements. But when k > n^2, it is worse than the common sorting algorithms. So we use the radix sort for solving this problem.
The idea of radix sort is as follows:
Sort elements according to each digit (from lower to higher).
For each digit, use counting sort.
To sort array according to each digit, counting sort is used. Note that, we only need to have a array of size 10 to store the frequencies of elements. This is because we only consider and sort a single digit in each iteration of Radix sort.
The general form of counting sort is:
(1) Count the frequencies of each elements. (count[a[i]] ++, this also considers the duplicates)
(2) Get the index of each number in the output array. (count[i]+= count[i-1])
(3) Put numbers in order. (output[count[a[i]] = a[i], count[a[i]]-- to handle the duplicates)
For radix sort, there is minor modifications, details see the code below.
Read full article from Yu's Coding Garden : leetcode Question: Maximum Gap
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
We all know that, merge, heap or quick sorting algorithm can achieve no better than O(n Log n) time complexity. But for linear time requirement, bucket sort, counting sort and radix sort are often good options.For this specific problem, bucket sort is not a good option because it usually works well on uniform distributions. Otherwise, in each bucket, the insertion sort may cause heavy burden on time complexity. Counting sort, has time complexity O(n + k), where k is the range of the elements. But when k > n^2, it is worse than the common sorting algorithms. So we use the radix sort for solving this problem.
The idea of radix sort is as follows:
Sort elements according to each digit (from lower to higher).
For each digit, use counting sort.
To sort array according to each digit, counting sort is used. Note that, we only need to have a array of size 10 to store the frequencies of elements. This is because we only consider and sort a single digit in each iteration of Radix sort.
The general form of counting sort is:
(1) Count the frequencies of each elements. (count[a[i]] ++, this also considers the duplicates)
(2) Get the index of each number in the output array. (count[i]+= count[i-1])
(3) Put numbers in order. (output[count[a[i]] = a[i], count[a[i]]-- to handle the duplicates)
For radix sort, there is minor modifications, details see the code below.
Read full article from Yu's Coding Garden : leetcode Question: Maximum Gap
