Sorting

Sorting

I started writing a blog about sorting but got so bogged down with the styling and the way it looked that I never got around to actually publishing it.  I just looked at the information and realised that it should be the content that's important.  The sheer size of the original blog post seems to have overwhelmed me too so I have decided to release smaller sections of the original post minus the styling and colouring at intervals that suit me :)

What is Sorting?

Well this seems like a dumb question doesn't it, I mean sorting obviously means putting a collection of something into some sort of recognised order!

Well yes this is what it means but what I intend to cover in this article is what makes a sort different from another, how can I sort a list of something into a particular order in more than one way, and does it matter?

Algorithms

This is in no way an exhaustive list of the sorting algorithms that are available it's just a list that I threw together.

• bubble sort
• selection sort
• insert sort
• merge sort
• heap sort
• quick

 Exploration

In order to examine and compare different algorithms I have decided to make a simple algorithm caller, also in keeping with my view onto the past I have decided to make the whole lot in C, old school!
So I made a very simple command line thing that you can request a list of items to be sorted using a particular method.  I am sure there are better nicer ways to achieve the desired result I am not a 'C' developer ordinarily and have almost no requirement to use Makefiles on a day to day basis, but this article is about the fundamentals of sorting that just so happens to use 'C' examples and should not be the focus of the reader.

Makefile

 # This is the general makefile for everything I can think of, for once I am
 # keeping the file to 80 characters, just to see if it makes any difference
 # when using such an old technology like C.
 GCC = gcc
 LINK = gcc
 SOURCE = src
SORT_HEADERS = $(SOURCE)/headers
OUTPUT = bin

all : $(OUTPUT)/sorting.o $(OUTPUT)/bubble.o $(OUTPUT)/insert.o \
$(OUTPUT)/selection.o $(OUTPUT)/merge.o $(OUTPUT)/quick.o $(OUTPUT)/heap.o
 $(LINK) --fatal-warnings -o $(OUTPUT)/sorting $(OUTPUT)/sorting.o \
 $(OUTPUT)/bubble.o $(OUTPUT)/insert.o $(OUTPUT)/selection.o \
 $(OUTPUT)/merge.o  $(OUTPUT)/heap.o $(OUTPUT)/quick.o

init:
 if ! [ -d $(OUTPUT) ]; then mkdir $(OUTPUT); fi

$(OUTPUT)/sorting.o : init $(SOURCE)/sorting.c $(SORT_HEADERS)/sorting.h \
$(OUTPUT)/bubble.o $(OUTPUT)/insert.o $(OUTPUT)/selection.o \
$(OUTPUT)/merge.o $(OUTPUT)/heap.o 
 $(GCC) -I$(SORT_HEADERS) -c -o $(OUTPUT)/sorting.o -x c \
 $(SOURCE)/sorting.c

$(OUTPUT)/bubble.o : $(SOURCE)/bubble.c $(SORT_HEADERS)/bubble.h
 $(GCC) -I$(SORT_HEADERS) -c -o $(OUTPUT)/bubble.o -x c \
$(SOURCE)/bubble.c

$(OUTPUT)/insert.o : $(SOURCE)/insert.c $(SORT_HEADERS)/insert.h
 $(GCC) -I$(SORT_HEADERS) -c -o $(OUTPUT)/insert.o -x c \
 $(SOURCE)/insert.c

$(OUTPUT)/selection.o : $(SOURCE)/selection.c $(SORT_HEADERS)/selection.h
 $(GCC) -I$(SORT_HEADERS) -c -o $(OUTPUT)/selection.o -x c \
 $(SOURCE)/selection.c

$(OUTPUT)/merge.o : $(SOURCE)/merge.c $(SORT_HEADERS)/merge.h
 $(GCC) -I$(SORT_HEADERS) -c -o $(OUTPUT)/merge.o -x c \
 $(SOURCE)/merge.c

$(OUTPUT)/heap.o : $(SOURCE)/heap.c $(SORT_HEADERS)/heap.h
 $(GCC) -I$(SORT_HEADERS) -c -o $(OUTPUT)/heap.o -x c \
 $(SOURCE)/heap.c

