# Bubble sort (C)

### From LiteratePrograms

## A somewhat generic implementation

The support for functional programming is not very elaborated in C. However you can have function pointers and this come in very handy, especially for sorting algorithms.

I have mimiced the interface of the standard function qsort. So it looks like this:

<<bubble_sort function>>=/* mimics the qsort interface */voidbubble_sort(void*base, size_t nmemb, size_t size,int(*compar)(constvoid*,constvoid*)){inti, j;char*pc = base;char*pc_at_i;char*pc_at_j;for(i = nmemb -1; i > 0; --i){for(j = 0; j < i; ++j){/* we have to calculate the offsets, by defintion the size of char is 1 in C, so we do not have to include the size of the elements while doing this address calculations */ pc_at_i = pc + (i * size); pc_at_j = pc + (j * size);if(compar (pc_at_i, pc_at_j) < 0){swap_fun(base, size, i, j);}}}}

I used two extra functions for comparison and swapping of elements. The swapping of elements was borrowed from the [[C++|Quicksort]] page and looks like this:

<<swap_fun function>>=/* Swapping of elements in an array. Because there is a void* we need to give this function the element_size of the to be sorted elements, we then can exchange the array elements character by character. */staticvoidswap_fun (void*base, size_t element_size,intindex1,intindex2){char*pc = base;chartmp;inti;for(i = 0; i < element_size; ++i){tmp = pc[index1 * element_size + i]; pc[index1 * element_size + i] = pc[index2*element_size + i]; pc[index2 * element_size + i] = tmp;}}

I just commented it a bit, because it's not fully clear to a C-outsider why one has to fall back to some character-wise operations.

Now the thing left is the comparison function. Here's the implementation:

<<int_cmp_fun function>>=intint_cmp_fun (constvoid* v1,constvoid* v2){constint* i1 = v1;constint* i2 = v2;intresult;if(*i1 == *i2){result = 0;}elseif(*i1 < *i2){result = -1;}else{result = 1;}returnresult;}

We can use the functions as follows

## Bubble-sort in action

Here a simple example for this sorting function:

<<bubble_sort.c>>=#include <stdio.h>swap_fun function bubble_sort function int_cmp_fun functionstaticvoidprint_int_arr(int*arr, size_t size_of_arr){inti;for(i = 0; i < size_of_arr; i++){printf("%d ", arr[i]);}putchar('\n');}intmain(void){enum{T_SIZE = 7};intarr[T_SIZE] ={-1, 2, 1, 3, 5, -10, -11}; printf("array before sorting: "); print_int_arr(arr, T_SIZE); printf("array after bubblesort: "); bubble_sort(arr, T_SIZE,sizeof(int), int_cmp_fun); print_int_arr(arr, T_SIZE);return0;}

We get the following output:

./a.out array before sorting: -1 2 1 3 5 -10 -11 array after bubblesort: -11 -10 -1 1 2 3 5

So if you are using C, consider using function pointers, the are a really helpful utility.