Tags
Algorithms, C, Ceedling, Grokking Algorithms, STM32, Unit Testing, Unity
The main focus of this chapter was “Divide and Concur”, starting with an algorithm to sum an array (using recursion), and then going to the quicksort algorithm.
There are a few exercises to use the divide and concur method on already developed algorithms, but I’ll leave these out of this post (thought they are worth going over yourself if you’re reading the book).
Recursive sum function
As a first example of a “divide and concur” algorithm, a recursive sum function is created. Normally, a simple loop would be more than enough for such a simple algorithm. However, being such a simple algorithm makes it a good algorithm to start with.
Unit Testing
As normal, I started creating unit tests in a TDD way, starting with a simple test, and working up to more complicated tests after each test has finished.
The following test units were created, with the sum module code being updated when each new test failed.
void test_when_given_an_empty_list_module_returns_0(void) { int list[] = {1}; int list_size = 0; int return_value = sum(list, list_size); TEST_ASSERT_EQUAL(0, return_value); } void test_when_given_a_list_with_single_item_return_correct_value(void) { int list[] = {1}; int list_size = 1; int return_value = sum(list, list_size); TEST_ASSERT_EQUAL(1, return_value); } void test_testing_larger_list(void) { int list[] = {1, 2, 3, 4, 5}; int list_size = 5; int return_value = sum(list, list_size); TEST_ASSERT_EQUAL(15, return_value); } void test_testing_very_large_list(void) { int list[1000]; int list_size = 1000; int expected_value = 0; for (int i = 0; i < list_size; i++) { list[i] = i; expected_value += i; } int return_value = sum(list, list_size); TEST_ASSERT_EQUAL(expected_value, return_value); }
With the module code below, the all of the tests passed. The module was pretty simple (which is hardly surprising given the simplicity of it).
The module tests for an empty or single element array, returning 0 or the value of the element respectively. If the array has two or more elements, the module adds up the first element in the array and the recursive sum of the rest of the array.
int sum(int list[], int list_size) { if (list_size == 0) { return 0; } if (list_size == 1) { return list[0]; } return (list[0] + sum(&list[1], (list_size-1))); }
The above was tested on an array of 1000 elements and everything worked as expected.
STM32 Test
Things got a bit more interesting when porting the code to the STM32 board. When the array was small, everything worked fine and the function returned the sum of all the elements in the array. In fact, when the array size up to 483 elements everything worked as expected.
However, when the array size went above 483, the function would not return and the program would crash. The board didn’t automatically reset, and no obvious errors came up (well they wouldn’t on an embedded device without extra error checking being added).
Initially, I thought that increasing the size of the head and stack in STM32CubeMX would help fix the problem. However, this didn’t make any difference. The board would crash on any array over 483 elements.
Playing around with optimisations, I found that if I changed the value from Og to O2, I was able to increase the size of the array. Lists over 1000 items in size without any issues. I haven’t looked into this, but I wonder if the optimisation is turning the recursion into a loop, which the module would be able to perform with very little difficulty.
It would be interesting to test this on different STM32 modules to see what the maximum array length I could get without adding the optimisations.
Quicksort
The quicksort algorithm was the main part of the chapter, as well as the part that gave me the most difficulty.
Unit Testing
Writing up this algorithm was a bit more complicated than I expected. There are actually two parts to this, the partition and the recursive quicksort. I unit tested the quicksort module as normal, but did not do any testing on the partition part. Looking back, I should have unit tested the partition part first, as this was the part that caused me quite a few problems.
void test_base_case_1_when_array_is_empty_return_null_pointer(void) { int array[0]; int array_size = 0; int* sorted_array = quicksort(array, array_size); TEST_ASSERT_NULL(sorted_array); } void test_base_case_2_when_array_has_single_element_return_pointer_to_element(void) { int array[1] = {2}; int array_size = 1; int* sorted_array = quicksort(array, array_size); TEST_ASSERT_EQUAL_INT_ARRAY(array, sorted_array, 1); } void test_when_given_a_sorted_array_of_two_elements_the_same_array_is_returned(void) { int array[2] = {1, 2}; int array_size = 2; int* sorted_array = quicksort(array, array_size); TEST_ASSERT_EQUAL_INT_ARRAY(array, sorted_array, 2); } void test_when_given_an_unsorted_array_of_two_elements_the_sorted_array_is_returned(void) { int array[2] = {2, 1}; int expected_array[2] = {1, 2}; int array_size = 2; int* sorted_array = quicksort(array, array_size); TEST_ASSERT_EQUAL_INT_ARRAY(expected_array, sorted_array, 2); } void test_when_given_array_of_3_sorted_items_function_returns_same_array(void) { int array[3] = {1, 2, 3}; int expected_array[3] = {1, 2, 3}; int array_size = 3; int* sorted_array = quicksort(array, array_size); TEST_ASSERT_EQUAL_INT_ARRAY(expected_array, sorted_array, 3); } void test_when_given_array_of_3_unsorted_items_function_returns_sorted_array(void) { int array[3] = {3, 2, 1}; int expected_array[3] = {1, 2, 3}; int array_size = 3; int* sorted_array = quicksort(array, array_size); TEST_ASSERT_EQUAL_INT_ARRAY(expected_array, sorted_array, 3); } void test_testing_array_from_book(void) { int array[4] = {10, 5, 2, 3}; int expected_array[4] = {2, 3, 5, 10}; int array_size = 4; int* sorted_array = quicksort(array, array_size); TEST_ASSERT_EQUAL_INT_ARRAY(expected_array, sorted_array, 4); } void test_testing_larger_array(void) { int array[] = {12,23,3,43,51,35,19,45}; int expected_array[] = {3,12,19,23,35,43,45,51}; int array_size = 8; int* sorted_array = quicksort(array, array_size); TEST_ASSERT_EQUAL_INT_ARRAY(expected_array, sorted_array, array_size); }
All of the tests above worked fine, with the exception of the last one.
The problem was with the partition. Initially, my partition function was simply looping through the elements, checking if it was smaller than the pivot, and then swapping in the two elements. Obviously this was wrong, but it did work on my initial tests (up until the last test actually).
This is why it would have been better if I had unit tested my partition code as a separate function (and probably before even working on the quicksort tests).
In the end I ended up with the following module which did allow all tests to pass.
void swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } int* quicksort(int array[], int array_size) { if (array_size == 0) return 0; if (array_size == 1) return array; int pivot_index = array_size - 1; int pivot = array[pivot_index]; // partition int i = -1; for (int j = 0; j < array_size-1; j++) { if (array[j] < pivot) { i++; swap(&array[i], &array[j]); } } swap(&array[i+1], &array[array_size - 1]); pivot_index = i+1; // sorting both sides of array quicksort(&array[0], pivot_index); quicksort(&array[pivot_index+1], array_size - pivot_index - 1); return array; }
It’s a bit messy, and I’d probably try and clean it up if I was to use it, but all the tests passed, and it works as expected.
STM32 Test
Unlike the sum module above, I had no issues getting the quicksort algorithm to work on my STM32 board. However, I did not include any really long arrays, which might have brought up some interesting problems if I had.
uint8_t buffer[64]; int list[] = {10, 5, 2, 3}; int* sorted_list = quicksort(list, 4); sprintf((char*)buffer, "Sorted list is now: %i %i %i %i\n\r", sorted_list[0],sorted_list[1],sorted_list[2],sorted_list[3]); HAL_UART_Transmit(&huart2, buffer, strlen((const char*)buffer), 1000);
The code above added to the main function (with the swap and quicksort algorithm added as well), gave the following output:
Sorted list is now: 2 3 5 10
So, everything is now working, and I’ll start reading through the next chapter: Hash Tables.