Google Whack

“If you like LISP you’re a parenthaefile”

Heap Sort

src/headers/heap.h

#include <selection.h>
#ifndef HEAPSORT
#define HEAPSORT
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

char** hsort(unsigned int, char**);
void heapify(int, unsigned int, char**);
void prnTree(unsigned int, char**);

#endif

src/heap.c

#include <heap.h>
/**
 * This is an example of the heap sort.
 * one thing I never realised in the past is that it's more or less a glorified
 * bubble it just limits the number of bubble comparisons to log2(n) so very
 * quick.  It does have the advantage of in place sorting.
 * 
 */
char** hsort(const unsigned int count, char** values) {
 unsigned int i;
 char* tmp;
 while(count>0) {
  heapify(0, count, values); 
  tmp = values[--count];
  values[count] = values[0];
  values[0] = tmp;
 }
 return values;
}

void heapify(int index, unsigned int size, char** values) {
 char* tmp;
 unsigned int count, child = 2*index + 1;
 prnTree(size, values);
 for(count=0;child<size && count<2;child++) {
  count++;
  if(child<size) {
   heapify(child, size, values);
   if(strcmp(values[child], values[index])>0) {
    tmp=values[index];
    values[index]=values[child];
    values[child]=tmp;
   }
  }
 } 
}

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

Selection Sort

src/headers/selection.h

#ifndef SELECTIONSORT
#define SELECTIONSORT

#include <strings.h>
#include <stdio.h>

char** ssort(const unsigned int count, char** values);

unsigned int findSmallest(const unsigned int items, char** values);

char** swapValues(const unsigned int from, 
                  const unsigned int to,
                  char** values);

void printList(const unsigned int idx, 
               const unsigned int count, 
               char** values);
#endif

src/selection.c

#include <selection.h>
/*
 * This method will sort the list of items that it is given using the simple
 * selection sort, very similar to the insert sort except it will 'select'
 * the highest value rather than insert the value where it best fits.
 */
char** ssort(const unsigned int count, char** values) {
  unsigned int i, j;
  printf("sorting a list of %i values", count);
  for(i = 0; i < count - 1; i++) {
    printList(i, count, values);
    swapValues(findSmallest(count - i, &values[i]), 0, &values[i]);
  }
  printf("\nsorting %i items required %i selects", count, count - 1);
  return values;
}

void printList(const unsigned int idx, const unsigned int count, 
        char** values) {
  unsigned int j;
  printf("\n%i:\tcurrent list: ", idx);
  for(j = 0; j < count - 1; j++) {
    printf("%s, ", values[j]);
  }
  printf("%s", values[j]);
}

unsigned int findSmallest(const unsigned int items, char** values) {
  char* tmp;
  unsigned int i, chosen = 0;
  for(i = 0; i < items; i++) {
    if(strcmp(values[chosen], values[i]) > 0) {
      chosen = i;
    }
  }
  printf(" : smallest value %s, %i comparisons", values[chosen], items);
  return chosen;
}

char** swapValues(const unsigned int from, const unsigned int to, 
        char** values) {
  char* tmp = values[to];
  values[to] = values[from];
  values[from] = tmp;
  return values;
}

Bubble Sort

Simple place holder for the code before I write asymptotic order e.t.c.
src/headers/bubble.h

#ifndef BUBBLE
#define BUBBLE

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

char** bsort(unsigned int, char**);
void swap(const char** values, const unsigned int idx);
#endif

src/bubble.c

#include <bubble.h>

/*
 * This method will sort the list of items that it is given using the simple
 * yet slow Bubble sort algorithm.
 */
char** bsort(const unsigned int count, char** values) {
  unsigned int i, j, moveCount = 0, swapCount = 0;
  char* tmp;
  printf("sorting a list of %i values\n", count);
  for(j=count; j > 0; j--) {
    for(i = 0; i < j - 1; i++) {
      printf("\n%i:\tcomparing %s to %s ", moveCount++, values[i], values[i+1]);
      if(strcmp(values[i], values[i + 1]) > 0) {
        swap((const char**) values, (const unsigned int) i);
        ++swapCount;
      }
    }
  }
  printf("\nsorting %i items required %i swaps",
    count, swapCount);
  return values;
}

/**
 * Swap the string at values[idx] with values[idx+1]
 */
void swap(const char** values, const unsigned int idx) {
  const char* tmp = (const char*)values[idx];
  values[idx] = values[idx + 1];
  values[idx + 1] = tmp;
  printf("swap made");
}

try

1. make
2. bin/sorting bubble 9 8 7 6 5 4 3 2 1 0

the output should look like

method: 0 -> bubble
sorting a list of 10 values

0: comparing 9 to 8 swap made
1: comparing 9 to 7 swap made
2: comparing 9 to 6 swap made
3: comparing 9 to 5 swap made
4: comparing 9 to 4 swap made
5: comparing 9 to 3 swap made
6: comparing 9 to 2 swap made
7: comparing 9 to 1 swap made
8: comparing 9 to 0 swap made
9: comparing 8 to 7 swap made
10: comparing 8 to 6 swap made
11: comparing 8 to 5 swap made
12: comparing 8 to 4 swap made
13: comparing 8 to 3 swap made
14: comparing 8 to 2 swap made
15: comparing 8 to 1 swap made
16: comparing 8 to 0 swap made
17: comparing 7 to 6 swap made
18: comparing 7 to 5 swap made
19: comparing 7 to 4 swap made
20: comparing 7 to 3 swap made
21: comparing 7 to 2 swap made
22: comparing 7 to 1 swap made
23: comparing 7 to 0 swap made
24: comparing 6 to 5 swap made
25: comparing 6 to 4 swap made
26: comparing 6 to 3 swap made
27: comparing 6 to 2 swap made
28: comparing 6 to 1 swap made
29: comparing 6 to 0 swap made
30: comparing 5 to 4 swap made
31: comparing 5 to 3 swap made
32: comparing 5 to 2 swap made
33: comparing 5 to 1 swap made
34: comparing 5 to 0 swap made
35: comparing 4 to 3 swap made
36: comparing 4 to 2 swap made
37: comparing 4 to 1 swap made
38: comparing 4 to 0 swap made
39: comparing 3 to 2 swap made
40: comparing 3 to 1 swap made
41: comparing 3 to 0 swap made
42: comparing 2 to 1 swap made
43: comparing 2 to 0 swap made
44: comparing 1 to 0 swap made
sorting 10 items required 45 swaps
0
1
2
3
4
5
6
7
8
9

As you can see straight away it does take a lot of swapping to sort a relatively simple list