C++

Forum

 
Bubble sort won't sort anything...

Pages: 12
WilliumBobCole (30)
Me again ;P

I have my code working perfectly now, my whole game works, it prevents duplicates, it stops when you run out of virtual money, it let's you re use the same ticket each time, it is pretty much flawless. The last thing I need, and is important for my grade, is to bubble sort the numbers that the player inputs on their lottery ticket, so each of the up to 10 lines is printed in ascending order, regardless of how they are entered. The code appears to me as if it should work, but in practice, although it compiles, the code does nothing, it doesn't even swap one number in the array with another...

This is probably another one of those silly, simply things, staring me in the face, but if anyone can help me out I would be extremely grateful!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
    //---BUBBLE SORT CODE-------------------------------------
    for(int Line = 0; Line < Lines; Line++)
    {
        bool swap = true;


        for(int n = 0; n < 6 && swap == true; n++)
        {
            swap = false;//resets flag
            for (int sort = 0; sort < (n - 1); sort++)
            {
                if(Guess[Line][n+1] < Guess[Line][n])     //if the next in the array is less than this one
                {
                     int temp;
                     temp = Guess[Line][n+1];             //swap elements using temp data storage
                     Guess[Line][n+1] = Guess[Line][n];
                     Guess[Line][n] = temp;
                     swap = true;               //indicates that a swap occurred.
                }
            }
        }
    }



Thank you!
Volatile Pulse (1543)
I'm not sure you're implementing the bubble sort correctly. Here is a quick example using a 1D array:
1
2
3
4
5
6
7
8
9
10
11
12
 
// Loops until we haven't swapped anymore elements
for (bool swap = true; swap;) {
   swap = false; // resets the bool
   // Loops through all the elements
   for (int i = 0; i < ARRAY_SIZE - 1; i ++)
      if (myArray[i] > myArray[i + 1]) {
         int temp = myArray[i];
         myArray[i] = myArray[i + 1];
         myArray[i + 1] = temp;
         swap = true; // Indicates we swapped at least one element this pass
      }
}


Now, looking at your code, the loop with n, I'm assuming is the maximum number of passes you're allowing? I don't understand the logic behind that. Actually, I'm not sure I understand the logic behind the for loop after that either. What's the purpose of the sort for loop? You don't use sort, but yet it looks like you should. Maybe n is supposed to be replaced with sort in your if statement?

Edit: I believe that's exactly your issue. This:
1
2
3
4
5
6
7
8
 
                if(Guess[Line][n+1] < Guess[Line][n])     //if the next in the array is less than this one
                {
                     int temp;
                     temp = Guess[Line][n+1];             //swap elements using temp data storage
                     Guess[Line][n+1] = Guess[Line][n];
                     Guess[Line][n] = temp;
                     swap = true;               //indicates that a swap occurred.
                }


Should become this:
1
2
3
4
5
6
7
8
 
                if(Guess[Line][sort+1] < Guess[Line][sort])     //if the next in the array is less than this one
                {
                     int temp;
                     temp = Guess[Line][sort+1];             //swap elements using temp data storage
                     Guess[Line][sort+1] = Guess[Line][sort];
                     Guess[Line][sort] = temp;
                     swap = true;               //indicates that a swap occurred.
                }
Last edited on
WilliumBobCole (30)
my array kind of looks like this

1
2
3
4
5
6
7
8
9
 
/*  n>  1   2   3   4   5   6
Line\/
    1   1   8   15  27  33  49
    2   7   46  12  26  11  4
    3   etc etc
    4
    \/
    10
 */


Line is the line on the player's ticket, up to 10 lines on a ticket but it might just be one or two.
For each line, there are exactly 6 entries, which in other for loops I refer to as n, though I could of course use anything to reference them.

I simply need to, for each one line, bubble sort the 6 numbers on them, then move onto the next line. The only problem is I am confused now by the 3 or more variables involved here, Lines isn't so bad as that is the main for loop, so does everything within, for each line. The next is a blur to me however. How do i be sure that I swap Guess[Line][1] with Guess[Line][2] etc, and then go back if there was at least one swap and do the same until there are no swaps on that line?

I've worked so hard and my program is perfect, I am just so drained and this is literally the last hurdle, and I'm not quite sure I can understand your examples...
Volatile Pulse (1543)
I edited my previous post, but I guess it was after you had already viewed it. You basically had it, but try making the changes that I bolded and see if that fixes your issue. Also, the for n loop, should just be identical to my swap loop above. The only reason you even need n is for the max size of the array. Even though its frowned upon by programmers, you can just put the number in place of the only time you actually use n, after making the changes that is.