$(OUTPUT)/quick.o : $(SOURCE)/quick.c $(SORT_HEADERS)/quick.h
 $(GCC) -I$(SORT_HEADERS) -c -o $(OUTPUT)/quick.o -x c \
 $(SOURCE)/quick.c

clean : clean-sorting

clean-sorting : clean-sorting-o clean-bubble-o clean-insert-o \
clean-selection-o clean-merge-o clean-heap-o clean-quick-o 
 @if [ -e $(OUTPUT)/sorting ]; then rm -f $(OUTPUT)/sorting ; \
 echo "clean sorting"; fi

clean-sorting-o :
 @if [ -e $(OUTPUT)/sorting.o ]; then rm -f $(OUTPUT)/sorting.o; \
 echo "clean sorting.o"; fi

clean-bubble-o :
 @if [ -e $(OUTPUT)/bubble.o ]; then rm -f $(OUTPUT)/bubble.o; \
 echo "clean bubble.o"; fi

clean-insert-o :
 @if [ -e $(OUTPUT)/insert.o ]; then rm -f $(OUTPUT)/insert.o; \
 echo "clean insert.o"; fi

clean-selection-o :
 @if [ -e $(OUTPUT)/selection.o ]; then rm -f $(OUTPUT)/selection.o; \
 echo "clean selection.o"; fi
 
clean-merge-o :
 @if [ -e $(OUTPUT)/merge.o ]; then rm -f $(OUTPUT)/merge.o; \
 echo "clean merge.o"; fi

clean-heap-o :
 @if [ -e $(OUTPUT)/heap.o ]; then rm -f $(OUTPUT)/heap.o; \
 echo "clean heap.o"; fi

clean-quick-o :
 @if [ -e $(OUTPUT)/quick.o ]; then rm -f $(OUTPUT)/quick.o; \
 echo "clean quick.o"; fi

src/headers/sorting.h

#ifndef SORTING
#define SORTING
#include <stdio.h>
#include <bubble.h>
#include <insert.h>
#include <selection.h>
#include <merge.h>
#include <heap.h>
#include <string.h>

//declare a few constants
const char* usagemsg;
struct SortMethod {
  char* name;
  char** (*func)(unsigned int, char**);
};

int main(int, char* []);
struct SortMethod* findMatch(const char*);

void sprintList(const unsigned int size, const char** values);

#endif

src/sorting.c

#include <sorting.h>
// create some constants
const char* usagemsg = "Usage:\n\t\
                        sorting  item1 item2 ... item N \
                        \n\tfor example sorting bubble my name is earl\n";

struct SortMethod s[] = {
  {"bubble\0", &bsort}, {"insert\0", &isort}, {"selection\0", &ssort},
  {"merge\0", &msort}, {"heap\0", &hsort}
};

int main(int argc, char* argv[]) {
  int i;
  if (argc < 2) {
    printf("%s\navailable algorithms:\n", usagemsg);
    for(i = 0; i < sizeof(s) / sizeof(s[0]); i++) {
      printf("\t%s\n", s[i].name);
    }
    printf("* note the default is %s\n", s[0].name);
  } else {
    printf("\n");
    sprintList(argc - 2, (const char**) findMatch(argv[1])->func(
        (unsigned int)argc - 2, (char**)&argv[2])
      );
  }
  return 0;
}

void sprintList(const unsigned int size, const char** values) {
  unsigned int i;
  printf("\n");
  for(i = 0; i < size; i++) {
    printf("%s\n", values[i]);
  }
}

struct SortMethod* findMatch(const char* name) {
  int i;
  struct SortMethod* result = &s[0];
  for(i = 0; i < sizeof(s) / sizeof(s[0]); i++) {
    if(!strcmp(name, s[i].name)) {
      printf("method: %i -> %s\n", i, s[i].name);
      result = &s[i];
    }
  }
  return result;
}

Test it out

So to give it a whirl try make which should compile all the files then try bin/sorting and you should get:
Usage:
    sorting <algorithm> item1 item2 ... item N
    for example sorting bubble my name is earl

available algorithms:
    bubble
    insert
    selection
    merge
    heap
* note the default is bubble

Done

So that's it, the foundation is laid so the next post and subsequent ones will be about different sorting algorithms and they will be triggered via this simple framework.