[GO] Heapsort made in C language

At the beginning

I wanted to create various algorithms using C language, so I will write heapsort first.

Reference book

"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)

What is heapsort?

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.

heap

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.

Heapsort

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.

1. If you can store all the values and create a heap, the heap has the maximum value stored at the root, so record this value at the very end of the sort result.
2. Since the root value is removed, we have to store an alternative value in this root, but instead we store the deepest and rightmost value of the binary tree, tentative Make a state.
3. In this tentative state, condition (2) is not satisfied, so again, the parent and child values are swapped.

These repetitions become heapsort.

Heapsort implementation

This time, as the title says, I will write in C language.

Create heap

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;
}

Finish

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.

Program execution

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);
}

Execution compiler, execution options

gcc -Wall -Wextra -Werror heap_sort.c

Execution result

[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.

At the end

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.