Bubble Sort

Bubble sort is a relatively simple, inefficient sorting algorithm. By "sort" I mean it takes the contents of an array and arranges them in a particular order. Here, our sorting order will be ascending, meaning the smallest value should be the first element in the array after sorting, and the largest value should be in the last element of the the array after sorting. For instance, we would expect the following:

Before (top row indicates index):

0 1 2 3 4 5 6

------------------------------

| 3 | 1 | 0 | 9 | 11 | 7 | 6 |

------------------------------

After (top row indicates index):

0 1 2 3 4 5 6

------------------------------

| 0 | 1 | 3 | 6 | 7 | 9 | 11 |

------------------------------

Bubble sort "bubbles" elements to their correct position by passing over the array multiple times. The algorithm passes over the array multiple times. Every time two adjacent elements are out of order (i.e. not sorted), it swaps the positions of these two elements. If we repeatedly loop over the array and perform swaps when elements are out of order, we will eventually end up with a sorted array.

The algorithm stops when it is able to pass over the array without changing the position of any values (i.e. no swap of adjacent values occurs, this means the list is sorted. Take a moment to make sure you understand why the array is sorted if no swaps occur).

Here is a visualization of the bubble sort algorithm: https://www.youtube.com/watch?v=Cq7SMsQBEUw

You can see in this video each pass over the array results in a slightly more sorted array than before.

Here is the psuedocode for bubble sort. Your job is to convert this psuedocode to C and then convert all array access operators [] into pointer arithmetic and dereferencing operators. Your solution should not use the array access [] operator.

procedure bubble_sort( list : array of items )

list_size = list.count;

for i = 0 to list_size-1 do:

/* assume we will not swap any elements */

swapped = false

for j = 0 to list_size-1 do:

/* compare the adjacent elements */

if list[j] > list[j+1] then

/* Swap them if they are out of order*/

tmp = list[j];

list[j] = list[j+1];

list[j+1] = tmp;

swapped = true

end if

end for

/*if no number was swapped that means

array is sorted now, break the loop.*/

if(not swapped) then

break

end if

end for

end procedure return list

Grading

You are NOT allowed to modify any code between "START DO NOT MODIFY" and "END DO NOT MODIFY." If you modify anything in this area, you will be given a max score of 75%. The automatic grader will be extremely strict on formatting; your output is expected to exactly match the test cases I have provided to the grader. This assignment will be automatically graded based on how many test cases your program passes. You should test a set of interesting/edge cases for your assignment. For this assignment you:

You may assume arr_len is always properly set.

You must not use the indexing operator []. You must complete the bubble sort algorithm using pointer arithmetic.

You must handle arrays of even and odd length.

You must handle arrays with a single element.

How to run your code

Simply click the run button above the editor, and your program will run in the terminal below the editor.

For this assignment, the input is a test case ID starting at 0 up to XX. Each inputted value corresponds to a specific test case.

Note that there are no debugging tools here, this is primarily for assignment submission. I encourage you to still use XCode/Visual Studio as your primary development environment, and to submit your final submission here. You should still verify your program works correctly in this environment.

Given Code:

// ----------------------------------------------------------------- // START DO NOT MODIFY // -----------------------------------------------------------------

#include

void bubble_sort(int *const a, size_t arr_len); void print_arr(int *const arr, size_t arr_len); void run_test_case(int test_case);

int main() { int test_case; printf("Enter test_case: "); scanf("%d", &test_case); run_test_case(test_case); }

// ----------------------------------------------------------------- // END DO NOT MODIFY // -----------------------------------------------------------------

// this implements "bubble sort", an inefficient but simple sorting algorithm. void bubble_sort(int *const a, size_t arr_len){ // complete implmentation here }

// ----------------------------------------------------------------- // START DO NOT MODIFY // ----------------------------------------------------------------- // helper function to print the contents of an array void print_arr(int *const arr, size_t arr_len) { for (int i = 0; i < arr_len; i++) { printf("%d ", *(arr+i)); } printf(" "); }

// runs test cases void run_test_case(int test_case) { // we use if statements here (instead of a switch) because a switch statement // has a single scope, meaning we can't define different versions of arr for // each case if (test_case == 0) { int arr[] = {3, 4, 5, 6}; size_t arr_len = sizeof(arr) / sizeof(int); printf("Before sorting: "); print_arr(arr, arr_len); bubble_sort(arr, arr_len); printf("After sorting: "); print_arr(arr, arr_len); } else if (test_case == 1) { int arr[] = {-3, 4, 5, 6, -7}; size_t arr_len = sizeof(arr) / sizeof(int); printf("Before sorting: "); print_arr(arr, arr_len); bubble_sort(arr, arr_len); printf("After sorting: "); print_arr(arr, arr_len); } else if (test_case == 2) { int arr[] = {3}; size_t arr_len = sizeof(arr) / sizeof(int); printf("Before sorting: "); print_arr(arr, arr_len); bubble_sort(arr, arr_len); printf("After sorting: "); print_arr(arr, arr_len); }

}

// ----------------------------------------------------------------- // END DO NOT MODIFY // -----------------------------------------------------------------