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.

Recommended Posts

Heapsort made in C language
Machine language embedding in C language
Multi-instance module test in C language
Realize interface class in C language
Segfault with 16 characters in C language
Linked list (list_head / queue) in C language
Generate C language from S-expressions in Python
How to multi-process exclusive control in C language
Set up a UDP server in C language
Handle signals in C
Container-like # 1 made with C
C language ALDS1_3_B Queue
Access MongoDB in C
Next Python in C
Container-like # 2 made with C
I made a module in C language to filter images loaded by Python
[C language algorithm] Endianness
C API in Python 3
Try to make a Python module in C language
Go language to see and remember Part 7 C language in GO language
Extend python in C ++ (Boost.NumPy)
C language ALDS1_4_B Binary Search
Use regular expressions in C
I made my own language. (1)
Programming language in "Hello World"
Imitated Python's Numpy in C #
Binary search in Python / C ++
I tried to illustrate the time and time in C language
Hello World in GO language
[C language] readdir () vs readdir_r ()
C language ALDS1_4_A Linear Search
I made my own language (2)
Minimum spanning tree in C #
Introduction to Socket API Learned in C Language Part 1 Server Edition
I made a C ++ learning site
Write a table-driven test in C
Try implementing Yubaba in Go language
Use optinal type-like in Go language
Function pointer and objdump ~ C language ~
100 Language Processing Knock Chapter 1 in Python
Writing C language with Sympy (metaprogramming)
ABC166 in Python A ~ C problem
Numer0n with items made in Python
High energy efficiency programming language C
Introduction to Protobuf-c (C language ⇔ Python)
When reading C ++ structs in Cython
Post to slack in Go language
Switch the language displayed in Django 1.9
Solve ABC036 A ~ C in Python
Start SQLite in a programming language
How to wrap C in Python
[C language algorithm] Binary search tree
Solve ABC037 A ~ C in Python
C language 8 queens problem solving 3 patterns
Write tests in GO language + gin
Write C unit tests in Python
Call c language from python (python.h)
Do something object-oriented in GO language
[C language] I want to generate random numbers in the specified range
Guidelines for reincarnating in the world of linux programming development (C / C ++ language)
I made a kind of simple image processing tool in Go language.