Radix Sort Using Queues

[AtticusOmundson]

My program involves populating an array of size 37 with empty queues, then sorting elements into the array based on their respective ASCII code (any special character ASCII goes into 1, numbers into 2-11, and letters into 12-37). It is to sort backwards through the strings using loops and foward using recursion. My issue is that I'm not sure how to code it so that the recursive function radixSortAsc operates correctly.

RadixSort.h:

#if !defined (RADIXSORT_H)
#define RADIXSORT_H

#include "QueueLinked.h"
using CSC2110::QueueLinked;

template < class T >
class RadixSort
{
   private:
	  static char getRadixChar(T* item, int index); //1-based
      static void binSort(QueueLinked<T>* bin, int curr_char, int num_chars, char (*getRadixChar) (T* item, int index));
      static void radixSortAsc(T** sort, int n, int num_chars, char (*getRadixChar) (T* item, int index));  //algorithm 1
      static void radixSortDesc(T** sort, int n, int num_chars, char (*getRadixChar) (T* item, int index));  //algorithm 2
 
   public:
      static T** radixSort(T** sort, int num_to_sort, int num_chars, bool asc, char (*getRadixChar) (T* item, int index));
};

template < class T >
T** RadixSort<T>::radixSort(T** unsorted, int num_to_sort, int num_chars, bool asc, char (*getRadixChar) (T* item, int index))
{
   //DO THIS
   //return unsorted;
   //Test stub
   
   //if(asc)
	 //  radixSortAsc(sort, n, num_chars, (*getRadixChar) (st, index));
   //else
	 //  radixSortDesc(sort, n, num_chars, (*getRadixChar) (st, index));
}

template < class T >
char RadixSort<T>::getRadixChar(T* item, int index)
{
	//return 0;
	//Test stub
}

template < class T >
void RadixSort<T>::radixSortAsc(T** sort, int n, int num_chars, char (*getRadixChar) (T* st, int index))
{
   //DO THIS
   //return;
   //Test stub
}

template < class T >
void RadixSort<T>::binSort(QueueLinked<T>* bin, int curr_char, int num_chars, char (*getRadixChar) (T* st, int index))
{
   //DO THIS
   //return;
   //Test stub
}

template < class T >
void RadixSort<T>::radixSortDesc(T** sort, int n, int num_chars, char (*getRadixChar) (T* st, int index))
{
   int num_queues = 37;  //covers letters and digits
   QueueLinked<T>** bins = new QueueLinked<T>*[num_queues];  

   //must instantiate each of the queues
   for (int i = 0; i < num_queues; i++)
   {
      //DO THIS
   }

   for (int i = num_chars; i > 0; i--)  //number of times to bin stuff
   {
      //DO THIS
   }

   for (int i = 0; i < num_queues; i++) 
   {
      delete bins[i];
   }

   delete[] bins;
}

#endif 

RadixSort.cpp:

#include "RadixSort.h"
#include "CD.h"
using CSC2110::CD;
#include "ListArray.h"
using CSC2110::ListArray;
#include "ListArrayIterator.h"
using CSC2110::ListArrayIterator;
#include "Text.h"
using CSC2110::String;

#include <iostream>
using namespace std;

void deleteCDs(ListArray<CD>* list)
{
   ListArrayIterator<CD>* iter = list->iterator();

   while(iter->hasNext())
   {
      CD* cd = iter->next();
      delete cd;
   }
   delete iter;
}

int main()
{
   ListArray<CD>* list = CD::readCDs("cds.txt");
   int size = list->size();

   CD** cds = new CD*[size];

   ListArrayIterator<CD>* iter = list->iterator();
   int count = 0;
   while(iter->hasNext())
   {
      CD* cd = iter->next();
      cds[count] = cd;
      count++;
   }
   delete iter;

   //DO THIS
   //test both radix sort methods using the cds array
   
	/*while(iter->hasNext())
	  {
		 CD* cd = iter->next();
		 cd->displayCD();
	  }*/
   //Test stub
   
   /*iter = list->iterator();
   CD* cd = iter->next();
   cd = iter->next();
   cd->displayCD();
   cout<< "radixChar1: " << CD::getRadixChar(cd, 1);
   delete iter;
   delete[] cds;*/
   //Test 2
   
   

   deleteCDs(list);
   delete list;

   return 0;
}

Any help would be appreciated.

[skiian12]

With radixSortAsc, you sort with the first character of every item first.

first off, you need to create one queue, that stores the items in the sort array, to send to binSort(). you can do that using a loop that runs the size of the array with items.

QueueLinked<T>* bin = new QueueLinked<T>();  //create one queue object 

for(int i = 0; i < size of sort; i++)
{
      bin->enqueue(sort[i]);  //puts each item into queue
}

Next Send that queue to binSort

binSort(bin, 1, num_chars, getRadixChar);  //sends queue, highest number of characters, functions pointer

after you send it to binSort(), binSort() sorts the bin you gave it and now you have to copy it back over with a loop

for(int i = 0; i < number of items; i++)
{
   sort[i] = bin->dequeue();  //put items in bin back in sort array
}

In binSort(), you have to create 37 bins

QueueLinked<T>** bins = new QueueLinked<T>*[37];

Now put a queue in them, with a loop

for(int i = 0; i < 37; i++)
{
   bins[i] = new QueueLinked<T>();
}

Now dequeue the bin from radixSortAsc(), and put the items in the bins using the items and curr_char or first letter.

I'll pick back up tomorrow