# Bubble sort

You will implement the sorting algorithm *bubble sort*.

:::{wpd} 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.
:::

:::{commons-figure} https://commons.wikimedia.org/wiki/File:Bubble-sort-example-300px.gif
:align: right
:figwidth: 35%
Bubble sort step by step.
:::

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))`{l=c}.

   The function pointer `pair_is_in_order` determines whether the pair has to be swapped or not.
   
1. Define two functions which can be used as `pair_is_in_order`:

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

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

   1. `numbers_ascending`

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

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

   ```c
   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.

1. Your project should contain:

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

     ```c
     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.