Project 2: You are to implement the radix sort that can sort a file contains either all positive integers or a file contains

mixture of positive and negative integers

**************************************

Language: C++

**************************************

Project name: Radix sort for integers

Run your program twice, once with data1 (all positive integers) and another with data2 (mixture of positives and

negatives).

Include in your pdf file:

- One cover page (include the main algorithm steps within the page!)

- One page draw illustration of Radix-sort as taught in class for data1 (can be hand drawing or others. )

-1 pt without the illustration drawings!!

- Program source code

- outFile1 from data1

- deBugFile from data1

- outFile1 from data2

- deBugFile from data2

******************************

I. Input: one input txt file. // -1 for hard code file name.

inFile (use argv[1]): a text file contains a list of integers (may contain negative numbers).

II. Outputs: There will be two output files. // -1 for each hard code file name.

a) outFile1 (argv[2]):

- Print the entire hush table after each iteration (move from one hash table to the other hash table.

- Print the result of the sorted data, 10 numbers per text-line with space in between two numbers.

b) deBugFile (use argv [3]): For all debugging prints.

********************************

III. Data structure:

********************************

- listNode class

- (int) data

- (listNode *) next

Methods:

- constructor (data) //create a listNode node for data and make sure assign nodes next null

- LLQueue class

- (listNode *) head // head hashTable[i][j], where i = 1 or 2, j = 0, or 1, , or 9

- (listNode *) tail // initially, tail head

Methods:

- constructor(...)

- insertQ (table, index, newNode) // insert the newNode after the tail of hashTable[table][index],

// as taught in class, on your own.

- (listNode *) deleteQ () // if Q is not empty, delete and return the node after the dummy,

// as t

aught in class, on your own.

2

- (bool) isEmpty ()// Returns true if tail == head, returns false otherwise.

- printQueue (whichTable, index, File) // File can be outFile1 or deBugFile.

// Print to File the entire linked list in hashTable[whichTable][index].

// For example, if whichTable is 1 and index is 6, then print

Table [1][6]: (-999, 33) ( 33, 36) ( 36, 18)............ (13, NULL) NULL

- A RadixSort class:

- (int) tableSize // set to 10.

- (LLQueue) hashTable[2][tableSize] // 2 1D arrays (size of 10) of linked list queues with dummy nodes.

// Initially, each hashTable[i][j]'s head and tail, as well as hashTable [i, j] are point to the dummy node.

- (int) data

- (int) currentTable // either 0 or 1

- (int) previousTable // either 0 or 1

- (int) maxDigits // the number of digits is the largest integer that controls the number of iterations of Radix sort

- (int) offSet // the absolute value of the smallest negative integer in the data;

// the offSet will add to each data before radix sort and subtract afterward.

- (int) digitPosition // The digit position of the number while sorting. Sorting integers is from right to left.

- (int) currentDigit // the digit which is currently used for sorting.

Methods:

- constructor () // Creates hashTable[2][tableSize]. On your own!

// Use loops to create LLQueue for each hashTable[i][j], i = 0 to 1 and j = 0 to 9, where

// each hashTable[i][j] points to a dummy node and initially, head and tail are also point to dummy node.

- preProcessing () // Read from input file; determine the largest and smallest integers in the file

// and establishes offset. See algorithm below. You may include this method in constructor!

- RSort () // Performs Radix sort; sorts from right-to-left. See algorithm below.

// The algorithm is exactly the same as taught in class.

- (int) getLength (data) // Determines and returns the length of a given data. On your own!

//** suggestion: convert data to string, then returns string length.

- (int) getDigit (data, position) //Determines and returns the digit at the position of data. On your own!

//return 0 if the number of digits in data is smaller than maxDigits. i.e., data will go to index 0.

//** suggestion: cast integer data to string to get the digit, then cast digit back to int, as hashIndex.

//** Reminder: string indexing is from left to right, however, the Radix sort for integer position is from

