I'm trying to write a simple bubble sort algorithm but it isn't working. The array is unchanged when it is printed at the end.
I have used the debugging tools on my IDE and it tell's me that the second for loop isn't incrementing but I can't tell why it isn't.
I'm still new to learning C++ and algorithms in general, so pointers on this would be helpful.
Here's the code, many thanks.
#include <iostream>
int main(){
int A[] = {13, 89, 43, 74, 45, 16};
int n = sizeof(A)/sizeof(*A);
for (int i=0; i<n; i++) { //pass through the algorithm n-1 times
int flag = 0;
for (int j=0; j<n-i-1; j++) { //optimise checks, avoid checking sorted part of array
if (A[j] > A[j+1]) {
int temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
flag = 1; //shows a swap happened
}
if (flag == 0) { //no swaps have occurred so the loop is over
break;
}
}
}
for (int i = 0; i < n; i++) {
std::cout << A[i] << " ";
}
return 0;
}
Your algorithm is wrong. You should check the flag after the second loop has finished
int flag = 0;
for (int j=0; j<n-i-1; j++) { //optimise checks, avoid checking sorted part of array
if (A[j] > A[j+1]) {
int temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
flag = 1; //shows a swap happened
}
}
if (flag == 0) { //no swaps have occurred so the loop is over
break;
}
The fact that you are initialising the flag before the second loop, but checking it inside the second loop should have been a clue that something was not quite right. So should have the debugger telling you that the second loop was not incrementing.
Sometimes when you look at your own code you'll just see what you think you wrote, not what you actually wrote. Looknig at your own code objectively is a habit you need to train yourself to do.