initialize

5 files changed, 313 insertions, 0 deletions

diff --git a/c/dataStructure/sorting/bubbleSort.c b/c/dataStructure/sorting/bubbleSort.c
new file mode 100755
index 0000000..521a781
--- /dev/null
+++ b/c/dataStructure/sorting/bubbleSort.c
@@ -0,0 +1,47 @@
+#include<stdio.h>
+#include<stdlib.h>
+#include<time.h>
+
+#define SIZE 10
+
+void swap(int * a, int * b)
+{
+	int tmp = *a;
+	*a = *b;
+	*b = tmp;
+}
+
+void generateRandom(int * arr, int n)
+{
+	time_t sr;
+	srand(sr);
+
+	for (int i = 0; i < n; i++)
+		arr[i] = rand() % 100;
+}
+
+void bubbleSort(int * arr, int n)
+{
+	for (int i = 0; i < n; i++)
+		for (int j = 0; j < n - 1 - i; j++)
+			if (arr[j] > arr[j+1])
+				swap(&arr[j],&arr[j+1]);
+}
+
+int main(void)
+{
+	int arr[SIZE];
+	generateRandom(arr,SIZE);
+
+	for (int i = 0; i < SIZE; i++)
+		printf("%3d",arr[i]);
+	putchar('\n');
+
+	bubbleSort(arr,SIZE);
+
+	for (int i = 0; i < SIZE; i++)
+		printf("%3d",arr[i]);
+	putchar('\n');
+
+	return 0;
+}
diff --git a/c/dataStructure/sorting/insertSort.c b/c/dataStructure/sorting/insertSort.c
new file mode 100755
index 0000000..741f295
--- /dev/null
+++ b/c/dataStructure/sorting/insertSort.c
@@ -0,0 +1,60 @@
+#include<stdio.h>
+#include<stdlib.h>
+#include<time.h>
+
+#define SIZE 10
+
+void swap(int * a, int * b)
+{
+	int tmp = *a;
+	*a = *b;
+	*b = tmp;
+}
+
+void generateRandom(int * arr, int n)
+{
+	time_t sr;
+	srand(*&sr);
+
+	for(int i = 0; i < n; i++)
+		arr[i] = rand() % 100;
+}
+
+void print(int * arr, int n)
+{
+	for(int i = 0; i < n; i++)
+		printf("%3d",*(arr+i));
+	putchar('\n');
+}
+
+void insertSort(int * arr, int n)
+{
+	int key, i, j;
+	
+	for (i = 1; i < n; i++)
+	{
+		key = arr[i];
+		j = i - 1;
+
+		while (j >= 0 && key < arr[j])
+		{
+			arr[j+1] = arr[j];
+			j--;
+		}
+		arr[j+1] = key;
+	}
+}
+
+int main(void)
+{
+	int arr[SIZE];
+	generateRandom(arr,SIZE);
+
+	print(arr,SIZE);
+
+	insertSort(arr,SIZE);
+
+	print(arr,SIZE);
+
+	return 0;
+}
diff --git a/c/dataStructure/sorting/mergeSort.c b/c/dataStructure/sorting/mergeSort.c
new file mode 100755
index 0000000..826df71
--- /dev/null
+++ b/c/dataStructure/sorting/mergeSort.c
@@ -0,0 +1,57 @@
+#include<stdio.h>
+
+#define N 10
+
+void merge(int * A, int low, int mid, int high)
+{
+    int m, n;
+    m = mid - low + 1;
+    n = high - mid;
+    int a1[m],a2[n];
+
+    for (int i = 0; i < m; i++)
+        a1[i] = A[low + i];
+    for (int j = 0; j < n; j++)
+        a2[j] = A[mid + 1 + j];
+
+    //compare two subsets, put lower one in sorted array
+    int i = 0, j = 0, k = low;
+
+    while (i < m && j < n)
+    {
+        if (a1[i] <= a2[j])
+            A[k++] = a1[i++];
+        else
+            A[k++] = a2[j++];
+    }
+
+    //Insert remains
+    while (i < m)
+        A[k++] = a1[i++];
+    while (j < n)
+        A[k++] = a2[j++];
+}
+
+void mergeSort(int * A, int low, int high)
+{
+    if (low < high)
+    {
+        int mid = low + (high - low) / 2;
+        mergeSort(A,low,mid);
+        mergeSort(A,mid+1,high);
+        merge(A,low,mid,high);
+    }
+}
+
+int main(void)
+{
+    int A[N] = {12,63,58,95,41,35,65,0,38,44};
+
+    mergeSort(A,0,N - 1);
+
+    for (int i = 0; i < N; i++)
+        printf("%3d",A[i]);
+
+    putchar('\n');
+    return 0;
+}
diff --git a/c/dataStructure/sorting/quickSort.c b/c/dataStructure/sorting/quickSort.c
new file mode 100755
index 0000000..2904b48
--- /dev/null
+++ b/c/dataStructure/sorting/quickSort.c
@@ -0,0 +1,63 @@
+#include<stdio.h>
+#include<stdlib.h>
+#include<time.h>
+
+#define SIZE 10
+
+void swap(int * a, int * b)
+{
+	int tmp = *a;
+	*a = *b;
+	*b = tmp;
+}
+
+void generateRandom(int * arr, int n)
+{
+	time_t sr;
+	srand(sr);
+
+	for(int i = 0; i < n; i++)
+		arr[i] = rand() % 100;
+}
+
+int partition(int * arr, int low, int high)
+{
+	int i,j;
+	for (i = low, j = low; i < high; i++)
+		if (arr[i] < arr[high])
+		{
+			swap(&arr[i],&arr[j]);
+			j++;
+		}
+	swap(&arr[high],&arr[j]);
+
+	return j;
+}
+
+void quickSort(int * arr, int low, int high)
+{
+	if (low < high)
+	{
+		int pivot = partition(arr,low,high);
+		quickSort(arr,low, pivot - 1);	// sort left
+		quickSort(arr,pivot + 1, high);
+	}
+}
+
+int main(void)
+{
+	int arr[SIZE];
+	generateRandom(arr,SIZE);
+
+	for(int i = 0; i < SIZE; i++)
+		printf("%3d",*(arr+i));
+	putchar('\n');
+
+	quickSort(arr,0,SIZE - 1);
+
+	for (int i = 0; i < SIZE; i++)
+		printf("%3d",arr[i]);
+	putchar('\n');
+
+	return 0;
+}
diff --git a/c/dataStructure/sorting/selectionSort.c b/c/dataStructure/sorting/selectionSort.c
new file mode 100755
index 0000000..0bfb671
--- /dev/null
+++ b/c/dataStructure/sorting/selectionSort.c
@@ -0,0 +1,86 @@
+#include<stdio.h>
+#include<time.h>
+#include<stdlib.h>
+
+void swap(int * a, int * b)
+{
+    int tmp;
+    tmp = *a;
+    *a = *b;
+    *b = tmp;
+}
+
+int * selectionSort(int * arr, size_t n)
+{
+    int tmp = 0;
+    for (int i = 0; i < (int)n - 1; i++)
+    {
+        int position = i;
+        for (int j = i + 1; j < (int)n; j++)
+            if ( arr[position] > arr[j])
+                position = j;
+        if (position != i)
+            swap(&arr[position], &arr[j]);
+    }
+
+    return arr;
+}
+
+void heapify(int * arr, size_t n, int i)
+{
+    int smallest = i;
+    int left = 2 * i + 1;
+    int right = 2 * i + 2;
+
+    if (left < n && arr[left] > arr[smallest])
+        smallest = left;
+    if (right < n && arr[right] > arr[smallest])
+        smallest = right;
+
+    if (smallest != i)
+    {
+        swap(&arr[i], &arr[smallest]);
+        heapify(arr,n,smallest);
+    }
+}
+
+int * heapSort(int * arr, size_t n)
+{
+    for (int i = n/2 - 1; i >= 0; i--)
+        heapify(arr,n,i);
+
+    for (int i = n - 1; i >= 0; i--)
+    {
+        swap(&arr[i],&arr[0]);
+        heapify(arr,i,0);
+    }
+
+    return arr;
+}
+
+int main(void)
+{
+    int sarr[] = {12,63,58,95,41,35,65,0,38,44};
+    int harr[] = {12,63,58,95,41,35,65,0,38,44};
+    size_t size = sizeof(sarr)/sizeof(int);
+
+
+    printf("Before sort:\n");
+    for (int i = 0; i < (int)size; i++)
+        printf("%3d",sarr[i]);
+    putchar('\n');
+
+    selectionSort(sarr,size);
+    printf("After selection sort:\n");
+    for (int i = 0; i < (int)size; i++)
+        printf("%3d",sarr[i]);
+    putchar('\n');
+
+    heapSort(harr,size);
+    printf("After heap sort:\n");
+    for (int i = 0; i < (int)size; i++)
+        printf("%3d",harr[i]);
+    putchar('\n');
+
+    return 0;
+}