shiladitya basu shiladitya basu - 2 months ago 12
C++ Question

Arranging a string in uppercase-first alphabetical order C++

I was trying to create a program in C++ that sorts a given string in alphabetical order in a way where the uppercase letters precede their lowercase equivalent.
Example:
DCBAdcba
Sorted string:
AaBbCcDd

Given below is the code.

#include <iostream>
#include <string>
#include <cctype>
struct char_ {
char c;
char diff;
char_();
char_(char x);
};
char_::char_() {
c = 0;
diff = 0;
}
char_::char_(char x) {
c = std::tolower(x);
diff = c - x;
}

void charswap(char_& x, char_& y) {
char_ temp;
temp = x;
x = y;
y = temp;
}

int main() {
std::string str;
getline(std::cin, str);
char_* str2 = new char_[str.length()];
for (int i = 0; i < str.length(); i++) {
str2[i] = char_(str[i]);
}

/*
for (int i = 0; i < str.length(); i++) {
std::cout << str2[i].c << std::endl;
}
*/
for (int i = 0; i < str.length(); i++) {
for (int j = i; j < str.length(); j++) {
if (str2[i].c > str2[j].c)
charswap(str2[i], str2[j]);
}
}


for (int k = 0; k < str.length(); k++) {
std::cout << str2[k].c << "\t" << (int)str2[k].diff << std::endl;
}

for (int i = 0; i < str.length(); i++) {

str2[i].c = str2[i].c - str2[i].diff;
}




for (int i = 0; i < str.length(); i++) std::cout << str2[i].c;
std::cout << "\n";
return 0;
}


A char_ struct is created to store the individual characters(converted to to lowercase) and their difference from the uppercase equivalent(0 or 32, depending if the original char was lowercase or uppercase, respectively). It then sorts the char_ characters on the basis of their lowercase values. And after the sort we add back the difference to the character to retrieve the uppercase form.

But when I try giving this string, it gives the following result.

DCBAdcba

AabBCcdD

I cannot understand what's happening here.

Answer

The problem is on this line:

if (str2[i].c > str2[j].c)
    charswap(str2[i], str2[j]);

It compares characters in case-insensitive way, with no provision for tie breaking when lowercase characters are the same.

You need to modify this to swap characters when lowercase on the right is greater than lowercase on the left, or when lowercase representations are the same, but the right side original character is in upper case:

if ((str2[i].c > str2[j].c) || (str2[i].c == str2[j].c && str2[j].diff))
    charswap(str2[i], str2[j]);