From c6bc541ab58363d783e60a007e80e9bf9e231fda Mon Sep 17 00:00:00 2001
From: garhve <git@garhve.com>
Date: Mon, 5 Dec 2022 19:43:39 +0800
Subject: initialize

---
 c/dataStructure/sorting/selectionSort.c | 86 +++++++++++++++++++++++++++++++++
 1 file changed, 86 insertions(+)
 create mode 100755 c/dataStructure/sorting/selectionSort.c

(limited to 'c/dataStructure/sorting/selectionSort.c')

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;
+}
-- 
cgit v1.2.3-70-g09d2