sorting algorithms for small arrays

smallsort.c

#include <stdio.h>
#include <sys/types.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <string.h>
#include <sys/time.h>

long long gettime_ms(void)
{
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

void combsort(long long *a, size_t l) {
    size_t j;
    size_t gap = l > 1 ? l / 2 : 1;

    if (l == 0) return;
    while(1) {
        int swapped = 0;

        for (j = 0; j < l-gap; j++) {
          //            printf(".");
            if (a[j] < a[j+gap]) {
                long long aux = a[j];
                a[j] = a[j+gap];
                a[j+gap] = aux;
                swapped = 1;
            }
        }
        if (gap > 1)
            gap = gap * 3 / 4;  /* This is like / 1.333... */
        else if (swapped == 0)
            break;  /* Array is sorted. */
    }
}

void insertionsort(long long* a, size_t n) {
  for (int i = 1; i < n; i++) {
    long long e = a[i];
    int j = i;
    while (--j >= 0 && a[j] > e) {
      a[j+1] = a[j];
    }
    a[j+1] = e;
  }
}

void bubblesort(long long* a, size_t n) {
  for (int j = 1; j < n; j++) {
    for (int i = 0; i < n - 1 - j; i++) {
      if (a[i] > a[i + 1]){
        long long aux = a[i];
        a[i] = a[i + 1];
        a[i + 1] = aux;
      }
    }
  }
}

int main(void) {
    long long offsets[10];
    long long tmp[10];

    srand(time(NULL)^getpid());
    for (int j = 0; j < 10; j++) {
      offsets[j] = rand();
    }

    long long t0 = gettime_ms();
    for (int n = 0; n < 15000000; n++) {
      //      printf("%d\n", sizeof(offsets));
      memcpy(tmp, offsets, sizeof(offsets));

      // pick one below
      //combsort(tmp, 6);
      //insertionsort(tmp, 6);
      bubblesort(tmp, 6);

      //      printf("\n");
      //for (int j = 0; j < 10; j++)
      //  printf("%lld\n", offsets[j]);
    }
    
    printf("%lld\n", gettime_ms() - t0);
    return 0;
}

gcc smallsort.c -std=gnu99 -O3 -o smallsort && ./smallsort

my limited testing gives that for 6 elements, bubblesort is the fastest. for 10 elements, insertionsort is fastest by far (especially with -O3). combsort was never the fastest.

just tested clang 3.2 instead of gcc 4.2 and then insertion sort always wins over bubble and comb sort, 6 or 10 elements.