Bubble sort

You will implement the sorting algorithm bubble sort.

bubble sort

a sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed until no swapping is needed.

The larger elements “bubble” up to the top of the list.

Fig. 20 Bubble sort step by step.
CC BY-SA 3.0. By Swfung8. Source: Wikimedia Commons

Algorithm:

input: array
n = length(array)
repeat
  swapping_occurred = false
  for i = 1 to n - 1 do
    if the pair array[i-1], array[i] is not in order
      swap the pair
      swapping_occurred = true
until not swapping_occurred

Requirements:

1. Implement the function bubble_sort(char arr, bool (pair_is_in_order*)(char a, char b)).

   The function pointer pair_is_in_order determines whether the pair has to be swapped or not.

2. Define two functions which can be used as pair_is_in_order:

   1. letters_in_order that checks if the two given chars are in order without case sensitivity. Assume that you will get a-z and A-Z. Examples

      letters_in_order('a', 'b'); // true
      letters_in_order('a', 'B'), // true
      letters_in_order('b', 'a'); // false
      letters_in_order('a', 'A'), // true
      

   2. numbers_ascending

      numbers_in_ascending_order(1, 2); // true
      numbers_in_ascending_order(1, 1); // true
      numbers_in_ascending_order(1, -1); // false
      

3. Define a function swap that can swap two elements of an array. swap has two arguments. For example:

   char arr[] = {1, 2, 3};
   swap(arr[0], arr[2]);
   // Now is arr = {3, 2, 1}
   

   It is possible to implement bubble_sort without swap, but we need this function for modularity and to swap more complex objects in future.

4. Your project should contain:

   • main.c which tests your function with at least the following arrays:

     char letter_arr1[] = {'z', 'S', 's', 'a'}`
     // aSsz
     char number_arr1[] = {4, -1, 2, 9}
     // -1, 2, 4, 9
     

   • sort.{c,h} which includes your implementation

   • a flowchart of the algorithm. Use as much natural language as possible but visualize at least the two loops.