1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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;
}
|
