Practice Assignment

Information

1. Write a function that will sort an array of integers. There are countless ways to do sorting, some are very easy to implement, some, not so easy. Since this is our first attempt at sorting, we're going to go the easy way. Simple sorting methods include selection sort, insertion sort, and exchange sort, also known as a bubble sort. All of these methods are similar in their implementations and performance.

   We're going to implement the bubble sort. Some of you have probably already seen this and maybe even know it's not a very good way to sort things. That may be, but we aren't interested in "the best" sort method at this point. (That time will come later...) I just want everyone to see this sort, so that when you compare it to others, you'll see and understand the differences.

   A bubble sort works by comparing adjacent items and exchanging (swapping) them if they are out of order. The meaning of "out of order" depends on how you want the items sorted: smallest to largest, or largest to smallest.

   Courtesy of Wikipedia

   More details about the algorithm are here. Basically, you will have a nested for loop. You won't need more than 10 lines of code, and may be able to have less, depending on how you do your logic.

   This is the prototype for the function:

   void bsort(int array[], int size);
   

   You'll notice that the array is not marked with the const keyword. This is simply because you are going to modify the array. You must sort the elements in-place. That's why it's not const. This means that you are not allowed to create another array.

   The name of the file should be named bsort.c and the command to compile it will look like this:

   gcc -Werror -Wall -Wextra -ansi -pedantic -O2 -o bsort main.c bsort.c PRNG.c
   

   Files:
   • Here is a sample driver file main.c: HTML   Text
   • Random number generator files (put these in the same directory as your C file)
     • - Header file (PRNG.h): HTML Text
     • - Implementation (PRNG.c): HTML Text

   • Here is a sample output file for you do diff with.

Notes

• Approximate number of lines of code: 8.
• You don't need to include any header files in your .c file.

• This is probably the simplest practice program thus far. (You will need it for future assignments.)
• If you are having trouble understanding the algorithm, please read this explanation first.

The bubble sort is called an N² algorithm because the number of operations required on N items is N², in the worst case. Other N² trivial sorting algorithms are selection sort and insertion sort. Both of those will typically run faster than a bubble sort. However, at this stage in your career, you are more worried about correctness than performance. In the Real World™ none of these sorting methods would be useable with large numbers of items. However, any of these algorithms provide a beginning programmer with a chance at creating a very simple sort function using the C programming language. You'll learn all about performance (worst-case asymptotic time complexity) of various algorithms and data structures in courses such as Data Structures and Algorithm Analysis.