grodtron · July 23, 2012 04:49 · Jul 23, 2012 · Jul 23, 2012 · Jul 23, 2012 · Jul 23, 2012
diff --git a/configure b/configure
@@ -8,26 +8,26 @@ exec > Makefile
 echo "# Auto-Generated file - don't edit!"
 echo "# Created on $(date)"
 
-echo -e "\n"
+echo -e '\n'
 
-echo "cflags=-ggdb -Wall -Wextra -pedantic"
-echo "ldflags="
+echo 'cflags=-ggdb -Wall -Wextra -pedantic'
+echo 'ldflags='
 echo "ofiles=\$(patsubst %.c, %.o, $files)"
-echo "exe=sort"
+echo 'exe=sort'
 
-echo -e "\n"
+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 -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"
+echo '$(exe): $(ofiles)'
+echo -e '\tgcc $(ldflags) $^ -o $@\n'
 
 for file in $files
 do
    gcc -MM $file
-   echo -e "\tgcc \$(cflags) -c \$< -o \$@\n"
+   echo -e '\tgcc $(cflags) -c $< -o $@\n'
 done
diff --git a/configure b/configure
@@ -3,33 +3,31 @@
 # the echo jams everything onto one line
 files=$(echo `ls *.c`)
 
-rm -f Makefile
-touch Makefile
+exec > Makefile
 
+echo "# Auto-Generated file - don't edit!"
+echo "# Created on $(date)"
 
-echo "# Auto-Generated file - don't edit!" >> Makefile
-echo "# Created on $(date)" >> Makefile
+echo -e "\n"
 
-echo -e "\n" >> Makefile
+echo "cflags=-ggdb -Wall -Wextra -pedantic"
+echo "ldflags="
+echo "ofiles=\$(patsubst %.c, %.o, $files)"
+echo "exe=sort"
 
-echo "cflags=-ggdb -Wall -Wextra -pedantic" >> Makefile
-echo "ldflags=" >> Makefile
-echo "ofiles=\$(patsubst %.c, %.o, $files)" >> Makefile
-echo "exe=sort" >> Makefile
+echo -e "\n"
 
-echo -e "\n" >> Makefile
+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 -e ".PHONY: clean all\n\t\n" >> Makefile
-echo -e "all: \$(exe)\n" >> Makefile
-echo    "clean:" >> Makefile
-echo -e "\trm -f \$(exe) \$(ofiles)" >> Makefile
-echo -e "\t./configure\n" >> Makefile
-
-echo "\$(exe): \$(ofiles)" >> Makefile
-echo -e "\tgcc \$(ldflags) $^ -o \$@\n" >> Makefile
+echo "\$(exe): \$(ofiles)"
+echo -e "\tgcc \$(ldflags) $^ -o \$@\n"
 
 for file in $files
 do
-   gcc -MM $file >> Makefile
-   echo -e "\tgcc \$(cflags) -c \$< -o \$@\n" >> Makefile
+   gcc -MM $file
+   echo -e "\tgcc \$(cflags) -c \$< -o \$@\n"
 done
diff --git a/configure b/configure
@@ -12,7 +12,7 @@ echo "# Created on $(date)" >> Makefile
 
 echo -e "\n" >> Makefile
 
-echo "cflags=-ggdb -Wall -Wextra" >> Makefile
+echo "cflags=-ggdb -Wall -Wextra -pedantic" >> Makefile
 echo "ldflags=" >> Makefile
 echo "ofiles=\$(patsubst %.c, %.o, $files)" >> Makefile
 echo "exe=sort" >> Makefile

diff --git a/main.c b/main.c
@@ -9,13 +9,17 @@
 int main()
 {
 
+   const size_t length = 30;
+   int * array1;
+   int * array2;
+   int * array3;
+   size_t i;
+
    srand(time(0));
 
-   size_t length = 30;
-   int * array1 = (int*)malloc(length * sizeof(int));
-   int * array2 = (int*)malloc(length * sizeof(int));
-   int * array3 = (int*)malloc(length * sizeof(int));
-   size_t i;
+   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);

diff --git a/mergesort.c b/mergesort.c
@@ -2,15 +2,19 @@
 #include <stdlib.h>
 
 void mergesort(int * const A, const size_t L){
-   if (L < 2) return;
 
-   const size_t b = (L/2);// + sizeof(int);
-   const size_t c = (L/2) + (L%2);// + sizeof(int);
+   size_t b, c, i, j, k;
+
+   int * B;
+   int * C;
+
+   if (L < 2) return;
 
-   size_t i, j, k;
+   b = (L/2);
+   c = (L/2) + (L%2);
 
-   int * const B = (int*) malloc(b * sizeof(int));
-   int * const C = (int*) malloc(c * sizeof(int));
+   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));

diff --git a/main.c b/main.c
@@ -4,6 +4,7 @@
 
 #include "heapsort.h"
 #include "quicksort.h"
