Sorting
Today we will implement the bubble sort algorithm. It's related the handshake problem. Even though the handshake problem is a toy problem, it's related to real problems we do care about solving. This is common in computer science, to see the same problem popping up in unexpected places.
In a previous lab, you used a nested for-loop to print all size-two subsets of a set of
size n. To implement bubble sort on an integer array a,
you need to make a minor modification to
print_two. Instead of printing {i,j}, your program should
check if a[i] and a[j] are in sorted order, if they are, do nothing,
otherwise, swap a[i] and a[j].
Using the above idea implement the function void bubble_sort(int a[], int n).
It should sort the first n elements of array a in ascending order.
Write appropriate PRE/POST comments. What limitations should your PRE comment place
on n? Write a print function to test your code.
Make a second version of bubble_sort. Call it bubble_sort_reversed.
It is should sort the array in reversed order.
In some C++ compilers, you're not allowed to declare arrays with variables. Our compiler allows us to. In this class, you're not permitted to use non-constant expressions to create arrays. All assignments and labs that require you to work with arrays, the maximum size of the array will be given.
Outside of main declare two integer constants; MAX_ROW, MAX_COLUMN.
const int MAX_ROW = 20;
const int MAX_COLUMN = 20;
Use these variables whenever you create an array. This way, if you need more
space for rows or columns, you only need to edit a single line of code.
MAX_ROW, MAX_COLUMN, are global variables. In general global variables
are frowned upon. They lead to hard to find bugs. We do make an exception
for constants since they can't be altered.
2D Arrays
When working with arrays, it is convenient to have a function that sets all
the elements of the array to a fixed value. Implement a function
void initialize(int a[MAX_ROW][MAX_COLUMN], int c = 0).
The function should set all the elements in the array to c.
If c isn't supplied, the default value 0 is used.
Don't forget your PRE/POST comments.
Use bubble_sort to create the function void bubble_sort(int a[MAX_ROW][MAX_COLUMN]).
This function should sort each row of the array. Write a print function to test you function.