Tri de tas fait en langage C

Au début

Je voulais créer divers algorithmes en utilisant le langage C, je vais donc commencer par écrire un tri de tas.

Livre de référence

"Structure des données et algorithme (par Atsushi Sugihara)" [Cliquez ici pour 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)

Qu'est-ce que le tri en tas?

Le moyen le plus simple de trier à l'aide d'arbres binaires est le tri rapide. Dans la plupart des cas, le tri rapide nécessite un temps de calcul O (nlogn), mais si vous n'êtes pas chanceux (la valeur triée est incluse dans l'entrée), cela prendra un temps de calcul O (n ^ 2). Le tri en tas comble cette lacune.

tas

Il existe deux conditions de tas

(1)L'arbre binaire est la profondeur k-Tous les sommets inférieurs ou égaux à 1 sont utilisés, et les sommets de profondeur k sont utilisés dans l'ordre à partir de la gauche.
(2)F si le sommet u est le parent du sommet v(u) ≥ f(v)Est

Lorsque ces deux conditions sont remplies, l'arborescence binaire est appelée un tas.

Tri de tas

Tout d'abord, il commence par stocker toutes les valeurs et créer un tas. Si la condition (2) n'est pas satisfaite lors de la création, le sommet et le sommet parent sont échangés et le tas est corrigé. Le temps de calcul à ce moment est O (nlogn) au maximum dans un arbre binaire à n sommets. Voici la méthode de tri du tas.

1. Si vous pouvez stocker toutes les valeurs et créer un tas, le tas a la valeur maximale stockée à la racine, donc enregistrez cette valeur à la toute fin du résultat du tri.
2. Puisque la valeur racine est supprimée, une valeur alternative doit être stockée dans cette racine, mais à la place, la valeur la plus profonde et la plus à droite de l'arborescence binaire est stockée et une valeur provisoire est stockée. Faites un état.
3. Dans cet état provisoire, la condition (2) n'est pas satisfaite, donc encore une fois, les valeurs parent et enfant sont permutées.

Ces répétitions sont des sortes de tas.

Implémentation du tri de tas

Cette fois, comme le titre l'indique, j'écrirai en langage C.

Créer un tas

Commencez par créer le tas. Puisque l'index est jusqu'à 0, 1, ..., n, si l'index enfant est i, l'index parent est (i -1) / 2. Cela peut être compris en écrivant un arbre binaire. Créez un programme en utilisant ceci.

HeapFunction

/*Créer un tas*/
/*reviens avec continuer*/
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 est le nombre d'éléments dans le tableau. Après avoir échangé des valeurs avec swap, j'utilise continuer à recommencer à partir de la valeur racine. La fonction swap utilisée dans l'instruction if est la mienne.

SwapFunction

void	swap(int *a, int *b)
{
	int tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;
}

terminer

Lorsque le tas est créé, index = 0 est la valeur maximale, alors échangez cette valeur avec la dernière valeur du tableau. Après cette opération, la valeur du premier ketsu ne participe pas à l'opération de tas, utilisez donc la valeur ht (heures de tas) pour couper la longueur du tableau un par un.

L'opération a également été ajoutée pour terminer la fonction heap_sort.

HeapFunction

void	heap_sort(int *num_array, int n)
{
	int 	i;
	int 	ht;

	hi = 0;
	while (ht < n - 1)
	{
		/*Créer un tas*/
		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++;
	}
}

Tournez jusqu'à ce que les temps de tas atteignent n-1 fois. Après chaque opération de tas, swap est utilisé pour permuter la valeur racine et la valeur du ketsu du tableau à ce moment.

Exécution du programme

L'ensemble du programme ressemble à ceci, y compris la fonction principale.

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)
    {
        /*Créer un tas*/
        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("----Avant de trier----\n");
    print_num_array(num_array, num);
    heap_sort(num_array, num);
    printf("----Avant de trier----\n");	
    print_num_array(num_array, num);
    return (0);
}

Compilateur d'exécution, options d'exécution

gcc -Wall -Wextra -Werror heap_sort.c

Résultat d'exécution

[zippowriter qiita]$ ./a.out
----Avant de trier----
23 5 900 45 11 65 4 0 0 9 432 43 444 899
----Après le tri----
0 0 4 5 9 11 23 43 45 65 432 444 899 900

Cela a fonctionné pour le moment.

À la fin

Honnêtement, je ne sais pas si c'est la bonne réponse parce que j'ai écrit les mots du livre de référence directement dans le code. L'imbrication est devenue plus profonde, je veux donc pouvoir écrire du code plus intelligent.