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


  • 12

    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];
    	}
    }
    
    void radixSort(vector<int> &X){
    	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 };
    	radixSort(test2);
    	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;
    }

  • 1
    L

    The implementation you gave here for radix sort is not O(1) auxiliary space. Unfortunately, radix sort with O(1) auxiliary space is non-trivial. Your comments are misleading.

    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());.


  • 0
    L

    can u give out a better solution?


  • 0
    L

    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];
    }
    

Log in to reply
 

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