0

Hello, I have some problems with this code

//Selection and Bubble are working

#include <iostream>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include "Sorts.h"
using namespace std;

typedef void (*SortFunction)(int a[], int n);

int main(int argc, char *argv[])
{
  if(argc < 4) {
    cerr << "Usage: " << argv[0]
         << " <algorithm> <n> <sequence [seed]>" << endl
         << "algorithm\t<B|S|I|Q|3|M|i>^+\n"
         << "\t\t(B)ubble\n"
         << "\t\t(S)election\n"
         << "\t\t(I)nsertion\n"
         << "\t\t(Q)uick (first element pivot)\n"
         << "\t\t(3)Quick (median of 3)\n"
         << "\t\t(M)erge\n"
         << "\t\t(i)terative merge\n"
         << "n\t\tsize\n"
         << "sequence\t<R|A|D>\n"
         << "\t\t(R)andom\n\t\t(A)scending\n\t\t(D)escending\n"
         << "seed\t\toptional parameter for R sequence"
         << " time(NULL) if not specified\n";
    return -1;
  }

  int n = atoi(argv[2]);
  int seed = time(NULL);
  int *orig = new int[n];
  int *correct = new int[n];
  char sequence = argv[3][0];

  switch(sequence)
  {
    case 'R':
      if(argc == 5)
        seed = atoi(argv[4]);
      srand(seed);
      for(int i = 0; i < n; i++)
        correct[i] = orig[i] = rand();
      break;
    case 'A':
      for(int i = 0; i < n; i++)
        correct[i] = orig[i] = i;
      break;
    case 'D':
      for(int i = 0; i < n; i++)
        correct[i] = orig[i] = n-i;
      break;
  }//end switch

  //when you correctly write a more efficient sorting routine
  //you should use that instead of selectionSort!
  bubbleSort<int>(correct,n);

  int m = 0; //number of algorithms
  while(argv[1][m] != '\0')
  {
    char algorithm = argv[1][m];
    string algstr;
    SortFunction f;
    switch(algorithm)
    {
      case 'B': f = &bubbleSort; algstr = "BubbleSort"; break;
      case 'S': f = &selectionSort; algstr = "SelectionSort"; break;
      //case 'Q': f = &quickSort; algstr = "QuickSort"; break;
    case 'R': f = &rSort; algstr = "Radix Sort"; break;

      default : cerr << "Invalid algorithm choice - '"
                     << algorithm << "'\n";
                exit(-1);
    }

    cout << algstr << "...\n";

    int *a = new int[n];
    for(int i = 0; i < n; i++)
      a[i] = orig[i];

    (f)(a,n);

    //check to see if data is sorted  
    for(int i = 1; i < n; i++)
      assert(a[i] >= a[i-1]);

    //check to see if data was corrupted
    for(int i = 0; i < n; i++)
      assert(a[i] == correct[i]);

    cout << "okay\n";

    delete [] a;
    m++;
  }//end while

  return 0;
}

Where I should test the algrothem I tested the bublle and the selection and work fine, but the radix is not working fine

> // Radix.cpp

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector < vector <int> > buckets;
void rSort(int x[],int length){
    int temp;
    int m=0;

    for(int i=0;i<100;i++){

        for(int j=0;j<length;j++){
            temp=(int)((x[j])/pow(double(10),i))%10;
            buckets[temp].push_back((x[j]));
        }

        for(int k=0;k<10;k++){
            for(int l=0;l<buckets[k].size();l++){
                x[m]=buckets[k][l];
                m++;
            }

           buckets[k].clear();
        }
        m=0;
    }
    buckets.clear();

}

Radix.cpp is include in Sort.h

after that i have to run it in the code below where the output should display, also i tested the Bubble and Selection and work fine but the Radix does not work

> #include <iostream>
#include <iomanip>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <sys/time.h>
#include <cmath>
#include "Sorts.h"
using namespace std;

unsigned long getTime() {
    timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec * 1000000ul + tv.tv_usec;
}

