This program implements the "bubble sort", which is one of many known methods used for sorting (long) sequences of numbers. Sorting theory is a field in itself, and it can be shown that the bubble sort is one of the least efficient methods available in most cases. It is, however, easy to understand, which is why it is being used in this example.
/* bubbles.c - A simple bubble sort program */ #include#define DEBUG /* This is a useful method for including code which is only used for debugging the program, and which can be removed when the debugging has finished. Look for the "#ifdef DEBUG" and "#endif" statements below */ #define NUM 10 /* Number of elements to be sorted. Using NUM instead of 10 means that we only have to change the value in one location if we ever want to change this value. It is good practice to _always_ use this method when you use numerical constants in your programs, this also reduces the chance of subtle bugs caused by typing the wrong number. */ main() { int ii, kk, tt, ff; int vv[NUM]; /* This is an array holding NUM (i.e. 10) elements */ /* It is a good idea to print a simple introduction at the start of a program */ printf("\nThis program demonstrates a simple bubble sort\n\n"); /* Get the data */ printf("Please enter %d integer numbers to be sorted\n", NUM); for ( ii = 0; ii < NUM; ii++ ) /* Note the use of NUM instead of 10 */ { printf("Enter value number %2d : ", ii+1 ); scanf("%d", &vv[ii]); } /* One twist here is that C counts the elements of an array from 0 to NUM-1. We humans prefer to start at number 1 and count to NUM. There is no rule stating that the numbering visible to the user has to be the same as the numbering used by the program. Please be aware, however, that this means the programmer needs to keep a close track of the numbering! */ /* We now have our numbers, it is time to get them sorted */ /* This is the _outer_ loop, which is needed to ensure that all the numbers get sorted. Running through the inner loop only is normally not sufficient, it needs to be done repeatedly up to NUM-1 times. The sort may take fewer loops, though */ for ( kk = NUM-1; kk > 0; kk-- ) { ff = 0; /* A counter to keep track of number of swaps for each round */ /* The following is the _inner_ loop, note that it keeps getting shorter as the program progresses. This is because the highest unsorted value will always rise like a "bubble" through the number sequence and end up in its proper position for each time this inner loop is being run */ for ( ii = 0; ii < kk; ii++ ) { if ( vv[ii] > vv[ii+1] ) { /* Swap values */ tt = vv[ii]; vv[ii] = vv[ii+1]; vv[ii+1] = tt; ff++; /* Increment counter */ } } /* End of inner loop */ #ifdef DEBUG /* For debugging purposes, it may be useful to see what is happening while the program is running. The following 6 lines can be commented out or removed when the program is working properly. This can be done "automatically" by just removing the "#define DEBUG" from the top of the program */ printf("\nLoop number %d :\n", (NUM-kk)); for ( ii = 0; ii < NUM; ii++ ) { printf("%d ", vv[ii]); } printf("\nThe number of swaps was %d\n", ff); #endif /* End of debugging code */ /* If no values are swapped in the inner loop, all the values have been sorted, and there is no need to continue, even if the outer loop hasn't finished */ if ( ff == 0 ) { break; /* This statement will break the loop in which it is enclosed - program execution will pass to the end of the loop. Care must be taken to ensure _which_ loop is being terminated! */ } } /* End of outer loop */ /* The actual sort is finished, now print values */ printf("\nThe sorted values are :\n"); for ( ii = 0; ii < NUM; ii++ ) { printf("Sorted value %2d is %d\n", ii+1, vv[ii]); } printf("\n\n"); }