sorting a string using counting sort

Question

I looked at the counting sort algorithm to sort a string here: https://www.geeksforgeeks.org/counting-sort/. I have a few questions:

#define RANGE 255

What is the function of RANGE? Why do we have to specifically define the RANGE to 255?

int count[RANGE + 1], i;

Why do we have to declare the size of count[] as RANGE+1? Why couldn't it be just 256?

// Store count of each character  
for(i = 0; arr[i]; ++i)  
    ++count[arr[i]];

The array stores the count of the specified digit, but here we have characters in a string, so how does the above code convert the characters to numeric equivalents to be stored in the array?

i am afraid most of your questions can be answerd by: That site unfortunately promotes bad practices. There is no good reason to `#define` a constant. `memset` is kinda ok-ish but not nice. Using `arr[i]` as stop condition is not wrong but also not nice. Not using `std::array`/`std::vector` in favor of c-arrays is not nice. Don't try to learn C++ from online tutorials but rather grab a good [book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) — 463035818_is_not_an_ai, Apr 02 '20 at 21:50
U could use c++ containers to map strings with integer values and act on integer value keys for counting sort algorithms like redix sorting — user786, Jun 24 '21 at 10:07

progiv · Answer 1 · 2020-07-08T14:30:08.847

0

RANGE defines possible keys for counters. Which are 0..RANGE. It might be arbitrary, but 255 is for having exactly 256 possible values. The same as the number of distinct characters.
So we have possible keys 0..255. That is exactly 256. You can hardcode it like this. But since RANGE is arbitrary, you may want to change it to 512 for example. In that case, you will need to change the size too.
From a logic point string consists of characters, but it is only our minds representation. For C++ string is an array of char type. Which is an integer type. Since the international part of ASCII table uses only values 0..127. We can safely use these values as array indexes.

edited Jul 08 '20 at 14:30

answered Apr 02 '20 at 21:53

progiv

44
6

"Which is an integer type with values -128..127" that is wrong. `char` can be either signed or unsigned – 463035818_is_not_an_ai Apr 03 '20 at 07:44
Here we are considering `char` which is signed, not `unsigned char` which is not signed – progiv Apr 07 '20 at 10:46
no that is wrong. `char` is either signed or unsigned, and either way it is a type distinct from `signed char` and `unsigned char`. You can read about it here: https://en.cppreference.com/w/cpp/language/types – 463035818_is_not_an_ai Apr 07 '20 at 10:48
1

Thank you @idclev463035818 for pointing it out. Removed wrong part of the answer – progiv Jul 08 '20 at 14:30

score 0 · Answer 2 · answered Apr 02 '20 at 22:23

I would not use that code as a learning example. There are so many errors in it that I wasn't even able to properly compile it.

What is the function of RANGE?

When you compile your code a special program called a preprocessor runs beforehand. The preprocessor essentially replaces a lot of things. It usually does this based on statements called preprocessor directives and they begin with the "#" symbol. In this case, #define RANGE 255 is telling the preprocessor to replace every occurence of "RANGE" in the code with "255". For example, the line int count[RANGE + 1], i becomes int count[255 + 1], i.

Why do we have to specifically define the RANGE to be 255?

To be completely honest I'm not sure why the code decided to use 255 for RANGE. I've tested the code and it works just fine with RANGE equal to 114 and it doesn't work with numbers. If you increase the length of the input string "geeksforgeeks" to something much larger then RANGE won't be sufficiently large enough.

How does the code convert the characters to numeric equivalents to be stored in the count array?

The char data type is actually an integer. Every character we use (A to Z, 0 to 9, punctuation, etc) all has a corresponding number. For example the code below will print out the number which corresponds to a which is "97".

#include <iostream>

int main()
{
    char name[] = "abc";

    int a = name[0];

    std::cout << a;

    return 0;
}

The line ++count[arr[i]]; simply accesses element i in the array arr and appends it to the count integer array which it can do because char is an integer. Once we have it in the count integer array it is treated like a normal integer and when we print it out in the console it shows us a number rather than a character.

sorting a string using counting sort

2 Answers2