Minimal, reproducible example:
#include <stdio.h>
main() {
int ctr, inner, outer, didSwap, temp;
int nums[10] = {0, 1, 9, 7, 8, 4, 3, 5, 7, 10};
for (outer = 0; outer < 9; outer++) {
didSwap = 0;
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;
}
}
puts("\nHere is the list after the sort:");
for (ctr = 0; ctr < 10; ctr++) {
printf("%d\n", nums[ctr]);
}
return (0);
}
Book code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
main() {
int ctr, inner, outer, didSwap, temp;
int nums[10];
time_t t;
// If you don't include this statement, your program will always
// generate the same 10 random numbers
srand(time( & t));
// The first step is to fill the array with random numbers
// (from 1 to 100)
for (ctr = 0; ctr < 10; ctr++) {
nums[ctr] = (rand() % 99) + 1;
}
// Now list the array as it currently is before sorting
puts("\nHere is the list before the sort:");
for (ctr = 0; ctr < 10; ctr++) {
printf("%d\n", nums[ctr]);
}
// 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);
}
Tweaked book code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
main() {
int ctr, inner, outer, didSwap, temp;
int nums[10];
time_t t;
srand(time( & t));
nums[0] = 0; //set the first element of the array to the lowest value possible
for (ctr = 1; ctr < 10; ctr++) {
nums[ctr] = (rand() % 99) + 1;
}
puts("\nHere is the list before the sort:");
for (ctr = 0; ctr < 10; ctr++) {
printf("%d\n", nums[ctr]);
}
for (outer = 0; outer < 9; outer++) {
didSwap = 0;
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;
}
}
puts("\nHere is the list after the sort:");
for (ctr = 0; ctr < 10; ctr++) {
printf("%d\n", nums[ctr]);
}
return (0);
}
From the book,
The next program sorts a list of 10 numbers. The numbers are randomly generated using rand(). The bubble sort routine is little more than a nested for loop. The inner loop walks through the list, swapping any pair of values that is out of order down the list. The outer loop causes the inner loop to run several times (one time for each item in the list).
An added bonus that is common to many improved bubble sort routines is the testing to see whether a swap took place during any iteration of the inner loop. If no swap took place, the outer loop finishes early (via a break statement). Therefore, if the loop is sorted to begin with, or if only a few passes are needed to sort the list, the outer loop doesn’t have to finish all its planned repetitions.
The second paragraph has to do with didSwap as it determines whether or not the program finishes early, if it's equal to zero.
The first example (from top to bottom) yields an unsorted array because no integer is less than the first element 0 in the array int nums[10] and so nums[inner] < 0 is false for every inner from 0 to 9 (inclusive). As a consequence, didSwap remains equal to zero, which finishes the program early: if (didSwap == 0) { break;}. However, according to the book, this means that the array was already sorted, but this is not the case.
Have I missed something? If not, I would like to know how would you modify the code to allow for what the book says in the second paragraph: "If the loop is sorted to begin with, or if only a few passes are needed to sort the list, the outer loop doesn’t have to finish all its planned repetitions." I haven't been able to think of something.
