Can someone explain this bubble sort example to me
Hi. I'm trying to learn C (no prior programming experience) and came across this bubble sort example:
To me it appears that the first time the if-statement in the inner for-loop runs...
"if (nums[inner] < nums[outer])"
...the same two array elements are compared, because outer is assigned to inner in the inner for-loop start expression.
That doesn't make sense to me, but being a rookie I'm aware that I'm missing something. Can someone explain to me why I'm wrong or why this is done?
“ // Sort the array
for (outer = 0; outer < 9; outer++)
{
didSwap = 0; //Becomes 1 (true) if list is not yet ordered
for (inner = outer; inner < 10; inner++)
{
if (nums[inner] < nums[outer])
{
temp = nums[inner];
nums[inner] = nums[outer];
nums[outer] = temp;
didSwap = 1;
}
}
if (didSwap == 0)
{
break;
}
}
// Now list the array as it currently is after sorting
puts("\nHere is the list after the sort:");
for (ctr = 0; ctr < 10; ctr++)
{
printf("%d\n", nums[ctr]);
}
return(0);
}”
Excerpt From: Dean Miller. “C Programming Absolute Beginner's Guide, 3/e.” iBooks. https://itun.es/dk/mgpUO.l
To me it appears that the first time the if-statement in the inner for-loop runs...
"if (nums[inner] < nums[outer])"
...the same two array elements are compared, because outer is assigned to inner in the inner for-loop start expression.
That doesn't make sense to me, but being a rookie I'm aware that I'm missing something. Can someone explain to me why I'm wrong or why this is done?
“ // Sort the array
for (outer = 0; outer < 9; outer++)
{
didSwap = 0; //Becomes 1 (true) if list is not yet ordered
for (inner = outer; inner < 10; inner++)
{
if (nums[inner] < nums[outer])
{
temp = nums[inner];
nums[inner] = nums[outer];
nums[outer] = temp;
didSwap = 1;
}
}
if (didSwap == 0)
{
break;
}
}
// Now list the array as it currently is after sorting
puts("\nHere is the list after the sort:");
for (ctr = 0; ctr < 10; ctr++)
{
printf("%d\n", nums[ctr]);
}
return(0);
}”
Excerpt From: Dean Miller. “C Programming Absolute Beginner's Guide, 3/e.” iBooks. https://itun.es/dk/mgpUO.l
Gyes - I'm a beginner as well, but since no one has answered you and I've used that same book, I'll throw in may 2 cents.
I think this example has 2 problems:
1. The purpose of the inner loop is to compare the inner integers one by one to the outer integer. If the inner integer is less than, swap them. As you mentioned though, the first iteration of the inner loop is a bit redundant:
for (inner = outer; inner < 10; inner++)
That will have the first iteration comparing the same array variable to itself. Since the number won't ever be less than itself, no swap will take place and it will move to the next iteration - comparing the next inner number to the outer number. For efficiency, the inner loop should have probably looked like this:
for (inner = outer + 1; inner < 10; inner++)
2. Perhaps I'm missing something, but the "break" on the "didSwap" is a huge flaw in this sort. This will work most times, but during my test fails about 1 out of 5 times for good reason.
The authors logic is that if no inner swap took place, then obviously the array is already in order. Not so. Take the following array -
int nums[10] = {1, 21, 92, 8, 37, 42, 60, 75, 49, 12}
The outer loop will put the counter at 0 which is the array variable "1". The inner loop will then proceed to compare 1 to all the other variables. It will first compare array variable "1" to itself (the error I already mentioned), then to 21, then to 92, and so on. It will make a swap if any integer is less than 1. When the inner loop is finished, it will find that no swap took place and leave "didSwap" at 0.
This program will now stop the outer loop ( if (didSwap == 0){break;} because no swap took place on the inner loop. The program as written believes the above array is in numerical order. As you can see though, this array is far from in numerical order.
What should happen logically is that the outer loop will move the variable to 21. Then the inner loop will compare 21 to 92, then to 8 and swap because 8 is less than 21. Like I said, maybe I'm missing something, but this seems like a huge logical flaw - that's repeated in the next example in the book!!
I think this example has 2 problems:
1. The purpose of the inner loop is to compare the inner integers one by one to the outer integer. If the inner integer is less than, swap them. As you mentioned though, the first iteration of the inner loop is a bit redundant:
for (inner = outer; inner < 10; inner++)
That will have the first iteration comparing the same array variable to itself. Since the number won't ever be less than itself, no swap will take place and it will move to the next iteration - comparing the next inner number to the outer number. For efficiency, the inner loop should have probably looked like this:
for (inner = outer + 1; inner < 10; inner++)
2. Perhaps I'm missing something, but the "break" on the "didSwap" is a huge flaw in this sort. This will work most times, but during my test fails about 1 out of 5 times for good reason.
The authors logic is that if no inner swap took place, then obviously the array is already in order. Not so. Take the following array -
int nums[10] = {1, 21, 92, 8, 37, 42, 60, 75, 49, 12}
The outer loop will put the counter at 0 which is the array variable "1". The inner loop will then proceed to compare 1 to all the other variables. It will first compare array variable "1" to itself (the error I already mentioned), then to 21, then to 92, and so on. It will make a swap if any integer is less than 1. When the inner loop is finished, it will find that no swap took place and leave "didSwap" at 0.
This program will now stop the outer loop ( if (didSwap == 0){break;} because no swap took place on the inner loop. The program as written believes the above array is in numerical order. As you can see though, this array is far from in numerical order.
What should happen logically is that the outer loop will move the variable to 21. Then the inner loop will compare 21 to 92, then to 8 and swap because 8 is less than 21. Like I said, maybe I'm missing something, but this seems like a huge logical flaw - that's repeated in the next example in the book!!
That is NOT bubble sort. Bubble sort only compares adjacent items. For example:
int nums[10] = {1, 21, 92, 8, 37, 42, 60, 75, 49, 12}
First pass would compare 1 and 21, then 21 and 92, then 92 and 8, and so on...
Resulting in {1, 21, 8, 37, 42, 60, 75, 49, 12}
Second pass would compare again and so on until it is sorted.
The algorithm you posted compares each item with all others. So as soon it finds an item in the correct position it will assume all others are as well.
Better to read wikipidia http://en.wikipedia.org/wiki/Bubble_sort
int nums[10] = {1, 21, 92, 8, 37, 42, 60, 75, 49, 12}
First pass would compare 1 and 21, then 21 and 92, then 92 and 8, and so on...
Resulting in {1, 21, 8, 37, 42, 60, 75, 49, 12}
Second pass would compare again and so on until it is sorted.
The algorithm you posted compares each item with all others. So as soon it finds an item in the correct position it will assume all others are as well.
Better to read wikipidia http://en.wikipedia.org/wiki/Bubble_sort
Thanks for the info ccsdude. This is the example given in the book the OP mentioned for a bubble sort.
Am I correct in assuming that this program will fail due to the break that's written in? As you said, it will assume all others are in the correct position if one is. Let me know if I'm wrong because I want to make sure that I'm not missing something.
Am I correct in assuming that this program will fail due to the break that's written in? As you said, it will assume all others are in the correct position if one is. Let me know if I'm wrong because I want to make sure that I'm not missing something.
Topic archived. No new replies allowed.