Semi-golfed sorting algorithms

.gitignore

*.swp
*.o
sort
Makefile

configure

#!/bin/bash

# the echo jams everything onto one line
files=$(echo `ls *.c`)

exec > Makefile

echo "# Auto-Generated file - don't edit!"
echo "# Created on $(date)"

echo -e '\n'

echo 'cflags=-ggdb -Wall -Wextra -pedantic'
echo 'ldflags='
echo "ofiles=\$(patsubst %.c, %.o, $files)"
echo 'exe=sort'

echo -e '\n'

echo -e '.PHONY: clean all\n\t\n'
echo -e 'all: $(exe)\n'
echo    'clean:'
echo -e '\trm -f $(exe) $(ofiles)'
echo -e '\t./configure\n'

echo '$(exe): $(ofiles)'
echo -e '\tgcc $(ldflags) $^ -o $@\n'

for file in $files
do
   gcc -MM $file
   echo -e '\tgcc $(cflags) -c $< -o $@\n'
done

heapsort.c

#include <stdlib.h>
#include "swap.h"

void heapsort(int * const A, const size_t L){
   size_t i, j;
   int * B;
   for (i = 0; i < L; ++i)
      for (j = i/2; i; i /= 2, j = i/2)
         if (A[i] > A[j]) swap(A + i, A + j);
         else break;
   for (B = A + L - 1; A != B; --B){
      swap(A, B);
      for (i = 0, j = 1; A + j < B; j = (2*i) + 1){
         if (A + j + 1 < B) j = A[j] > A[j+1] ? j : j+1;
         if (A[i] < A[j]) swap(A + i, A + j), i = j;
         else break;
      }
   }
}

heapsort.h

#ifndef HEAPSORT_H
#define HEAPSORT_H

#include <stdlib.h>

void heapsort(int*const, const size_t);

#endif

main.c

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

#include "heapsort.h"
#include "quicksort.h"
#include "mergesort.h"

int main()
{

   const size_t length = 30;
   int * array1;
   int * array2;
   int * array3;
   size_t i;

   srand(time(0));

   array1 = (int*)malloc(length * sizeof(int));
   array2 = (int*)malloc(length * sizeof(int));
   array3 = (int*)malloc(length * sizeof(int));

   for(i = 0 ; i < length; ++i){
      printf("%d ", array1[i] = array2[i] = array3[i] = rand()%length);
   }
   printf("\n");

   puts("Heapsorting...");
   heapsort(array1, length);
   puts("Quicksorting...");
   quicksort(array2, length);
   puts("Mergesorting...");
   mergesort(array3, length);

   puts("Heapsort output:");
   for(i = 0 ; i < length; ++i){
      printf("%d ", array1[i]);
   }
   printf("\n");

   puts("Quicksort output:");
   for(i = 0 ; i < length; ++i){
      printf("%d ", array2[i]);
   }
   printf("\n");

   puts("Mergesort output:");
   for(i = 0 ; i < length; ++i){
      printf("%d ", array3[i]);
   }
   printf("\n");

   return 0;
}

mergesort.c

#include <string.h>
#include <stdlib.h>

void mergesort(int * const A, const size_t L){

   size_t b, c, i, j, k;

   int * B;
   int * C;

   if (L < 2) return;

   b = (L/2);
   c = (L/2) + (L%2);

   B = (int*) malloc(b * sizeof(int));
   C = (int*) malloc(c * sizeof(int));

   memcpy(B, A, b * sizeof(int));
   memcpy(C, A + b, c * sizeof(int));

   mergesort(B, b);
   mergesort(C, c);

   for(i=j=k=0; j<b && k<c; A[i++] = C[k]<B[j] ? C[k++] : B[j++]);

   if(j < b)
      memcpy(A + i, B + j, (L - i) * sizeof(int));
   else
      memcpy(A + i, C + k, (L - i) * sizeof(int));

   free(B);
   free(C);
}

mergesort.h

#ifndef MERGESORT_H
#define MERGESORT_H

#include <stdlib.h>

void mergesort(int * const, const size_t);

#endif

quicksort.c

#include <stdlib.h>
#include "swap.h"

void quicksort(int * const A, const size_t Ln){
   int * R = A + Ln - 1;
   int * L = A;
   int Ld = 1;
   int Rd = 1;
   int P = *(A + (Ln/2));
   if (Ln < 2) return;
   while(1){
      while(*R >= P){
         if(*R > P) --R;
         else{
            while(*(R - Rd) == P && (R - Rd) > L) ++Rd;
            if((R - Rd) > L) swap(R, R - Rd);
            else break;
         }
      }
      while(*L <= P){
         if(*L < P) ++L;
         else{
            while(*(L + Ld) == P && (L + Ld) < R) ++Ld;
            if((L + Ld) < R) swap(L, L + Ld);
            else break;
         }
      }
      if(*L > P || *R < P){
         swap(L, R);
      }else{
         break;
      }
   }
   quicksort(A, (size_t) (L - A));
   quicksort(R + 1, (size_t) Ln - (R + 1 - A));
}

quicksort.h

#ifndef QUICKSORT_H
#define QUICKSORT_H

#include <stdlib.h>

void quicksort(int * const, const size_t);

#endif

swap.c

void swap(int* a, int* b){
   int c = *a;
   *a = *b;
   *b = c;
}

swap.h

#ifndef SWAP_H
#define SWAP_H

void swap(int*, int*);

#endif