typedef void (*SortFunction)(int a[], int n);

int main(int argc, char *argv[]) {
  if(argc < 6) {
    cerr << "Usage: " << argv[0]
         << " <algorithm> <mink> <maxk> <iterations> <sequence [seed]>" << endl
         << "algorithm\t<B|S|R>\n"
         //<< "algorithm\t<B|S|I|Q|M>\n"
         << "\t\t(B)ubble\n"
         << "\t\t(S)election\n"
        << "\t\t(R)adix\n"
         //<< "\t\t(I)nsertion\n"
         //<< "\t\t(Q)uick (first element pivot)\n"
         //<< "\t\t(3)Quick (median of 3)\n"
         //<< "\t\t(M)erge\n"
         //<< "\t\t(i)terative merge\n"
         << "mink\t\tminimum exponent for size, 2^(2*i)\n"
         << "maxk\t\tmaximum exponent for size, 2^(2*i)\n"
         << "iterations\tnatural number for iterations\n"
         << "sequence\t<R|A|D>\n"
         << "\t\t(R)andom\n\t\t(A)scending\n\t\t(D)escending\n"
         << "seed\t\toptional parameter for R sequence"
         << " time(NULL) if not specified\n";
    return -1;
  }

  int seed = time(NULL);

  int m = 0; //number of algorithms
  while(argv[1][m] != '\0')
  {
    char algorithm = argv[1][m];
    string algstr;
    SortFunction f;
    switch(algorithm)
    {
      case 'B': f = &bubbleSort; algstr = "BubbleSort"; break;
      case 'S': f = &selectionSort; algstr = "SelectionSort"; break;
      //case 'I': f = &insertionSort; algstr = "InsertionSort"; break;
      //case 'M': f = &mergeSort; algstr = "MergeSort"; break;
      //case 'i': f = &imergeSort; algstr = "iMergeSort"; break;
      //case 'Q': f = &quickSort; algstr = "QuickSort"; break;
      //case '3': f = &quickSort3; algstr = "QuickSort3"; break;
      default : cerr << "Invalid algorithm choice - '"
                     << algorithm << "'\n";
                exit(-1);
    }

    const int mink = atoi(argv[2]);
    const int maxk = atoi(argv[3]);
    const int iterations = atoi(argv[4]);;
    const char sequence = argv[5][0];
    if(argc == 7)
      seed = atoi(argv[6]);
    srand(seed);
    cout << algstr << endl;
    for(int i = mink; i <= maxk; i++)
    {
      unsigned long totaltime = 0;
      //modified for report
      int n = (int)pow((double)2,(2*(double)i));
      int *a = new int[n];
      if(a == NULL)
      {
        cerr << "Can't allocate an array of size " << n << endl;
        exit(-1);
      }
      for(int j = 0; j < iterations; j++)
      {
        switch(sequence)
        {
          case 'R':
            for(int x = 0; x < n; x++)
              a[x] = rand();
            break;
          case 'A':
            for(int x = 0; x < n; x++)
              a[x] = x;
            break;
          case 'D':
            for(int x = 0; x < n; x++)
              a[x] = n-x;
            break;
        }//end switch

        unsigned long start = getTime();
        (f)(a,n);
        totaltime += getTime() - start;
      }//end j for loop

      delete [] a;

      double avgtime = totaltime/(double)iterations;

      cout << "t_" << left << setw(11) << n
           << " = " << right << setw(15)
           << avgtime << " microseconds"
           << right << setw(15) 
           << (avgtime/1000000.0) << " seconds\n"
           << left;
    }//end i for loop

    m++;
  }//end while

  return 0;
}//end main
2
Contributors
1
Reply
5
Views
4 Years
Discussion Span
Last Post by deceptikon
0

What do you mean by "does not work"? If you mean that it doesn't sort the array properly, then your radix sort is broken and you need to check the algorithm. Perhaps compare what you're doing logically with a working radix sort.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.