11.2.3 The Radix Sort The radix sort is included here because it is quite differ

Question

11.2.3 The Radix Sort The radix sort is included here because it is quite different from the other sorts we've described, as it does not compare the array's entries Imagine again that you are sorting a hand of cards. This time you pick up the cards one at a time and arrange them by rank into 1 3 possible groups in this order: 2, 3, . . . , 10, J, Q, KA Combine these groups and place the cards face down on the table so that the 2s are on top and the aces are on the bottom. Now pick up the cards one at a time and arrange them by suit into four possible groups in this order: clubs, diamonds, hearts, and spades. When taken together, the groups result in a sorted hand of cards A radix sort uses this idea of forming groups and then combining them to sort a collection of data. The sort treats each data item as a character string. As a first simple example of a radix sort, con- sider this collection of three-letter strings: ABC, XYZ, BWZ, AAC, RLT, JBX, RDT, KLT, AEO, TLJ The sort begins by organizing the data according to the rightmost (least significant) letters. Although none of the strings ends in A or B, two strings end in C. Place those two strings into a group. Continu- ing through the alphabet, you form the following groups (ABC, AAC) (TLJ) (AEO) (RLT, RDT, KLT) (JBX) (XYZ, BWZ) Group strings by their rightmost letter The strings in each group end with the same letter, and the groups are ordered by that letter. In addi- tion, the strings within each group retain their relative order from the original list of strings Now combine the groups into one as follows. Take the items in the first group in their present order, follow them with the items in the second group in their present order, and so on. The following group results ABC, AAC, TLJ, AEO, RLT, RDT, KLT, JBX, XYZ, BWZ Combine the groups Next, form new groups as you did before, but this time use the middle letter of each string instead of the last letter:

Explanation / Answer

#include <iostream>

using namespace std;

// Function to return the maximum value from array.

int getMaximum(int ItemArray[], int length)

{

// Initially stores the zero index position value of ItemArray as maximum value

int maximum = ItemArray[0];

// Loops from one to length of the ItemArray

for (int counter = 1; counter < length; counter++)

// Checks if the current index position data is greater than the earlier maximum data

if (ItemArray[counter] > maximum)

// Update the maximum value by assigning the current index position data of ItemArray

maximum = ItemArray[counter];

// Returns the maximum value

return maximum;

}// End of function

// A function to do counting sort of ItemArray[] according to

// the digit represented by exp.

void countSort(int ItemArray[], int length, int exp)

{

// To store the output

int outputArray[length];

// countArray[i] array will be counting the number of array values

// having that 'counter' digit at their (exp)th place.

// Initializes all 10 index position values to 0

int countArray[10] = {0};

// Loop variable

int counter;

// Count the number of times each digit occurred at (exp)th place in every input.

// and store count of occurrences in countArray[]

for (counter = 0; counter < length; counter++)

countArray[(ItemArray[counter] / exp) % 10]++;

// Calculating their cumulative count.

// Change countArray[counter] so that countArray[counter] now contains actual

// position of this digit in outputArray[]

// Loops from 1 to 10

for (counter = 1; counter < 10; counter++)

countArray[counter] += countArray[counter - 1];

// Inserting values according to the digit '(ItemArray[counter] / exp) % 10'

// fetched into countArray[(ItemArray[counter] / exp) % 10].

// Loop from last index position to zero index position

for (counter = length - 1; counter >= 0; counter--)

{

outputArray[countArray[(ItemArray[counter] / exp) % 10] - 1] = ItemArray[counter];

countArray[(ItemArray[counter] / exp) % 10]--;

}// End of for loop

// Copy the output array to ItemArray[], so that ItemArray[] now

// contains sorted numbers according to current digit

// Loops till length of the array

for (counter = 0; counter < length; counter++)

ItemArray[counter] = outputArray[counter];

}// End of function

// Function to sort ItemArray[] of size length using Radix Sort

void radixSorting(int ItemArray[], int length)

{

int exp;

// Calls the function to find the maximum number to know number of digits

int maximum = getMaximum(ItemArray, length);

// Do counting sort for every digit.

// Instead of passing digit number, exp is passed.

// exp is 10 ^ d, where d is current digit number

for (exp = 1; maximum / exp > 0; exp *= 10)

countSort(ItemArray, length, exp);

}// End of function

// Function to display the array contents

void displayResult(int ItemArray[], int length)

{

// Loops till length of the ItemArray

for (int counter = 0; counter < length; counter++)

// Displays each index position data of ItemArray with comma

cout << ItemArray[counter] << ", ";

}// End of function

// main function definition

int main()

{

// To store the length of the array

int length;

// Accepts the length of the array

cout<<" Enter the number of data element to be sorted using Radix Sort: ";

cin>>length;

// Declares an array with length size

int ItemArray[length];

// Loops till length of the array

for(int counter = 0; counter < length; counter++)

{

// Displays message with counter value

cout<<"Enter element "<<counter + 1<<": ";

// Accepts data

cin>>ItemArray[counter];

}// End of for loop

cout<<" ******************* Before Radix Sort ******************* ";

// Calls the function to display the array contents

displayResult(ItemArray, length);

// Calls the function to perform radix sort

radixSorting(ItemArray, length);

cout<<" ******************* After Radix Sort ******************* ";

// Calls the function to display the array contents

displayResult(ItemArray, length);

return 0;

}// End of main function

Sample Output:

Enter the number of data element to be sorted using Radix Sort: 10
Enter element 1: 459
Enter element 2: 22
Enter element 3: 45
Enter element 4: 66
Enter element 5: 789
Enter element 6: 922
Enter element 7: 112
Enter element 8: 4
Enter element 9: 367
Enter element 10: 58

******************* Before Radix Sort *******************
459, 22, 45, 66, 789, 922, 112, 4, 367, 58,
******************* After Radix Sort *******************
4, 22, 45, 58, 66, 112, 367, 459, 789, 922,

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.