Bubble Sort code (Please help)

[Pip3mAn]

hello i am new here and i am also just a beginner in C++.
I have made a bubble sort program but there seems to be a problem in it. it dose not seem to sort the last line of numbers i.e. i think it dose not repeat the loop once it has completed it even though there is still numbers left to be sorted in it i have tried to fix that problem but instead it now runs a infinite loop.

the output of the program is as below:

How many numbers do you want to swap? 3

Please enter the 3 numbers one by one 3
Please enter the 3 numbers one by one 2
Please enter the 3 numbers one by one 1

3    2    1
2    3    1
2    1    3
2    1    3
this is where the infinite loop keeps going.....

as you can see in the output the last line of numbers is never sorted for some reason and instead initiates a infinite loop.

#include <iostream.h>

int swappingFunction(int *x, int *y){
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

main(){

    int userDASize; // that means user defined array size...
    
    // Asking the user for the arraySize.
    cout << "How many numbers do you want to swap? ";
    cin >> userDASize;
    cout << endl;
    
    // Declaring constant arraySize.
    const int arraySize = userDASize;
    
    // Declaring array and variables.
    int numbersToBeSwapped[arraySize],i,j,k,swap;
    
    // Populating the array.
    for(i = 0; i < arraySize; i++){
        cout << "Please enter the " << arraySize << " numbers one by one ";
        cin >> numbersToBeSwapped[i];
    }
    
    // Displaying the unsorted list.
    for(i = 0; i < arraySize; i++){
        cout << numbersToBeSwapped[i] << "\t";
    }
    
    cout << endl;
    
    // Swap = 0 means that no swap as occured 1 means it has.
    swap = 0;
    
    // Sorting the numbers.
    for(i = 0; i < arraySize; i++){
        if(numbersToBeSwapped[i] > numbersToBeSwapped[i + 1]){
            swap = 1;
            // Function call. The address of i and i + 1 index value is sent to the function.
            swappingFunction(&numbersToBeSwapped[i],&numbersToBeSwapped[i + 1]);
        }
        
        if(swap == 1 && i == arraySize - 1){
            i = 0; // this is to repeat the loop if a swap has occurred in the above if statement.
        }
        else if(swap == 0){ // if no swap has occurred then it is safe to exit the loop.
            break;
        }
        
        // displaying the sorted numbers.
        for(j = 0; j < arraySize; j++){
            cout << numbersToBeSwapped[j] << "\t";
        }
        cout << endl;
    }
    
    system("PAUSE");
    
}

[Gaminic]

You're code (and logic) is a bit messy, but at first sight it should work. Just add the line "swap = 0" behind line 50. Now, if a single swap is made, swap is set to 1. This never changes back to 0, hence the infinite loop.

If that does the trick, you can start reanalyzing your algorithm logic and make it much more efficient with just a few insights.

[edit]
Also, don't use system() commands.

[TheMeerkat]

I think you should get rid of

else if(swap == 0){ // if no swap has occurred then it is safe to exit the loop.
            break;
        }

What I think you actually mean in that else if statement is else if((swap == 0) && (i== arraySize - 1)){

Otherwise, I would have guessed that you could actually be breaking out of the for statement before you mean to. Also within

if(swap == 1 && i == arraySize - 1){
            i = 0; // this is to repeat the loop if a swap has occurred in the above if statement.
        }

you should also set swap back to 0, that's probably where your infinite loop is coming from.

EDIT: Beaten to it.

[Pip3mAn]

the infinite loop has stopped. but the main problem still seems to be there i.e. the function is not sorting 2 and 1... the last line should be

1 2 3 not 2 1 3.

[TheMeerkat]

did you get rid of

else if(swap == 0){ // if no swap has occurred then it is safe to exit the loop.
            break;
        }

Can't actually see how that would be the problem but I'm pretty sure it shouldn't be there.

[Gaminic]

After a second look, I'm actually quite confused your code compiles...

You're using static declaration of an int with variable size (as it is read from user input). That shouldn't be possible. Either the size must be known at compile time, or you need to use dynamic declaration.

Anyway, considering the sorting logic, here's a hint: if i = T, all elements before T are sorted and can be ignored, until a smaller element is dragged back. Dragging back can only happen step-per-step. This means "resets" ('i=0') are useless. Instead, when a swap is found, have it take a step back ('--i'). That way, the currently swapped element will be compared to its new predecessor, until it hits a smaller predecessor.

That way, you can drop the "swap" variable and the confusion/mess it brings with it.

[hellohellomoon]

Hm, I'm new too but that was pretty confusing. I thought it would be a little easier for me to understand by now but nope. How long have you been coding for? Just wondering.

[Gaminic]

C++? Bit over a year now, on and off.

Here's a golden tip for designing algorithms: work it out on paper. Several times and for several different examples. It's very easy to find "unnecessary steps" when doing it manually. In this case, you would have realized that "starting over" when a swap is found is useless, as simply taking a step back is sufficient.

[Pip3mAn]

thanks for the help tho i think i found the problem. I.ll check what you said in a few minutes and reply back if it works or not. also hellohellomoon if you were asking me that. i have been coding for about just 1 week so still getting the hang of things..

[moorecm]

How are you doing a bubble sort that is O(n²) with just one loop?

[ne555]

Hi, your book and your compiler are ancient.

#include <iostream> //not .h, you will need to use namespaces too

int main(){ // main must return int 

I don't see where swap is declared, but you should be using bool and true, false values

The logic of the program is incorrect. You are traversing the array just one time.

[rmsharkey]

First, It's not a "bubble sort", it's an "insertion sort".

Second, If you happen to have two input numbers that are already in sort order, then your loop will terminate prematurely due to line 52 if I'm not mistaken.

Here is a little more nicely structured example of an insertion sort:

#include<stdio.h>
void main()
{
	int A[20], N, Temp, i, j;
	printf("\n\n\t ENTER THE NUMBER OF TERMS...: ");
	scanf("%d", &N);
	printf("\n\t ENTER THE ELEMENTS OF THE ARRAY...:");
	for(i=0; i<N; i++)
	{
		scanf("\n\t\t%d", &A[i]);
	}
	for(i=1; i<N; i++)
	{
		Temp = A[i];
		j = i-1;
		while(Temp<A[j] && j>=0)
		{
			A[j+1] = A[j];
			j = j-1;
		}
		A[j+1] = Temp;
	}
	printf("\n\tTHE ASCENDING ORDER LIST IS...:\n");
	for(i=0; i<N; i++)
		printf("\n\t\t\t%d", A[i]);
	getch();
}

[hellohellomoon]

Oh wow. Gaminic I would of thought you'd programmed for longer than a year. Maybe two years or more.

And Pip3man I would of thought you programmed for a few months.

If you only learned C++ for a week, how come you could make your code all neat and
stuff? I mean, I'm not saying I don't believe you but I can only think of two reasons

1. The first is that you're talented
2. The second is that this isn't your first programming language.

So is C++ your first programming language. I'm just curious because I just want to see where
I'm at and how fast or how slow I'm progressing.

I've been trying to learn C++, which is my very first language and no prior experience, for about one month and a half, on and off. I've gotten most of the beginning syntax down. But, it was still hard for me.

So, I'm curious, what is your study routine like? Maybe I'm doing something wrong.

[Pip3mAn]

ne555 the swap variable is declared at line 23 . i haven't used bool and true false values yet the lectures and book im reading about C++ did not introduce them yet and yes the book im reading is indeed ancient it was made in 2004 i guess tho i have the C++ for dummies book too that should fill the gap. and btw i am using dev C++ if there is any other better compiler i should know about do tell.

moorecm: i don't get it a bubble sort can be done with just one loop.. the only problem in my program is that it dose not seem to be sorting 2 with 1 and 1 with 2 i.e. index[0] with index[1] everything seems to be correct in the function so i am guessing that somethings wrong in the main code.

hellohellomoon: i have done java script before not a pro at it but i have done the basics and some advanced topics in it.

[TheMeerkat]

bool true and false are essentially just the same and int 0 and 1. But bool is considered better to use for cases like this as it makes it more obvious what you are trying to do. Instead of declaring it as int swap; do bool swap; are set/check them as true or false instead of 0 or 1.

Second, If you happen to have two input numbers that are already in sort order, then your loop will terminate prematurely due to line 52 if I'm not mistaken.

Yea, like I've said before, I'm pretty sure just getting rid of that entire else if statement should fix the problem.

Are you sure that there isn't anything weird going on within the for loop, like the array isn't being updated when the number get swapped? Try completely leaving the for loop and using a while loop or something to re-enter it, it's probably a long shot, and I really don't know the inner workings of how code actually runs to know if I'm talking complete rubbish or not.

Dev C++ seems to be considered too old. I've heard a few people recommend code::blocks before. Don't have an opinion on it personally though.

[stridexr]

Why Dev-C++ is rubbish:

http://cplusplus.com/articles/36vU7k9E/

[Pip3mAn]

yea there is indeed something wrong going on in the loop but i think i found it dont still know how to fix it though but the problem is that the for loop on 39 seems to be not repeating itself. let me be clear on what my real problem was my real problem was that the for loop at line 39 dose not repeat itself when it should be repeating itself.

this is an updated output of the program after i fixed the code a bit as you can see in the output there should be one last line i.e. 1 2 3 but its not being printed because the for loop at line 39 dose not repeat itself.

How many numbers do you want to swap? 3

Please enter the 3 numbers one by one 3
Please enter the 3 numbers one by one 2
Please enter the 3 numbers one by one 1

3    2    1
2    3    1
2    1    3

i have updated the code and fixed some problems in it i.ll advise you to see this one now.

#include <iostream.h>

int swappingFunction(int *x, int *y){
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

main(){

    int userDASize; // that means user defined array size...
    
    // Asking the user for the arraySize.
    cout << "How many numbers do you want to swap? ";
    cin >> userDASize;
    cout << endl;
    
    // Declaring constant arraySize.
    const int arraySize = userDASize;
    
    // Declaring array and variables.
    int numbersToBeSwapped[arraySize],i,j;
    
    // Populating the array.
    for(i = 0; i < arraySize; i++){
        cout << "Please enter the " << arraySize << " numbers one by one ";
        cin >> numbersToBeSwapped[i];
    }
    
    // Displaying the unsorted list.
    for(i = 0; i < arraySize; i++){
        cout << numbersToBeSwapped[i] << "\t";
    }
    
    cout << endl;
    
    // Sorting the numbers.
    for(i = 0; i < arraySize; i++){
        if(numbersToBeSwapped[i] > numbersToBeSwapped[i + 1]){
            // Function call. The address of i and i + 1 index value is sent to the function.
            swappingFunction(&numbersToBeSwapped[i],&numbersToBeSwapped[i + 1]);
            --i;
        }
        
        // displaying the sorted numbers.
        if(numbersToBeSwapped[i] > numbersToBeSwapped[i + 1]){
            for(j = 0; j < arraySize; j++){
                cout << numbersToBeSwapped[j] << "\t";  
            }
            cout << endl;
        }
    }
    
    system("PAUSE");
    
}

edit: stridexr: yeah tell me about it dev C++ has alot of bugs thanks for the link needed to find some good IDE now i did.

[TheMeerkat]

I'm not sure if simply putting --i will work.

if you have the numbers:
(2 3 1)

i==0: nothing will happen
it will get to the end of the for loop i++
i== 1: 3 and 1 will swap
i--
new order== (2 1 3)
goes to the end of the for loop i++
i==1: 1 is less than 3 so the for loop will end.

You actually want i to decrement by 2 unless i==0, in which case don't decrement at all.


What IDE did you go for?

[Pip3mAn]

yeah that's kind of what i want to do im gonna open the compiler now and do that.

and i downloaded code blocks it seems good i.ll just have to use it and see.

EDIT: i think im just gonna create the program from scratch again with a different loop this time maybe i.ll catch the problem in the way. i.ll let you guys know if it works..

[Gaminic]

@People saying "Can't do BubbleSort with 1 loop because it's O(n²)":

Yes you can. Imagine the row 3 4 2 1, and you wish to sort low-to-high.

i = 0: compare (3,4), see it's correct, ++i. (3 4 2 1)
i = 1: compare (4,2), see it's wrong, swap, --i. (3 2 4 1)
i = 0: compare (3,2), see it's wrong, swap, see i = 0, ++i. (2 3 4 1)
i = 1: compare (3,4), see it's correct, ++i.
i = 2: compare (4,1), see it's wrong, swap, --i. (2 3 1 4)
i = 1: compare (3,1), see it's wrong, swap, --1 (2 1 3 4)
i = 0: compare (2,1), see it's wrong, swap, see i = 0, ++i. (1 2 3 4)
i = 1: compare (2,3), see it's correct, ++i.
i = 2: compare (3,4), see it's correct, ++i.
i = 3: see i+1 = numElements, quit.

It works with one loop because it always checks the neighbor. Keep in mind that O(n²) means Worst Case Scenario performance. A pre-sorted list will be "bubblesorted" in linear time. Any other case will be worse, because of the "stepping back" after swaps.

[Note: the increments and decrements in the example have to be adjusted in case of a simple "++i" for. I use a different control structure.]

@hellohellomoon:
I learned some basic PHP at a very early age, but never really got into it. Just sufficient to have a basic grasp of control structures, variables and functions. About a year ago (think around early July 2010) I started learning C++, but in a very functional way. All I need are the skills to implement algorithms and data structures, nothing else. Ask me a question about interfaces, graphics or anything beyond std::cout and I won't have a clue. I've never used a non-standard library and I wouldn't even know how to "install" it.

I learned by means of online tutorials (which was bad), the Introduction to C++ by Microsoft (which was worse, at that point) and this forum. Also, I have the tendency to read up on algorithms before trying to implement them. The OP of this topic probably wouldn't have posted his question had he bothered to read the Wikipedia page on Sorting. Even the pages that don't include (pseudo)code generally lay out the problem so clearly that all you need to do is translate into code.