+#include "mergesort.h"
 
 int main()
 {
@@ -13,17 +14,20 @@ int main()
    size_t length = 30;
    int * array1 = (int*)malloc(length * sizeof(int));
    int * array2 = (int*)malloc(length * sizeof(int));
+   int * array3 = (int*)malloc(length * sizeof(int));
    size_t i;
 
    for(i = 0 ; i < length; ++i){
-      printf("%d ", array1[i] = array2[i] = rand()%length);
+      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){
@@ -37,5 +41,11 @@ int main()
    }
    printf("\n");
 
+   puts("Mergesort output:");
+   for(i = 0 ; i < length; ++i){
+      printf("%d ", array3[i]);
+   }
+   printf("\n");
+
    return 0;
 }
diff --git a/mergesort.c b/mergesort.c
@@ -0,0 +1,31 @@
+#include <string.h>
+#include <stdlib.h>
+
+void mergesort(int * const A, const size_t L){
+   if (L < 2) return;
+
+   const size_t b = (L/2);// + sizeof(int);
+   const size_t c = (L/2) + (L%2);// + sizeof(int);
+
+   size_t i, j, k;
+
+   int * const B = (int*) malloc(b * sizeof(int));
+   int * const 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);
+}
+
diff --git a/mergesort.h b/mergesort.h
@@ -0,0 +1,8 @@
+#ifndef MERGESORT_H
+#define MERGESORT_H
+
+#include <stdlib.h>
+
+void mergesort(int * const, const size_t);
+
+#endif
diff --git a/dummy.txt b/dummy.txt
@@ -1 +0,0 @@
-deleteme!

diff --git a/dummy.txt b/dummy.txt
@@ -0,0 +1 @@
+deleteme!
diff --git a/dummy.txt b/dummy.txt
@@ -0,0 +1 @@
+deleteme!
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,4 @@
+*.swp
+*.o
+sort
+Makefile
diff --git a/configure b/configure
@@ -0,0 +1,35 @@
+#!/bin/bash
+
+# the echo jams everything onto one line
+files=$(echo `ls *.c`)
+
+rm -f Makefile
+touch Makefile
+
+
+echo "# Auto-Generated file - don't edit!" >> Makefile
+echo "# Created on $(date)" >> Makefile
+
+echo -e "\n" >> Makefile
+
+echo "cflags=-ggdb -Wall -Wextra" >> Makefile
+echo "ldflags=" >> Makefile
+echo "ofiles=\$(patsubst %.c, %.o, $files)" >> Makefile
+echo "exe=sort" >> Makefile
+
+echo -e "\n" >> Makefile
+
+echo -e ".PHONY: clean all\n\t\n" >> Makefile
+echo -e "all: \$(exe)\n" >> Makefile
+echo    "clean:" >> Makefile
+echo -e "\trm -f \$(exe) \$(ofiles)" >> Makefile
+echo -e "\t./configure\n" >> Makefile
+
+echo "\$(exe): \$(ofiles)" >> Makefile
+echo -e "\tgcc \$(ldflags) $^ -o \$@\n" >> Makefile
+
+for file in $files
+do
+   gcc -MM $file >> Makefile
+   echo -e "\tgcc \$(cflags) -c \$< -o \$@\n" >> Makefile
+done
diff --git a/heapsort.c b/heapsort.c
@@ -0,0 +1,19 @@
+#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;
+      }
+   }
+}
diff --git a/heapsort.h b/heapsort.h
@@ -0,0 +1,8 @@
+#ifndef HEAPSORT_H
+#define HEAPSORT_H
+
+#include <stdlib.h>
+
+void heapsort(int*const, const size_t);
+
+#endif
diff --git a/main.c b/main.c
@@ -0,0 +1,41 @@
+#include <time.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "heapsort.h"
+#include "quicksort.h"
+
+int main()
+{
+
+   srand(time(0));
+
+   size_t length = 30;
+   int * array1 = (int*)malloc(length * sizeof(int));
+   int * array2 = (int*)malloc(length * sizeof(int));
+   size_t i;
+
+   for(i = 0 ; i < length; ++i){
+      printf("%d ", array1[i] = array2[i] = rand()%length);
+   }
+   printf("\n");
+
+   puts("Heapsorting...");
+   heapsort(array1, length);
+   puts("Quicksorting...");
+   quicksort(array2, 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");
+
+   return 0;
+}
diff --git a/quicksort.c b/quicksort.c
@@ -0,0 +1,36 @@
+#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));
+}
diff --git a/quicksort.h b/quicksort.h
@@ -0,0 +1,8 @@
+#ifndef QUICKSORT_H
+#define QUICKSORT_H
+
+#include <stdlib.h>
+
+void quicksort(int * const, const size_t);
+
+#endif
diff --git a/swap.c b/swap.c
@@ -0,0 +1,5 @@
+void swap(int* a, int* b){
+   int c = *a;
+   *a = *b;
+   *b = c;
+}
diff --git a/swap.h b/swap.h
@@ -0,0 +1,6 @@
+#ifndef SWAP_H
+#define SWAP_H
+
+void swap(int*, int*);
+
+#endif