Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have designed and implemented Parallel Radix Sort handling positive and negative numbers in C++ Programming Language.
Before diving into this, go through the Time Complexity Analysis of Basic version of Radix Sort.
Table of contents
- Introduction
- R1. MSD recursive approach
- R2. LSD recursive approach
- P1. MSD parallel approach
- using OpenMP
- P2. LSD parallel approach
- using std:thread
- using POSIX thread
Introduction
Radix sort is an algorithm that uses the radix,base,digit or element of a string or number to sort arrays. You can start the algorithm from left to right and that means the most significant digit (MSD) or from right to left and that means the least significant digit (LSD).
Before using the parallel approach it is very important to understand how the algorithm works.
For implementation we can use the recursive way to sort array numbers.
R1. MSD recursive approach
This approach is kind of straight forward. We can easily see that the bigger the most left radix is, the bigger the number is. Having this thought in mind we can setup bins for each numeral digit starting from -9,-8,...-1,0,1,...8,9 in total 19 bins or buckets.
Algorithm:
- determine the max width of a number in the array, i.e. its length as if it is a string
- start with first digit, the left most side
- place the number in the corresponding bin or bucket based on its digit
(if digit is less the the max width then digit is 0) - go to step 2 by moving the digit with 1 position to the right
- combine the array based on sorted bins
Time complexity is determined by the length of the biggest number in the array, say n, and the number of bins, say k, which in our case is constant to 19. So, the overall execution time will be in O(n).
Study case: -142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0
Very useful to know in case of negative numbers, every digit consisting the number will have the negative sign !
Ex. -142 will have the first digit -1, the second digit -4 and the last digit -2
A way of implementation
#include <iostream>
#include <sstream>
#include <vector>
#define BINS 19
using namespace std;
class Radix
{
vector<int> *radix;
int w;
public:
Radix(vector<int> &v)
{
radix = &v;
set_max_width();
}
void radix_sort(vector<int> &v, int digit)
{
vector<int> *temp = new vector<int> [BINS];
int i=0,j=0,k=0;
for(i=0;i<v.size();i++)
switch( get_digit(v[i],digit) )
{
case -9: temp[0].push_back( v[i] ); break;
case -8: temp[1].push_back( v[i] ); break;
case -7: temp[2].push_back( v[i] ); break;
case -6: temp[3].push_back( v[i] ); break;
case -5: temp[4].push_back( v[i] ); break;
case -4: temp[5].push_back( v[i] ); break;
case -3: temp[6].push_back( v[i] ); break;
case -2: temp[7].push_back( v[i] ); break;
case -1: temp[8].push_back( v[i] ); break;
case 0: temp[9].push_back( v[i] ); break;
case 1: temp[10].push_back( v[i] ); break;
case 2: temp[11].push_back( v[i] ); break;
case 3: temp[12].push_back( v[i] ); break;
case 4: temp[13].push_back( v[i] ); break;
case 5: temp[14].push_back( v[i] ); break;
case 6: temp[15].push_back( v[i] ); break;
case 7: temp[16].push_back( v[i] ); break;
case 8: temp[17].push_back( v[i] ); break;
case 9: temp[18].push_back( v[i] ); break;
}
for(i=0;i<BINS;i++)
if( temp[i].size() > 1 && digit + 1 < w)
radix_sort(temp[i], digit + 1);
for(i=0;i<BINS;i++)
{
if(temp[i].size()>0)cout<<"digit "<<digit<<": ";
for(j=0;j<temp[i].size();j++)
v[k++] = temp[i][j], cout<<v[k-1]<<" ";
if(temp[i].size()>0)cout<<endl;
}
}
void set_max_width()
{
ostringstream st;
string s;
int max = 0;
for(int i=0;i<radix->size();i++)
{
st <<( (*radix)[i] < 0 ? (*radix)[i] * -1 : (*radix)[i] );
s = st.str();
if(s.size() > max) max = s.size();
st.str(string()); //delete previous input
}
w = max;
}
int get_max_width()
{
return w;
}
int get_digit(int a, int digit)
{
ostringstream st;
string s;
int size=0;
if( a >= 0)
{
st << a;
s = st.str();
size = s.size();
for(int i=0; i < w - size; i++ ) s.insert(0,"0");
return (int)s[digit] - '0';
}
else
{
st << a;
s = st.str();
size = s.size() - 1; // minus the "-" character !!!
for(int i=0; i < w - size; i++ ) s.insert(1,"0");
return (int)s[digit+1]*-1 + '0';
}
}
vector<int> get_radix()
{
return *radix;
}
};
int main()
{
vector<int> v = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0};
Radix r(v);
r.radix_sort(v,0);
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
return 0;
}
Output:
digit 1: -183
digit 1: -142
digit 1: -100
digit 2: -12
digit 2: -10
digit 2: -1 -1
digit 2: 0 0
digit 2: 1
digit 2: 5
digit 1: -12 -10
digit 1: -1 -1 0 0 1 5
digit 1: 10
digit 2: 225
digit 2: 229
digit 1: 225 229
digit 0: -183 -142 -100
digit 0: -12 -10 -1 -1 0 0 1 5 10
digit 0: 100
digit 0: 225 229
-183 -142 -100 -12 -10 -1 -1 0 0 1 5 10 100 225 229
2. LSD recursive approach
When we start from right it is not possible to determine if that number is bigger or not. So, we must find another way to do so. At each step we might think to sort the numbers based on their digit. Because radix sort is a non-comparasion algorithm the only algorithm left to use is the counting sort.
Algorithm
- determine the max width of a number in the array, i.e. its length as if it is a string
- start with last digit, the right most side
- sort the elements using counting sort based on their radix
(if digit is less the the max width then digit is 0) - go to step 2 by moving the digit with 1 position to the left
Obs. This algorithm works for positive numbers only! If our array contains both positive and negative values, then we must split the array in 2 arrays each of them corresponding to the negative and positive elements. In case of the array with negative values, make all values positive and use the countig sort and after that recombine the array in reverse order placing the negative sign.
Time complexity in this case is determined mostly by the counting sort algorithm which is O(n+k).
Study case: -142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
class Radix
{
vector<int> *radix;
int w;
public:
Radix(vector<int> &v)
{
radix = &v;
set_max_width();
}
int get_max(vector<int> v)
{
int max;
if(v.size() >=0)
max = v[0];
if(v.size() > 1)
for(int i=1; i<v.size(); i++)
if(v[i] > max) max = v[i];
return max;
}
void counting_sort(vector<int> &v, int digit)
{
int i,j,max = get_max(v), count;
vector<int> count_array(max+1, 0);//initialize array with zeros
vector<int> sort_array(v.size());
for(i=0; i<v.size(); i++)
count_array[ get_digit(v[i], digit) ] ++; // count elements
for(i=1; i<count_array.size(); i++)
count_array[i] += count_array[i-1]; //increase with previous element
for(i=v.size()-1; i>=0; i--)
sort_array[ count_array[ get_digit(v[i], digit) ] -1 ] = v[i], //assign value
count_array[ get_digit(v[i], digit) ]--; //decrease element
v.clear();
v = sort_array;
}
void radix_sort(vector<int> &v, int digit)
{
int i;
vector<int> neg, pos;
for(i=0;i<v.size();i++)
{
if(v[i] < 0) neg.push_back(-v[i]);
if(v[i] >= 0) pos.push_back(v[i]);
}
if(!neg.empty()) counting_sort(neg,digit);
if(!pos.empty()) counting_sort(pos,digit);
if(digit == 0) //at the last step insert neg elem in reverse order
{
v.clear();
for(auto x:neg) v.insert(v.begin(),-x);
for(auto x:pos) v.insert(v.end(),x);
}
else
{
v.clear();
for(auto x:neg) v.insert(v.end(),-x);
for(auto x:pos) v.insert(v.end(),x);
}
cout<<"digit "<<digit<<": ";
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
cout<<endl;
if( digit - 1 >= 0)
radix_sort(v, digit - 1);
}
void set_max_width()
{
ostringstream st;
string s;
int max = 0;
for(int i=0;i<radix->size();i++)
{
st <<( (*radix)[i] < 0 ? (*radix)[i] * -1 : (*radix)[i] );
s = st.str();
if(s.size() > max) max = s.size();
st.str(string()); //delete previous input
}
w = max;
}
int get_max_width()
{
return w;
}
int get_digit(int a, int digit)
{
ostringstream st;
string s;
int size=0;
if( a >= 0)
{
st << a;
s = st.str();
size = s.size();
for(int i=0; i < w - size; i++ ) s.insert(0,"0");
return (int)s[digit] - '0';
}
else
{
st << a;
s = st.str();
size = s.size() - 1; // minus the "-" character !!!
for(int i=0; i < w - size; i++ ) s.insert(1,"0");
return (int)s[digit+1]*-1 + '0';
}
}
vector<int> get_radix()
{
return *radix;
}
};
int main()
{
vector<int> v = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0};
Radix r(v);
r.radix_sort(v, r.get_max_width() - 1);
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
return 0;
}
Output:
digit 2: -10 -100 -1 -1 -142 -12 -183 100 0 10 0 1 225 5 229
digit 1: -100 -1 -1 -10 -12 -142 -183 100 0 0 1 5 10 225 229
digit 0: -183 -142 -100 -12 -10 -1 -1 0 0 1 5 10 100 225 229
-183 -142 -100 -12 -10 -1 -1 0 0 1 5 10 100 225 229
P1. MSD parallel approach
using OpenMP library at the call of recursive function radix_sort will make the program to create a thread for each recursive call. It will be good to limit the numbers of threads to 1, as our function will be called only once.
#include <iostream>
#include <sstream>
#include <vector>
#include <omp.h>
#define BINS 19
using namespace std;
class Radix
{
vector<int> *radix;
int w;
public:
Radix(vector<int> &v)
{
radix = &v;
set_max_width();
}
void radix_sort(vector<int> &v, int digit)
{
vector<int> *temp = new vector<int> [BINS];
int i=0,j=0,k=0;
for(i=0;i<v.size();i++)
switch( get_digit(v[i],digit) )
{
case -9: temp[0].push_back( v[i] ); break;
case -8: temp[1].push_back( v[i] ); break;
case -7: temp[2].push_back( v[i] ); break;
case -6: temp[3].push_back( v[i] ); break;
case -5: temp[4].push_back( v[i] ); break;
case -4: temp[5].push_back( v[i] ); break;
case -3: temp[6].push_back( v[i] ); break;
case -2: temp[7].push_back( v[i] ); break;
case -1: temp[8].push_back( v[i] ); break;
case 0: temp[9].push_back( v[i] ); break;
case 1: temp[10].push_back( v[i] ); break;
case 2: temp[11].push_back( v[i] ); break;
case 3: temp[12].push_back( v[i] ); break;
case 4: temp[13].push_back( v[i] ); break;
case 5: temp[14].push_back( v[i] ); break;
case 6: temp[15].push_back( v[i] ); break;
case 7: temp[16].push_back( v[i] ); break;
case 8: temp[17].push_back( v[i] ); break;
case 9: temp[18].push_back( v[i] ); break;
}
for(i=0;i<BINS;i++)
if( temp[i].size() > 1 && digit + 1 < w)
#pragma omp parallel num_threads(1)
{
int id = omp_get_thread_num();
int total = omp_get_num_threads();
printf("process %d out of %d \n", id, total);
radix_sort(temp[i], digit + 1);
}
for(i=0;i<BINS;i++)
{
if(temp[i].size()>0)cout<<"digit "<<digit<<": ";
for(j=0;j<temp[i].size();j++)
v[k++] = temp[i][j], cout<<v[k-1]<<" ";
if(temp[i].size()>0)cout<<endl;
}
}
void set_max_width()
{
ostringstream st;
string s;
int max = 0;
for(int i=0;i<radix->size();i++)
{
st <<( (*radix)[i] < 0 ? (*radix)[i] * -1 : (*radix)[i] );
s = st.str();
if(s.size() > max) max = s.size();
st.str(string()); //delete previous input
}
w = max;
}
int get_max_width()
{
return w;
}
int get_digit(int a, int digit)
{
ostringstream st;
string s;
int size=0;
if( a >= 0)
{
st << a;
s = st.str();
size = s.size();
for(int i=0; i < w - size; i++ ) s.insert(0,"0");
return (int)s[digit] - '0';
}
else
{
st << a;
s = st.str();
size = s.size() - 1; // minus the "-" character !!!
for(int i=0; i < w - size; i++ ) s.insert(1,"0");
return (int)s[digit+1]*-1 + '0';
}
}
vector<int> get_radix()
{
return *radix;
}
};
int main()
{
vector<int> v = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0};
Radix r(v);
r.radix_sort(v,0);
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
return 0;
}
Output:
process 0 out of 1
digit 1: -183
digit 1: -142
digit 1: -100
process 0 out of 1
process 0 out of 1
digit 2: -12
digit 2: -10
process 0 out of 1
digit 2: -1 -1
digit 2: 0 0
digit 2: 1
digit 2: 5
digit 1: -12 -10
digit 1: -1 -1 0 0 1 5
digit 1: 10
process 0 out of 1
process 0 out of 1
digit 2: 225
digit 2: 229
digit 1: 225 229
digit 0: -183 -142 -100
digit 0: -12 -10 -1 -1 0 0 1 5 10
digit 0: 100
digit 0: 225 229
-183 -142 -100 -12 -10 -1 -1 0 0 1 5 10 100 225 229
P2. LSD parallel approach
Using std:thread is not making us to change very much the structure of the program. What we have to do is to comment the recursive call of our method and utilize the parallel call for it. Again, using join function will make our threads to wait for each other, otherwise we will get a wrong result because the computation order of the digits needs to be incremental.
#include <iostream>
#include <sstream>
#include <vector>
#include <thread>
using namespace std;
class Radix
{
vector<int> *radix;
int w;
public:
Radix(vector<int> &v)
{
radix = &v;
set_max_width();
}
int get_max(vector<int> v)
{
int max;
if(v.size() >=0)
max = v[0];
if(v.size() > 1)
for(int i=1; i<v.size(); i++)
if(v[i] > max) max = v[i];
return max;
}
void counting_sort(vector<int> &v, int digit)
{
int i,j,max = get_max(v), count;
vector<int> count_array(max+1, 0);//initialize array with zeros
vector<int> sort_array(v.size());
for(i=0; i<v.size(); i++)
count_array[ get_digit(v[i], digit) ] ++; // count elements
for(i=1; i<count_array.size(); i++)
count_array[i] += count_array[i-1]; //increase with previous element
for(i=v.size()-1; i>=0; i--)
sort_array[ count_array[ get_digit(v[i], digit) ] -1 ] = v[i], //assign value
count_array[ get_digit(v[i], digit) ]--; //decrease element
v.clear();
v = sort_array;
}
void radix_sort(vector<int> &v, int digit)
{
int i;
vector<int> neg, pos;
for(i=0;i<v.size();i++)
{
if(v[i] < 0) neg.push_back(-v[i]);
if(v[i] >= 0) pos.push_back(v[i]);
}
if(!neg.empty()) counting_sort(neg,digit);
if(!pos.empty()) counting_sort(pos,digit);
if(digit == 0) //at the last step insert neg elem in reverse order
{
v.clear();
for(auto x:neg) v.insert(v.begin(),-x);
for(auto x:pos) v.insert(v.end(),x);
}
else
{
v.clear();
for(auto x:neg) v.insert(v.end(),-x);
for(auto x:pos) v.insert(v.end(),x);
}
cout<<"digit "<<digit<<": ";
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
cout<<endl;
//if( digit - 1 >= 0)
// radix_sort(v, digit - 1);
}
void set_max_width()
{
ostringstream st;
string s;
int max = 0;
for(int i=0;i<radix->size();i++)
{
st <<( (*radix)[i] < 0 ? (*radix)[i] * -1 : (*radix)[i] );
s = st.str();
if(s.size() > max) max = s.size();
st.str(string()); //delete previous input
}
w = max;
}
int get_max_width()
{
return w;
}
int get_digit(int a, int digit)
{
ostringstream st;
string s;
int size=0;
if( a >= 0)
{
st << a;
s = st.str();
size = s.size();
for(int i=0; i < w - size; i++ ) s.insert(0,"0");
return (int)s[digit] - '0';
}
else
{
st << a;
s = st.str();
size = s.size() - 1; // minus the "-" character !!!
for(int i=0; i < w - size; i++ ) s.insert(1,"0");
return (int)s[digit+1]*-1 + '0';
}
}
vector<int> get_radix()
{
return *radix;
}
};
int main()
{
vector<int> v = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0};
Radix r(v);
vector<thread> vt;
for(int i=1; i<=r.get_max_width();i++)
{
vt.push_back( thread( &Radix::radix_sort, ref(r), ref(v), r.get_max_width() - i ) ),
vt[i-1].join();
}
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
return 0;
}
Output:
digit 2: -10 -100 -1 -1 -142 -12 -183 100 0 10 0 1 225 5 229
digit 1: -100 -1 -1 -10 -12 -142 -183 100 0 0 1 5 10 225 229
digit 0: -183 -142 -100 -12 -10 -1 -1 0 0 1 5 10 100 225 229
-183 -142 -100 -12 -10 -1 -1 0 0 1 5 10 100 225 229
using POSIX thread makes us to do some changes in the structure of the program especially on radix_sort function. It's declaration needs to be changed in accordance with the start_routine of the POSIX thread. And because of that, we are facing with the problem of sending paramenters to the function. Luckly when I design this class, I've used a pointer that keeps the address of the array that needs to be sorted. Having this in mind, we can easily replace the array parameter from the recursive approach with the member class that points to the array that needs to be sorted.
#include <iostream>
#include <sstream>
#include <vector>
#include <pthread.h>
using namespace std;
typedef void * (*function_ptr)(void *);
class Radix
{
vector<int> *radix;
int digit;
int w;
public:
Radix(vector<int> &v)
{
radix = &v;
set_max_width();
}
int get_max(vector<int> v)
{
int max;
if(v.size() >=0)
max = v[0];
if(v.size() > 1)
for(int i=1; i<v.size(); i++)
if(v[i] > max) max = v[i];
return max;
}
void counting_sort(vector<int> &v, int digit)
{
int i,j,max = get_max(v), count;
vector<int> count_array(max+1, 0);//initialize array with zeros
vector<int> sort_array(v.size());
for(i=0; i<v.size(); i++)
count_array[ get_digit(v[i], digit) ] ++; // count elements
for(i=1; i<count_array.size(); i++)
count_array[i] += count_array[i-1]; //increase with previous element
for(i=v.size()-1; i>=0; i--)
sort_array[ count_array[ get_digit(v[i], digit) ] -1 ] = v[i], //assign value
count_array[ get_digit(v[i], digit) ]--; //decrease element
v.clear();
v = sort_array;
}
//void radix_sort(vector<int> &v, int digit)
void* radix_sort(void *args)
{
int i;
vector<int> neg, pos;
for(i=0;i< radix->size();i++)
{
if(radix->at(i) < 0) neg.push_back(-radix->at(i) );
if(radix->at(i) >= 0) pos.push_back(radix->at(i) );
}
if(!neg.empty()) counting_sort(neg, digit);
if(!pos.empty()) counting_sort(pos, digit);
if(digit == 0) //at the last step insert neg elem in reverse order
{
radix->clear();
for(auto x:neg) radix->insert(radix->begin(),-x);
for(auto x:pos) radix->insert(radix->end(),x);
}
else
{
radix->clear();
for(auto x:neg) radix->insert(radix->end(),-x);
for(auto x:pos) radix->insert(radix->end(),x);
}
cout<<"digit "<<digit<<": ";
for(int i=0;i<radix->size();i++)
cout<<radix->at(i)<<" ";
cout<<endl;
//if( digit - 1 >= 0)
// radix_sort(v, digit - 1);
return NULL;
}
void set_max_width()
{
ostringstream st;
string s;
int max = 0;
for(int i=0;i<radix->size();i++)
{
st <<( (*radix)[i] < 0 ? (*radix)[i] * -1 : (*radix)[i] );
s = st.str();
if(s.size() > max) max = s.size();
st.str(string()); //delete previous input
}
w = max;
}
int get_max_width()
{
return w;
}
void set_digit(int digit)
{
this->digit = digit;
}
int get_digit(int a, int digit)
{
ostringstream st;
string s;
int size=0;
if( a >= 0)
{
st << a;
s = st.str();
size = s.size();
for(int i=0; i < w - size; i++ ) s.insert(0,"0");
return (int)s[digit] - '0';
}
else
{
st << a;
s = st.str();
size = s.size() - 1; // minus the "-" character !!!
for(int i=0; i < w - size; i++ ) s.insert(1,"0");
return (int)s[digit+1]*-1 + '0';
}
}
vector<int> get_radix()
{
return *radix;
}
};
int main()
{
vector<int> v = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0};
Radix r(v);
vector<pthread_t> vt;
pthread_t t;
for(int i=1; i<=r.get_max_width();i++)
{
vt.push_back( t );
r.set_digit(r.get_max_width()-i);
pthread_create(&vt[i-1], NULL, (function_ptr) &Radix::radix_sort, &r );
pthread_join( vt[i-1], NULL );
}
for(int i=0;i<v.size();i++)
cout<<(r.get_radix())[i]<<" ";
return 0;
}
Output:
main.cpp: In function ‘int main()’:
main.cpp:175:69: warning: converting from ‘void* (Radix::)(void)’ to ‘thread_ptr’ {aka ‘void* ()(void)’} [-Wpmf-conversions]
175 pthread_create(&vt[i-1], NULL, (thread_ptr) &Radix::radix_sort, &r );
digit 2: -10 -100 -1 -1 -142 -12 -183 100 0 10 0 1 225 5 229
digit 1: -100 -1 -1 -10 -12 -142 -183 100 0 0 1 5 10 225 229
digit 0: -183 -142 -100 -12 -10 -1 -1 0 0 1 5 10 100 225 229
-183 -142 -100 -12 -10 -1 -1 0 0 1 5 10 100 225 229
The warning message that compiler give tell us that we have used a cast type from pointer to a function to a pointer to a member of a class. It was mandatory to use a new typedef that will simulate the start_routine signature.
