Bubble Sort in C: Array vs Linked List

A few weeks ago I posted a code review of a linked list so I decided to implement bubble sort on my journey of learning C. Here is the referenced linked list library, though this isn't really what's being reviewed (feel free if you'd like!).

Linked lists seem inefficient for bubble sort as deletes and gets both have to walk the list. So it's probably something like $O\left( n^{3} \right)$?

I implemented it with arrays too, which is faster because the swapping can be done in place.

LinkedList.h

LinkedList.c

BubbleSort.c:

#include "../linked_list/ll.h"

assert(list);
int sorted = 1;
for (int x = 0; x < list->size; x++) {
/* don't do it if this is the last value */
if (x + 1 == list->size) {
continue;
}
int second = linked_list_get(list, x + 1);
if (first > second) {
sorted = 0;
/* {1, 7, 3}, 1 -> {1, 3} */
/* {1, 3}, 7, 1 -> {1, 3, 7} */
}
}
/* do it again if it's not fully sorted */
if (!sorted) {
}
}

void sort_array(int *array, int size) {
assert(size >= 0);
int sorted = 1;
for (int x = 0; x < size; x++) {
/* don't do it if this is the last value */
if (x + 1 == size) {
break;
}
int *first = array + x;
/* get int address after that one */
int *second = first + 1;
if (*first > *second) {
/* we did some sorting so not sorted */
sorted = 0;
int temp = *first;
int temp2 = *second;
/* swap values */
*first = temp2;
*second = temp;
}
}
/* do it again if it's not fully sorted */
if (sorted == 0) {
sort_array(array, size);
}
}

void print_array(int *array, int size) {
printf("{ ");
for (int x = 0; x < size; x++) {
printf("%d ", *array);
array++;
}
printf("}\n");
}

int main() {
int a[5] = {7, 5, 3, 8, 1};
print_array(a, 5);
sort_array(a, 5);
print_array(a, 5);
return 0;
}


Makefile:

    all: ../linked_list/ll.h bubble.c
gcc -std=c99 -Wall -o bubble bubble.c ../linked_list/ll.c
./bubble


As you can see, linked_list is in another directory. Is this the correct way to include this in my project? I don't fully understand Makefiles quite yet.

Also, any general style tips for my bubble sort would be appreciated. I use pointer arithmetic with my arrays because it helps me understand what's really going on (which is why I'm learning C) but let me know if that's messy. I'd just like to keep learning how to write good C code.

-
If you want your other code reviewed, you need to post it here, not a link to it. –  syb0rg Apr 6 at 4:16
don't need it reviewed, just posting it here because it's referenced in this code! –  dysruption Apr 6 at 4:17

Things you did well

• You initialize your variables when you declared them.

• You initialize variables inside of your for loops.(C99)

• Your pointer arithmetic looks pretty sound.

Things you can improve

Efficiency/Algorithm

• Unfortunately, bubble sort is not a very good sorting algorithm if you are looking for speed. Its average case performance is $O\left(n^{2}\right)$.

• If you are looking into greater speed with your sorting function, look at a quicksort algorithm. Its average case performance is $O\left( n \log n \right)$.

User experience

• Is shutting down the program really necessary when your linked list doesn't actually exist, or that the size of your array is less than one? Do something more useful than assert(), and return a specific error code that you can handle later on in your code. This will greatly help you in debugging too.

Makefile

• Makefile variables - Right now your Makefile isn't very expandable. Variables help out a lot with that.

• Put your compiler names into variables.

CXX = g++
CC = gcc


This is something I like to do, however, some variables like CC are declared already, so you generally don't need to.

• Put your final executable into a variable name.

EXECUTABLE = bubble

• Put your sources into a variable name.

SOURCES = bubble.c

• Put your objects into a variable name.

OBJECTS = $(SOURCES:.c=.o) .c.o:$(CC) $(CFLAGS) -o$@ $<  • All of your compiler flags should be in one variable. And tack on a linker flag variable while we are at it, for futures sake. CFLAGS = -std=c99 -Wall LDFLAGS =  • Calling the variables is now a lot more easy and flexible. all:$(EXECUTABLE)

$(EXECUTABLE):$(OBJECTS)
$(CC)$(LDFLAGS) -o $@$<

• Compiler flags - get the most out of your compiler so that you can code better.

• You should change the standards you are using to C11 with --std=c11

• -g adds symbols for debugging. Without it, your debugger won't be able to give you variable or function names. The don't slow down the program, and we don't care if the program is a kilobyte larger, so there's little reason to not use this.

• -O3 indicated optimization level three, which tries every trick known to build faster code. If, when you run the debugger, you find that too many variables have been optimized out for you to follow what's going on, then change this to -O0.

If you want to go above and beyond, here are all of the compiler flags I use.

CFLAGS = -std=gnu11 -c -s -O3 -Werror -Wall -Wextra -Wformat=2 -Winit-self -Wswitch-enum -Wstrict-aliasing=2 -Wundef -Wshadow -Wpointer-arith -Wbad-function-cast -Wcast-qual -Wcast-align -Wwrite-strings -Wstrict-prototypes -Wold-style-definition -Wmissing-prototypes -Wmissing-declarations -Wredundant-decls -Wnested-externs -Winline -Wdisabled-optimization -Wunused-macros -Wno-unused


Standards

• You don't have to return 0 at the end of main(), just like you wouldn't bother putting return; at the end of a void-returning function. The C standard knows how frequently this is used, and lets you not bother.

C99 & C11 §5.1.2.2(3)

...reaching the } that terminates the main() function returns a value of 0.

Syntax/Styling

• Use Yoda conditions to prevent future bugs.

if (0 == sorted)


Placing the constant value in the expression does not change the behavior of the program. A common mistake is to accidentally assign a value instead of writing a conditional statement. Using Yoda conditions will throw a syntax error if you accidentally do that, so your code won't compile.

• You should return some status indicators from your sorting functions, so we can check that the sorting went okay. This also makes for easier debugging.

• You can simplify some of your test conditionals

if (sorted == 0)


That is actually harder for me to understand over my version.

if (!sorted)


If I were to read my version out loud, it would read "if not sorted", whereas your version is "if sorted is equal to 0". It's odd, since you have this in one place, but not the other (always be consistent).

• Declare your method parameters as void if you don't take any arguments in.

int main(void)

-
Awesome. very helpful stuff. (and I know bubble sort is inefficient, I'm just going through basic data structures / algorithms in C to get used to it). Thanks! –  dysruption Apr 6 at 5:20