Edit: Also note that to change my bubble sort to work with yours, you need to change the array name to guesses and also add [Line] after the array name. Also change ARRAY_MAX to 6.
Last edited on
WilliumBobCole (30)
so going by mine, I have changed instances of n from within the third for loop to instead be the value of sort, so now it is as follows

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
 
    //---BUBBLE SORT CODE-------------------------------------
    for(int Line = 0; Line < Lines; Line++)
    {
        bool swap = true;


        for(int n = 0; swap; n++)
        {
            swap = false;//resets flag
            for (int sort = 0; sort < (n - 1); sort++)
            {
                if(Guess[Line][sort+1] < Guess[Line][sort])     //if the next in the array is less than this one
                {
                     int temp;
                     temp = Guess[Line][sort+1];             //swap elements using temp data storage
                     Guess[Line][sort+1] = Guess[Line][sort];
                     Guess[Line][sort] = temp;
                     swap = true;               //indicates that a swap occurred.
                }

                if(n == 6)
                {
                    n=0;
                }
            }
        }
    }


again it compiles but does nothing, but i think it is almost there isn't it? do I NEED the three for loops or do i just need two? I put three because I have a 2D array, but maybe if I make it just two for loops, one for the lines, and the other for swapping, and cut the swap loop off when i sorts all 6 numbers on that line... ah this is confusing as hell lol

also, what do you mean by changing ARRAY_MAX to 6? the second part of the array, usually called n, is never more than 6 anyway...
Last edited on
Volatile Pulse (1543)
You need the middle loop, albeit it can be a while loop instead of a for loop. Your issue though is that n should be equal to 6, not zero. Also, don't increment n. That's why I said in the last for loop to change n-1 to 6-1 or just 5. Then your middle for loop should look just like my outer for loop.
WilliumBobCole (30)
OH
I've got it to swap the first number at least!! I needed to more swap = false; to within the final for loop instead of before it, otherwise that for loop never runs!

now I need to make it swap the next numbers...

edit: now it sorts 2 of the 6 numbers...
if I put in 6 5 4 3 2 1 as the first line, it will out put 4 3 2 1 5 6. part way there, why does it stop before all numbers are sorted? here is it now:

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
 
//---BUBBLE SORT CODE-------------------------------------
    for(int Line = 0; Line < Lines; Line++)
    {
        bool swap = true;


        for(int n = 6; swap; )
        {
            for (int sort = 0; swap == true && sort < (n - 1); sort++)
            {
                swap = false;//resets flag

                if(Guess[Line][sort+1] < Guess[Line][sort])     //if the next in the array is less than this one
                {
                     int temp;
                     temp = Guess[Line][sort+1];             //swap elements using temp data storage
                     Guess[Line][sort+1] = Guess[Line][sort];
                     Guess[Line][sort] = temp;
                     swap = true;               //indicates that a swap occurred.
                }

                if(swap == 6)
                {
                    swap = 0;
                }
            }
        }
    }
Last edited on
Volatile Pulse (1543)
Sorry, I've been trying to respond on my phone and it's irritating using a virtual keyboard to try to type out what I mean. Here is what I meant for your code:
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
 
    //---BUBBLE SORT CODE-------------------------------------
    for(int Line = 0; Line < Lines; Line++)
    {
        // bool swap = true;
        // swap is declared in the next loop, no need for it here

        // for(int n = 0; swap; n++)
        // And here
        for (bool swap = true; swap; )
        {
            swap = false;//resets flag
            // for (int sort = 0; sort < (n - 1); sort++)
            // This is what I mean for changing n
            for (int sort = 0; sort < (6 - 1); sort ++)
            {
                if(Guess[Line][sort+1] < Guess[Line][sort])     //if the next in the array is less than this one
                {
                     int temp;
                     temp = Guess[Line][sort+1];             //swap elements using temp data storage
                     Guess[Line][sort+1] = Guess[Line][sort];
                     Guess[Line][sort] = temp;
                     swap = true;               //indicates that a swap occurred.
                }

               /* if(n == 6)
                {
                    n=0;
                }*/ // This isn't needed, n isn't relevant
            }
        }
    }


That should fix your sort algorithm. The reason it wasn't working was because swap would be set to false, n was equal to 0, but you have 6 numbers, not 6, and sort is equal to 0. So in the inner most loop, sort is less than 0 - 1 so that loop never runs. It returns to your middle loop and swap is no longer true so it exits that loop. When you moved the false down a line, it forced it to have to run through that inner most loop twice before setting swap to false.
goth (47)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
    //---BUBBLE SORT CODE-------------------------------------
    for(int Line = 0; Line < Lines; Line++)
    {
        bool swap = true;

        do
        {
            swap = false;//resets flag
            for (int sort = 0; sort < (n - 1); sort++)
            {
                if(Guess[Line][sort+1] < Guess[Line][sort])     //if the next in the array is less than this one
                {
                     int temp;
                     temp = Guess[Line][sort+1];             //swap elements using temp data storage
                     Guess[Line][sort+1] = Guess[Line][sort];
                     Guess[Line][sort] = temp;
                     swap = true;               //indicates that a swap occurred.
                }
            }
        }while(swap);
    }
