Radix Sort Negative Numbers

[celoz0828]

So I have to write a program that performs radix sort. I have radix sort working. but only with positive numbers. I need to write a function called in the code "uintVal" that will return an unsigned representation of the negative number.

here is my code

header

#ifndef _SORTING_HH_
#define _SORTING_HH_

#include <iostream>
#include <cstring>
using namespace std;

template <class Elem,class Comp>
class Sortings
{
public:
  // static void merge(Elem *arr, unsigned int n);
  static void quick(Elem *arr, unsigned int n);// do merge or this one
  static void select(Elem *arr, unsigned int n);
  static void shell(Elem *arr, unsigned int n);
  static void radix(Elem *arr, unsigned int n); // when using radix, Comp should be a class
  // with a static method "uintVal(...)" that gives an unsigned int representation of the item
private:
  // These are all optional, add or remove as functions as you need
  static const unsigned int THRESHOLD = 3; // used by shell
  static const unsigned int RADIX = 16; // used by radix
  static void insert2(Elem *arr, unsigned int incr, unsigned int n);
  static void swap(Elem *arr, unsigned int, unsigned int);
  static void quickRecurse(Elem *arr, unsigned int l, unsigned int r);
};

class intuival
{
public:
  static unsigned int uintVal(int n);
};

class intintCompare
{
public:
  static bool lt(int, int);
  static bool gt(int, int);
  static bool eq(int, int);
};

class strstrCompare
{
public:
  static bool lt(char*, char*);
  static bool gt(char*, char*);
  static bool eq(char*, char*);  
};

#endif 

main

#include "sorting.hh"
#include <cstdlib>
using namespace std;

int main()
{
  int i = 0;
  const int n = 5;
  int arr[5];
  const unsigned int RADIX = 10;
  unsigned int exp;
  int count[RADIX];
  int B[n];

  for (i=0; i<n; i++)
  {  
	  cout << "Enter: " << endl;
	  cin >> arr[i];
  }
  unsigned int max;
  
  if (arr != NULL && n > 1)
  {
	for (max = intuival::uintVal(arr[0]), i = 1; i < n; i++)
		if (intuival::uintVal(arr[i]) > max)
		max = intuival::uintVal(arr[i]);

	for (exp = 1; max/exp > 0; exp *= RADIX)
	{		
		for(i = 0; i < RADIX; i++)
			count[i] = 0;
		for(i = 0; i < n; i++) 
			count[(intuival::uintVal(arr[i])/exp)%RADIX]++;
		for(i = 1; i < RADIX; i++)
			count[i]=count[i]+count[i-1];
		for(i = n - 1; i >= 0; i--)
			B[--count[((intuival::uintVal(arr[i]))/exp) % RADIX]]=arr[i];
		for(i = 0; i < n; i++)
			arr[i] = B[i];
	}
	for (i = 0; i < n; i++)
		cout <<arr[i] << " ";
  }
	  system("pause");
	  return 0;
}

right now I'm just doing it in main to get it to work. I am prepared to then move it into its own file and have main just call it. I also just use five elements in the array for the sake of testing it.

What or how do I go about creating the uintVal? I don't really know where to start on that.

[mik2718]

A signed 32 bit integer goes from −2,147,483,648 to 2,147,483,647
and an unsigned from 0 to 4,294,967,295

so you could just add 2,147,483,648 to the signed number to convert it to an unsigned one for sorting

then subtract to get back to signed numbers when you have finished sorting