Commits

ascetic85  committed 4f995ce

heap sort

  • Participants
  • Parent commits 8d9a9b2

Comments (0)

Files changed (4)

File sort/common.c

+#include "sort.h"
+
+#include <stdio.h>
+
+void my_swap(int *a, int *b)
+{
+    int c = *a;
+    *a = *b;
+    *b = c;
+}
+
+
+void print_array(int A[], int s, int size)
+{
+    int i = s;
+    for (; i < size; i++)
+        printf("%d ", A[i]);
+    printf("\n");
+}

File sort/heap_sort.c

+#include "sort.h"
+
+#define PARENT(i) ((i-1) / 2)
+#define LEFT(i) (2*i + 1)
+#define RIGHT(i) (2*i + 2)
+
+void max_heapify(int A[], int i, int size)
+{
+    int l = LEFT(i);
+    int r = RIGHT(i);
+    int largest = i;
+    if (l < size && A[l] > A[i])
+        largest = l;
+
+    if (r < size && A[r] > A[largest])
+        largest = r;
+
+    if (largest != i)
+    {
+        my_swap(&A[i], &A[largest]);
+        max_heapify(A, largest, size);
+    }
+}
+
+void build_max_heap(int A[], int size)
+{
+    my_swap(&A[0], &A[size-1]);
+    int i = size/2;
+    for (; i >= 0; i--)
+        max_heapify(A, i, size);
+}
+
+void heap_sort(int A[], int size)
+{
+    build_max_heap(A, size);
+    int i = size-1;
+    for (; i >= 1; i--)
+    {
+        my_swap(&A[0], &A[i]);
+        max_heapify(A, 0, i);
+    }
+}
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "sort.h"
+
+int main(int argc, char **argv)
+{
+    if (argc != 2) {
+        printf("Usage: \n\t%s [file]\n", argv[0]);
+        return 1;
+    }
+
+    FILE *in = freopen(argv[1], "rt", stdin);
+    FILE *out = freopen("out.txt", "wt", stdout);
+
+    int len;
+    scanf("%d", &len);
+
+    int *A = (int*) malloc (sizeof(int) * len);
+    int i = 0;
+    for (; i < len; i++)
+        scanf("%d", &A[i]);
+
+    clock_t start = clock();
+    heap_sort(A, len);
+    clock_t end = clock();
+    printf("Time using: %ld\n", end - start);
+
+    print_array(A, 0, len);
+
+    fclose(out);
+    fclose(in);
+
+    return 0;
+}
+#ifndef SORT_H
+#define SORT_H
+
+void print_array(int A[], int s, int size);
+
+void my_swap(int *a, int *b);
+
+void heap_sort(int A[], int size);
+
+#endif // SORT_H