C++

Forum

 
Alphabetical Sorting Algorithm Help

cGuru (42)
My program is freezing when I run this code which makes me guess that it is going into an infinite loop:

Note: I already sorted them according to length, that is why you see line 36.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
vector<string> PlayerNames;
map<char,int> Alphabet;

Alphabet['A'] = 1;
Alphabet['B'] = 2;
Alphabet['C'] = 3;
Alphabet['D'] = 4;
Alphabet['E'] = 5;
Alphabet['F'] = 6;
Alphabet['G'] = 7;
Alphabet['H'] = 8;
Alphabet['I'] = 9;
Alphabet['J'] = 10;
Alphabet['K'] = 11;
Alphabet['L'] = 12;
Alphabet['M'] = 13;
Alphabet['N'] = 14;
Alphabet['O'] = 15;
Alphabet['P'] = 16;
Alphabet['Q'] = 17;
Alphabet['R'] = 18;
Alphabet['S'] = 19;
Alphabet['T'] = 20;
Alphabet['U'] = 21;
Alphabet['V'] = 22;
Alphabet['W'] = 23;
Alphabet['X'] = 24;
Alphabet['Y'] = 25;
Alphabet['Z'] = 26;

do // Bubble Sort
{
	swap = false;
	for (int count = 0; count < (PlayerNames.size() - 1); count++)
	{
		if (PlayerNames[count].length() == PlayerNames[count + 1].length())
		{
			for (int letter = 0; letter < PlayerNames[count].length(); letter++)
			{
				if (Alphabet[PlayerNames[count][letter]] > Alphabet[PlayerNames[count + 1][letter]])
				{
                                        // Swap everything

					swap = true;
					break;
				}
			}
		}
	}
} while (swap);


Any help will be greatly appreciated!
Last edited on
mutexe (2372)
put some print statements in your for loops, e.g.
 
 
std::cout << "In outer loop!" << std::endl;

at least that will tell you which loop you're getting stuck in.

edit:
wait a second. do you actually populate your PlayerNames vector?

I also suspect you're not getting to line 44.
Last edited on
cGuru (42)
Yes its all populated
MiiNiPaa (8886)
Do your strings really contain all capital letters?

And do you required to:
1) Use loops and manual comparison instead of builtin lexographical comparison? Lines 38-40 can be replaced with if(PlayerNames[count] > PlayerNames[count+1])
2) Write your own sorting function. Whole code can be replaced with calling std::sort with predicate.
Last edited on
cGuru (42)
@mutexe

I put a cout under each "for" and "if" declaration but it is outputting them all.

And it is getting to line 44. That swapping code is pasted from somewhere else that does work.
cGuru (42)
@MiiNiiPaa

Yes, it contains all Capital letters. I am will write the correct algorithm for numbering when I solve this.

1. I don't understand this.
2. I have several vectors that need to be sorted together that is why I am writing my own instead of using sort. (PlayerNames, PlayerScores, PlayerRanks, etc.)

I am trying to learn the following:
http://stackoverflow.com/questions/17074324/how-can-i-sort-two-vectors-in-the-same-way-with-criteria-that-uses-only-one-of

But, I haven't even learned templates in class yet.
MiiNiPaa (8886)
1. As I said: you can replace a loop an checking condition with simple condition:
1
2
3
4
 
if(PlayerNames[count] > PlayerNames[count+1]) {
    //sort stuff
    swap = true;
}


2. Usually parallel data structures are sign of a bad design. Why not combine all these into one structure containing all data together and have one vector of structures.

Either way, you better move all comparison stuff into a single function returning a bool.

Your code should look like:

1
2
3
4
5
6
7
8
9
10
11
 
do
{
    swap = false;
    for (int count = 0; count < (PlayerNames.size() - 1); ++count++) {
        if (not compare(PlayerNames[count], PlayerNames[count + 1]) {
            // Swap everything
            swap = true;
        }
        //Nothing here
    }
} while (swap);
cGuru (42)
I got it. Put:

1
2
 
else
{ break; }


after line 46.
MiiNiPaa (8886)
That would be useless, as no letters aside from first would be checked in this case
cGuru (42)
@MiiNiPaa

Yes, if the first one is in the correct alphabetical order, then there would be no point to checking the remaining letters.

Besides there being no point, it would introduce the infinite loop because it would never stop rearranging the names.
MiiNiPaa (8886)
In that case lines AC and AB would be threated as if they were in correct order.

As long as you do not mess with letter variable, your loop would reach the end eventually. It would not swap stuff repeadetly because there is a break after swap exactly for that.
Topic archived. No new replies allowed.