×

Search anything:

# Parallel Radix Sort handling positive & negative numbers in C++

#### C++ Sorting Algorithms Algorithms

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.

• Introduction
• R1. MSD recursive approach
• R2. LSD recursive approach
• P1. MSD parallel approach
• using OpenMP
• P2. LSD parallel approach

#### 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:

1. determine the max width of a number in the array, i.e. its length as if it is a string
3. 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)
4. go to step 2 by moving the digit with 1 position to the right
5. 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;

{
int w;

public:
{
set_max_width();
}

{
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)

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;

{
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';
}

}

{
}
};

int main()
{
vector<int> v = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,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

1. determine the max width of a number in the array, i.e. its length as if it is a string
3. sort the elements using counting sort based on their radix
(if digit is less the the max width then digit is 0)
4. 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;

{
int w;

public:
{
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;
}

{
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)
}

void set_max_width()
{
ostringstream st;
string s;
int max = 0;

{
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';
}

}

{
}

};

int main()
{
vector<int> v = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0};

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;

{
int w;

public:
{
set_max_width();
}

{
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)
{
printf("process %d out of %d \n", id, total);

}

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;

{
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';
}

}

{
}
};

int main()
{
vector<int> v = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,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>

using namespace std;

{
int w;

public:
{
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;
}

{
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)

}

void set_max_width()
{
ostringstream st;
string s;
int max = 0;

{
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';
}

}

{
}

};

int main()
{
vector<int> v = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0};

for(int i=1; i<=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>

using namespace std;

typedef void * (*function_ptr)(void *);

{
int digit;
int w;

public:
{

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

{
int i;

vector<int> neg, pos;

{
}
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
{
}
else
{
}

cout<<"digit "<<digit<<": ";
cout<<endl;

//if( digit - 1 >= 0)

return NULL;
}

void set_max_width()
{
ostringstream st;
string s;
int max = 0;

{
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';
}

}

{
}
};

int main()
{
vector<int> v = {-142,100,-183,229,-10,225,-100,0,-1,1,10,5,-12,-1,0};

for(int i=1; i<=r.get_max_width();i++)
{
vt.push_back( t );

r.set_digit(r.get_max_width()-i);

}

for(int i=0;i<v.size();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]