WilliumBobCole (30)
please forgive me, I am almost getting this, I have removed n entirely now, and changed from a for to a do while swap is true loop, but it still only moves the first 2 numbers to their correct positions and I can't see what is limiting it to just those two. Hopefully this code is a little cleaner now anyway, seeing as n is gone.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
//---BUBBLE SORT CODE-------------------------------------
    for(int Line = 0; Line < Lines; Line++)
    {
        bool swap = true;

        do
        {
            for (int sort = 0; sort < 5; sort++)
            {
                swap = false;   //resets flag

                if(Guess[Line][sort] > Guess[Line][sort+1])     //if this number is greater than the next
                {
                    int temp;
                    temp = Guess[Line][sort+1];             //swap elements using temp data storage
                    Guess[Line][sort+1] = Guess[Line][sort];
                    Guess[Line][sort] = temp;
                    swap = true;               //indicates that a swap occurred.
                }
            }
        }
        while(swap);
    }
Volatile Pulse (1543)
Move the swap outside of the for loop. That should fix your problem.
cire (8284)
Line 10 should be between line 7 and line 8, just like the post above yours shows.
WilliumBobCole (30)
oh my giddy days thank you so much now my program is complete aside from a few cosmetic adjustments including pauses between printing the ticket and between starting to generate the balls and between each ball, and maybe the colour of the console window lool! yay!!

Source code for anyone that wants to play my new game and maybe check over the code or bug test or whatever, but I truly believe it is watertight now, please feel free to prove me wrong! :P
http://pastebin.com/2MYs004F
Last edited on
goth (47)
I'm insanely rich right now:
You now have #142354459 in your wallet to play with!


I think you should lower the chances or maybe compare the numbers entered in the same order they were extracted by the machine (if I enter 1,2,3,4,5,6 then there's almost 100% chance ([edit:] 60%, still kind of high) that I win something, even if the balls are extracted in a different order since I think you compare them after sorting the lines)

Great job otherwise.
Last edited on
WilliumBobCole (30)
there's definately not 100% chance of winning, it checks EACH number that line against EACH ball, regardless of order, and does that for each line, and increases score for each line's total matches, which ultimately pays out the winnings in one go. I forgot to make it so that you need to bet within 1 and 49 instead of 1 and 10 (which just made debugging much easier). to fix this, just change BetHigh from 10 to 49 (it's in the global variables at the top)

I have found a couple of hidden bugs since then that weren't major but they kinda broke the game. NOW I think it's watertight ;P

I have also added in some fancy things like pauses and text colour. I am now just trying to prevent input whilst the program is doing work... for example, after you pick the numbers on each line, it has to do lots of things like print the ticket, generate and print the balls, compare them all together, and print out your winnings, and with the pauses in place now, you can type whilst all this is happening, you can't see anything until these processes are finished, but it will be in the input field when it next asks for input. AND, if you press enter whilst you type in something random and cant see it, it will immediately put that into the next input field, without you ever knowing what it was or where it will go. so if you type gsfgjdfl whilst it is printing the ticket and press enter, when it asks if you want to play with the same ticket, it will immediately run that code with the input gsfgjfl, which of course will not DO anything as it is not considered valid... but how do i prevent the user from typing anything into cin UNTIL it ASKS for cin?

I have tried variations of cin.ignore or cin.flush or cin.clear, none of them either compile, or DO what i want when they do compile...

once that is added, it's only minor but i would like it... THEN my program will be complete and i will re-paste the code for you to try again =]
goth (47)
You can add FlushConsoleInputBuffer(GetStdHandle(STD_OUTPUT_HANDLE)); right after you want to ask for the user's input(after all those pauses) to clear the stream.
WilliumBobCole (30)
I put this before, and then after, the next request for input, but the text still pops up when asking for input, and still automatically uses that input if, during the pauses, you follow that input with enter...
WilliumBobCole (30)
i have also tried cin.ignore(1000,'\n');, immediately after taking one input, immediately before taking another input, and immediately after taking the next input (which doesnt even make sense)

nothing seems to ignore input, whether the user presses enter or not

i am basically asking, is there a way of locking any keyboard entry from occurring at all, be it charaters integers symbols or any other key such as space or enter, EXCEPT when cin is required. And of course without rewriting everything just to fit this in...
Last edited on
Chervil (7320)
how do i prevent the user from typing anything into cin UNTIL it ASKS for cin?
You can't unless you take away the keyboard, or tie the user's hands.

However, what you can do is to empty the input buffer before getting any input. Try cin.sync(); before using cin.
http://www.cplusplus.com/reference/istream/istream/sync/
goth (47)
This should do the trick:
1
2
3
4
5
6
7
8
 
//...code...
    BlockInput(1);
//...do output stuff and Sleep()'s like so:
    Sleep(2000);
    cout << "Input is blocked " << endl;
//...etc...
    BlockInput(0);
    cout << "Enter input: "; keybd_event(VK_LCONTROL,0,0x0002,0); cin.get();


(make sure you include <winable.h> and be careful when using BlockInput(); not deactivating it(BlockInput(0)) freezes your system until you press ctrl+alt+del)
Pages: 12