Clean C++ implementation of 3 linear-time-sort-alg with detailed explaination

• As we can see, we should grasp all the 3 typical linear-time-sorting algorithm implementation.
All the following 3 implementations have been modified from the GeeksForGeeks.
I have change the counting sort implementation to support negative numbers.
And the bucket support any float array input.

counting sort [ stable ] [ support:+/- intergers ]

radix sort [ use counting sort as sub-routine] [ support only
positive intergers]

bucket sort [support float : we need to change the array to in the
range [0, 1) ]

``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
``````
``````/* counting sort  Time O(N)  Space O(N+range) */
/*
support : positive / negative arrays
the last travese the array X :
FORWARD->not stable
BACKWARD->stable
*/
``````
``````void countingSort(vector<int>& X){
int len = X.size();
int start = INT_MAX, end = INT_MIN;
for (int i = 0; i < len; i++){
start = min(start, X[i]);
end = max(end, X[i]);
}
int range = end - start + 1;
vector<int> count(range, 0);
vector<int> result(len, 0);
for (int i = 0; i < len; i++){
count[X[i]-start]++;
}
for (int i = 1; i < range; i++){
count[i]=count[i-1]+count[i];
}
//for-ward traverse is not stable sorting
//for (int i = 0; i < len; i++)
//back-ward traverse is stable sorting
for (int i = len-1; i >= 0; i--){
//as we know that the count array recorded element should '-1' to get the index
result[count[X[i] - start]-1] = X[i];
count[X[i] - start]--;
}
for (int i = 0; i < len; i++){
X[i] = result[i];
}
}
``````
``````/* Radix sort  Time O(log(base,MAX)*(N+base))  Space O(constant)  default:base=10 */
/*
support : only positive interger
can only deal with positive integers or change the float number
of the specified precision to intergers by multiplying 10^n
*/
``````
``````void countingSort(vector<int>& X, int exp, int base){
int len = X.size();
int start = INT_MAX, end = INT_MIN;
for (int i = 0; i < len; i++){
start = min(start, (X[i] / exp)%base);
end = max(end, (X[i] / exp) % base);
}
int range = end - start + 1;
vector<int> count(range, 0);
vector<int> result(len, 0);
for (int i = 0; i < len; i++){
count[(X[i] / exp) % base -start]++;
}
for (int i = 1; i < range; i++){
count[i] = count[i - 1] + count[i];
}
//back-ward traverse is stable sorting
for (int i = len - 1; i >= 0; i--){
//as we know that the count array recorded element should '-1' to get the index
result[count[(X[i] / exp) % base -start] - 1] = X[i];
count[(X[i] / exp) % base - start]--;
}
for (int i = 0; i < len; i++){
X[i] = result[i];
}
}

int len = X.size();
int max_val = INT_MIN;
int base = 10;
for (int i = 0; i < len; i++) max_val = max(X[i], max_val);
for (int exp = 1; max_val / exp>0; exp *= base){
countingSort(X, exp, base);
}
}
``````
``````/* bubble sort  Time   Space */
/*
support : any float & int numbers
sort a large set of floating nubmers in range from 0.0 to 1.0
uniformly distributed across the range
the key idea is :
the insertion sort for all individual bucket is O(N)
*/
``````
``````void bucketSort(vector<float>& X){
int len = X.size();
float max_val = X[0], min_val = X[0];;
for (int i = 1; i < len; i++) {
max_val = max(max_val, X[i]);
min_val = min(min_val, X[i]);
}
max_val++;

vector<vector<float>> bucket(len, vector<float>());
for (int i = 0; i < len; i++){
int index = len*(X[i]-min_val)/(max_val-min_val);
bucket[index].push_back(X[i]);
}

for (int i = 0; i < len; i++)	sort(bucket[i].begin(), bucket[i].end());

int index = 0;
for (int i = 0; i < len; i++)
for (int j = 0; j < bucket[i].size(); j++)
X[index++] = bucket[i][j];
}
``````

/* test all the 3-linear-sorting-implementation */

``````int main(){
vector<int> test1 = { 11, -200, 14, -2000, 30, 400, 10, 22, 456 };
countingSort(test1);
cout << endl<<"counting Sort result: ";
for (int i = 0; i < test1.size(); i++)	 cout << test1[i] <<" - ";
vector<int> test2 = { 11, 200, 14, 2000, 30, 400, 10, 22, 456 };
cout << endl << "radix Sort result: ";
for (int i = 0; i < test2.size(); i++)	 cout << test2[i] << " - ";
vector<float> test3 = { 11, -200, 14, -2000, 30, 400, 10, 22, 456 };
bucketSort(test3);
cout << endl << "bucket Sort result: ";
for (int i = 0; i < test3.size(); i++)	 cout << test3[i] << " - ";
return 0;
}``````

The 3rd sort in your post is not a linear sort, consider the worst case all n-1 number fall in the same bucket, and you are reusing `sort(bucket[i].begin(), bucket[i].end());`.

• can u give out a better solution?

• In the radix sort, it is unnecessary for u to calculate the maximum and minimum value in the counting sort,
because we know that the max range is 10;
So, that counting sort can be rewritten as follows:

``````void countSort(vector<int>& v, int exp, int base)
{
vector<int> count(10, 0);
for(int& i: v)
{
int index = (i/exp)%base;
++count[index]
}
for(int i=1; i<10; i++)
count[i] += count[i-1];
vector<int> result(v.size(), 0);
for(int i=v.size()-1; i>=0; --i)
{
int index = count[(v[i]/exp)%base];
result[index-1] = i;
--count[(v[i]/exp)%base];
}
for(int i=0; i<v.size(); i++)
v[i] = result[i];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.