// right to left, after converting integer to string, the position of digit you want in the data will be opposite

//of string indexing. For example,

// if position is 0, the digit you want will be at the converted string at index (length -1).

// if position is 1, the string at index length -2,

// at position = 2 the string at index length -3, etc.

- printTable (whichTable, File) // On your own!

// Call printQueue () for each none empty queue in hashTable[whichTable].

- printSortedData (whichTable, outFile1) On your own!

// Print nodes data in none empty queue in hashTable[whichTable][index], index = 0 to tableSize

// 10 numbers per text-line with space in between two numbers.

//*** make sure to subtract offSet before printing the data.

******************************

IV. main()

******************************

Step 0: inFile open via argv[1]

outFile1 open via argv[2]

deBugFile open via argv[3]

hashTable[2][tableSize] create by RadixSort constructor

Step 1: preProcessing (inFile, deBugFile) // can be formed by constructor.

Step 2: close inFile

reopen inFile.

Step 3: RSort (inFile, outFile1, deBugFile)

Step 4: close all files

3

******************************

V. preProcessing (inFile, deBugFile)

******************************

Step 0: deBugFile "*** Performing firstReading"

negativeNum 0

positiveNum 0

Step 1: data read from inFile

If data < negativeNum

negativeNum data

If data > positiveNum

positiveNum data

Step 2: repeat step 1 until inFile is empty

Step 3: negativeNum < 0

offSet abs (negativeNum)

else

offSet 0

Step 4: positiveNum positiveNum + offset

maxDigits getLength (positiveNum)

Step 5: deBugFile print negativeNum, offSet, positiveNum, maxDigits (with captions)

******************************

VII. RSort (inFile, outFile1, deBugFile)

******************************

Step 0: deBugFile "*** Performing RSort"

Step 1: digitPosition 0 // the first digit/position from the right of the data.

currentTable 0 // the first hashTable

Step 2: data read a data from inFile

data += offSet // for simplicity, we add offset even if it is zero.

newNode create a new listNode with data

hashIndex getDigit (data, digitPosition)

// get the digitPosition of the data in the node, make sure it returns a single digit

insertQ (hashTable[currentTable][hashIndex], newNode)

// add newNode at the tail of the queue at hashTable[currentTable][hashIndex]

Step 3: repeat step 2 until inFile is empty

Step 4: digitPosition ++

previousTable currentTable

currentTable mod (currentTable + 1, 2)

Step 5: deBugFile print digitPosition, currentTable, previousTable with caption

outFile1 *** Printing hashTable[previousTable] fill-in whatever the previousTable is 0 or 1.

Step 6: printTable (hashTable[previousTable])

Step 7: tableIndex 0

Step 8: // step 8 and step 9 move nodes from hashTable[previousTable][ tableIndex] queue to the current table

newNode deleteQ (hashTable[previousTable][ tableIndex])

hashIndex getDigit (newNode's data, digitPosition)

insertQ (hashTable[currentTable][hashIndex], newNode)

Step 9: repeat steps 8 until hashTable[previousTable][ tableIndex] is empty.

Step 10: tableIndex ++ // continue to process the next queue in the previous hashTable

Step 11: repeat step 8 to step 10 until tableIndex >= tableSize - 1

// finish moving all nodes from previous table to current table.

Step 12: repeat step 4 to step 11 while digitPosition < maxDigits

// continue processing until the data are sorted.

Step 13: printSortedData (previousTable, outFile1)

Data1:

191 328 402 18

999

152 653

714

37

538 296 730 777

67

64 852

123

48 91

22

49 4

95

816 702 8 95 61 9229

6

40

9715

388

Data 2:

2 134 410

908 14 482

213 23 821 6

824 8

226

127 -532 25 94 9

740

361

676 43 755

324 539 9 -95

16 39 695 7

91 56 702 -8 5

910

676 278 685

7 333 414 597 806

613 999