I wanted to create various algorithms using C language, so I will write heapsort first.
"Data Structure and Algorithm (by Kokichi Sugihara)" [Click here for amazon](https://www.amazon.co.jp/%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0%E3 % 81% A8% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0-% E6% 9D% 89% E5% 8E% 9F-% E5% 8E% 9A% E5% 90% 89 / dp / 4320120345)
Quicksort is the easiest sort using binary trees. In most cases, quicksort requires only O (nlogn) calculation time, but if you are unlucky (the sorted value comes into the input), it will take O (n ^ 2) calculation time. Heapsort fills that shortcoming.
There are two heap conditions
(1)Binary tree is depth k-All vertices less than or equal to 1 are used, and vertices of depth k are used in order from the left.
(2)F if vertex u is the parent of vertex v(u) ≥ f(v)Is
When these two conditions are met, the binary tree is called a heap.
We start by storing all the values and creating a heap. If condition (2) is not met during creation, the vertices and parent vertices are swapped and the heap is repaired. The calculation time at this time is O (nlogn) at the maximum in a binary tree with n vertices. The following is the heapsort method.
These repetitions become heapsort.
This time, as the title says, I will write in C language.
First, create the heap. Since the index is up to 0, 1, ..., n, if the child index is i, the parent index is (i -1) / 2. You can see this by writing a binary tree. Make a program using this.
HeapFunction
/*Create heap*/
/*come back with continue*/
i = 0;
while (i < n)
{
if (num_array[i] > num_array[(i - 1) / 2])
{
swap(&num_array[i], &num_array[(i - 1) / 2]);
i = 0;
continue;
}
i++;
}
n is the number of elements in the array. After swapping the values, I'm using continue to start from the root value again. The swap function used in the if statement is my own.
SwapFunction
void swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
When the heap is created, index = 0 is the maximum value, so exchange this value with the last value in the array. After this operation, the value of the first ketsu does not participate in the heap operation, so use the value ht (heap times) to cut the length of the array one by one.
The operation was also added to complete the heap_sort function.
HeapFunction
void heap_sort(int *num_array, int n)
{
int i;
int ht;
hi = 0;
while (ht < n - 1)
{
/*Create heap*/
i = 0;
while (i < n - ht)
{
if (num_array[i] > num_array[(i - 1) / 2])
{
swap(&num_array[i], &num_array[(i - 1) / 2]);
i = 0;
continue;
}
i++;
}
swap(&num_array[n - ht - 1], &num_array[0]);
hi++;
}
}
Turn until heap times reaches n-1 times. After each heap operation, swap is used to swap the root value and the value of the array at that time.
The whole program looks like this, including the main function.
heap_sort.c
#include <stdio.h>
void swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void heap_sort(int *num_array, int n)
{
int i;
int hi;
hi = 0;
while (hi < n - 1)
{
/*Create heap*/
i = 0;
while (i < n - hi)
{
if (num_array[i] > num_array[(i - 1) / 2])
{
swap(&num_array[i], &num_array[(i - 1) / 2]);
i = 0;
continue;
}
i++;
}
swap(&num_array[n - hi - 1], &num_array[0]);
hi++;
}
}
void print_num_array(int *num_array, int n)
{
int i;
i = 0;
while (i < n)
{
printf("%d ", num_array[i]);
i++;
}
printf("\n");
}
int main(void)
{
int num_array[] = {23, 5, 900, 45, 11, 65, 4, 0, 0, 9, 432, 43, 444, 899};
int num;
num = sizeof(num_array) / sizeof(int);
printf("----Before sorting----\n");
print_num_array(num_array, num);
heap_sort(num_array, num);
printf("----Before sorting----\n");
print_num_array(num_array, num);
return (0);
}
gcc -Wall -Wextra -Werror heap_sort.c
[zippowriter qiita]$ ./a.out
----Before sorting----
23 5 900 45 11 65 4 0 0 9 432 43 444 899
----After sorting----
0 0 4 5 9 11 23 43 45 65 432 444 899 900
It worked for the time being.
I honestly wrote down the words in the reference book into the code, so I honestly don't know if this is the correct answer. The nesting has become deeper, so I want to be able to write smarter code.
Recommended Posts