Bubble Sort in C

Question

I am trying to learn C coming from Python. Below is an implementation of bubble sort, slightly optimized. Any advice on best practices, readability, use of macros, and edge cases would be greatly appreciated.

// Int Bubble sort slightly optimized
// USAGE: ./bubble_sort 7 3 5 4 0 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LEN(a) (sizeof(a) / sizeof(a[0]))

void swap(int *x, int *y)
{
  int temp = *x;
  *x = *y;
  *y = temp;
}

void print_list(int target[], size_t len) {

  int i;
  for(i = 0; i < len; i++) {
      printf("%d\n", target[i]);
  }
}

int *one_pass(int nums[], size_t len, int num_sorted)
{
  // makes one pass of bubble sort up to index
  // barrier determined by "num_sorted" variable
  int *current = nums;
  int *pivot = nums + 1;
  int i = 0;

  for(i = 0; i < (len-1) - num_sorted; i++) {
      if (*current > *pivot) {
          swap(current, pivot);
      }
      current++;
      pivot++;
  }

  return nums;
}


int *bubble_sort(int nums[], size_t len)
{
  // uses one_pass fxn to sort a list
  // smallest to largest using bubble sort alg
  int num_sorted = 0; // assume right most 0 are sorted

  for(num_sorted = 0; num_sorted < len; num_sorted++) {
      nums = one_pass(nums, len,  num_sorted);
  }

  return nums;
}

int main(int argc, char *argv[])
{
  if(argc < 2) {
      printf("USAGE: bubble_sort 7 3 5 4 0 1\n");
      return 1;
  }

  int len = argc - 1;
  int i = 0;
  char **inputs = argv + 1;

  int *nums = malloc(len + sizeof(int));

  for(i = 0; i < len; i++) {
      nums[i] = atoi(inputs[i]);
  }

  nums = bubble_sort(nums, len);
  print_list(nums, len);

  return 0;
}

Answer 1

LEN() Function-like macro to return array length

This is a very common practice in C and C++. I recommend not doing this, because, as written, LEN() only returns the correct value when called with a statically-defined array in the same scope it was defined in. Thus, its usefulness is a bit limited, and in my opinion, overshadowed by the the fact that it will likely silently return an incorrect value if it used on a pointer. For more discussion, as well as some suggested alternative definitions for the macro, see the follow Stack Overflow questions:

• Common array length macro for C?
• Is there a standard function in C that would return the length of an array?
• Array-size macro that rejects pointers

Of course, your code never actually uses LEN(), so there is no problem here. This suggestion is just to make you aware of the issue.

Locality of reference / Define loop variables in loop initialization

Since C99 was standardized, it has been legal to declare variables anywhere in a block, rather than at the top of the block. Declaring variables close to where they are used is part of the concept of "locality of reference".

One example of locality of reference is defining loop iterator variables inside the loop initialzation:

for (int i = 0; i < len - 1 - num_sorted; i++) {
    ...
}

This makes it clear that the variable i exists solely for the purpose of iterating through the loop. It doesn't have life outside the scope of the loop, and any attempt to reference it outside the loop will cause the compiler to emit an error.

Whitespace around C keywords

for, if, while are not functions. By "nuzzling" them up to the parentheses that follow them, it looks like a function call. Separate the words from the parenthetical expressions that follow them:

• Do: if (argc < 2) {
• Don't: if(argc < 2) {

Use argv[0] instead of hard-coding program name into error/help messages

When you check if the user has passed in enough parameters on the command line,

if(argc < 2) {
    printf("USAGE: bubble_sort 7 3 5 4 0 1\n");
    return 1;
}

Use argv[0] instead of hard-coding the program name when you print the error message. Also, consider printing error messages to stderr instead of the default stdout by using fprintf() ("formatted print to file descriptor"). fprintf() and stderr is defined in <stdio.h>, which you are already including, so the idiomatic program usage error message would be:

fprintf(stderr, "USAGE: %s 7 3 5 4 0 1\n", argv[0]);

Bug: Memory allocation / buffer overflow

You dynamically allocate memory for the integers passed on the command line (where len is the number of integers given by the user):

int *nums = malloc(len + sizeof(int));

There is a bug here. If the user gives, say, 10 numbers on the command line, then malloc will allocate 10 + 4 = 14 bytes for your array (assuming sizeof (int) is 4). You needed 40 bytes to store the 10 numbers. When you go to convert the numbers to int and store them in the memory pointed to by nums, you would walk off the end of the memory — a classic buffer overflow.

Solution: change the + operator to *:

int *nums = malloc(len * sizeof(int));

Bug: Memory leak (apparent)

Coming from Python, memory management in C is tricky. Once you allocate memory, never lose a pointer to that allocated memory. If you lose track of a pointer returned by malloc(), then you effectively have a memory leak — that memory can never be returned to the heap (within the scope of your program), because you can't tell free() the address of the memory region you are freeing up.

The problem you have is in main():

nums = bubble_sort(nums, len);

After nums was assigned the memory address returned by malloc(), you then potentially let nums point to something else. Don't do that. Now, as it turns out, you don't actually have a memory leak. But it's really hard to tell. Even looking at the definition of bubble_sort(), it's not apparent that there is no leak.

Really, there is no need for bubble_sort() to return a value. Or even if it does, do not assign its return value to nums. Better to just call it as such:

bubble_sort(nums, len);