Initial commit

1 files changed, 180 insertions, 0 deletions

diff --git a/sorts.c b/sorts.c
new file mode 100644
index 0000000..5dd49a2
--- /dev/null
+++ b/sorts.c
@@ -0,0 +1,180 @@
+/* sorts.c
+ *
+ *
+ * notes: implement simple hash table, use k&r book
+ * 
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <memory.h>
+#include <string.h>
+#include <time.h>
+#include <assert.h>
+#define ARR_SIZE 10
+
+/* function prototypes */
+void insrt_sort(int *, int);
+void select_sort(int *, int);
+void bubble_sort(int *, int);
+void prnt_arr(int *, int);
+int *mk_rand_arr(int, int);
+void mergesort(int *, int, int);
+void merge(int *, int, int, int);
+
+/* merge sort, divide and conquer */
+void mergesort(int a[], int low, int high)
+{
+    int mid;
+
+    if (low < high)
+    {
+        mid = (low + high) / 2;
+        mergesort(a, low, mid);
+        mergesort(a, mid + 1, high);
+        merge(a, low, high, mid);
+    }
+}
+
+/* http://en.allexperts.com/q/C-1587/Merge-Sort-C.htm */
+void merge(int a[], int low, int high, int mid)
+{
+    int i, j, k, c[50];
+    i = low;
+    j = mid + 1;
+    k = low;
+
+    while ( (i <= mid) && (j <= high) )
+    {
+        if (a[i] < a[j])
+        {
+            c[k] = a[i];
+            k++;
+            i++;
+        }
+        else
+        {
+            c[k] = a[j];
+            k++;
+            j++;
+        }
+    }
+
+    while (i <= mid)
+    {
+        c[k] = a[i];
+        k++;
+        i++;
+    }
+
+    while (j <= high)
+    {
+        c[k] = a[j];
+        k++;
+        j++;
+    }
+
+    for (i = low; i < k; i++)
+        a[i] = c[i];
+}
+
+/* in every iteration an element is compared with all the elements before it */
+void insrt_sort(int *arr, int elem)
+{
+    int i, j, tmp;
+    for (i = 1; i < elem; i++)
+    {
+        tmp = arr[i];
+        j = i - 1;
+        /* tmp is compared to all elements that were already inserted and are in order */
+        while ( (j >= 0) && (tmp < arr[j]) )
+        {
+            arr[j+1] = arr[j];
+            j--;
+        }
+        arr[j+1] = tmp;
+    }  
+}
+
+/* slow on nearly sorted array */
+void select_sort(int *arr, int elem)
+{
+    int i, j, tmp;
+
+    for (i = 0; i < elem - 1; i++)
+        for (j = i + 1; j < elem; j++)
+            if (arr[i] > arr[j])
+            {
+                tmp = arr[i];
+                arr[i] = arr[j];
+                arr[j] = tmp;
+            }
+}
+
+/* pretty fast on nearly sorted array with extra code */
+void bubble_sort(int *arr, int elem)
+{
+    int i, j, tmp;
+    
+    for (i = 0; i < elem; i++)
+        for (j = 0; j < elem - i - 1; j++)
+        {
+            if (arr[j] > arr[j+1])
+            {
+                tmp = arr[j];
+                arr[j] = arr[j+1];
+                arr[j+1] = tmp;
+            }
+        }
+}
+
+void prnt_arr(int *arr, int elem)
+{
+    if (arr == NULL)
+        fputs("nothing to print", stderr);
+
+    int i;
+    for (i = 0; i < elem; i++)
+    {
+        printf("%d ", *(arr + i) );
+        if ( (i % 10 == 0) && i != 0)
+            printf("\n");
+    }
+    printf("\n");
+}
+
+int *mk_rand_arr(int elem, int range)
+{
+    assert(elem > 0);
+
+    int *arr = (int *) malloc(sizeof(int) * elem);
+    if (arr == NULL)
+    {
+        perror("malloc");
+        exit(-1);
+    }
+
+    int i;
+    range++;
+    for (i = 0; i < elem; i++)
+        arr[i] = rand() % range;
+
+    return arr;
+}
+
+
+int main(int argc, char **argv)
+{
+    srand( (unsigned int )time(NULL) );
+
+    int *arr = mk_rand_arr(ARR_SIZE, 10);
+    prnt_arr(arr, ARR_SIZE);
+
+    //bubble_sort(arr, ARR_SIZE);
+    //select_sort(arr, ARR_SIZE);
+    insrt_sort(arr, ARR_SIZE);
+    prnt_arr(arr, ARR_SIZE);
+
+    return 0;
+}
+