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.

Recommended Posts

Tri de tas fait en langage C
Intégration du langage machine en langage C
Test de module multi-instance en langage C
Réaliser une classe d'interface en langage C
Segfo avec 16 caractères en langage C
Liste de liens (list_head / queue) en langage C
Générer un langage C à partir d'une expression S avec Python
Méthode de contrôle exclusive multi-processus en langage C
Configurer un serveur UDP en langage C
Gérer les signaux en langage C
En forme de conteneur réalisé avec C # 1
File d'attente ALDS1_3_B langage C
Accéder à MongoDB en C
Next Python en langage C
J'ai fait un module en langage C qui filtre les images chargées par Python
[Algorithme de langage C] Endianness
API C en Python 3
Essayez de créer un module Python en langage C
Aller à la langue pour voir et se souvenir du langage Partie 7 C en langage GO
Étendre python en C ++ (Boost.NumPy)
Recherche binaire ALDS1_4_B langage C
Utiliser des expressions régulières en C
J'ai fait ma propre langue. (1)
Imiter Numpy de Python en C #
Recherche binaire en Python / C ++
J'ai essayé d'illustrer le temps et le temps du langage C
Hello World en langue GO
[Langage C] readdir () vs readdir_r ()
Recherche linéaire ALDS1_4_A en langage C
J'ai fait ma propre langue (2)
Arborescence de surface totale minimale en C #
Introduction à l'API Socket apprise en langage C, partie 1, édition serveur
J'ai créé un site d'apprentissage C ++
Ecrire un test piloté par table en C
Essayez d'implémenter Yuma en langage Go
Pointeur de fonction et objdump ~ Langage C ~
100 Language Processing Knock Chapitre 1 en Python
Ecriture du langage C avec Sympy (métaprogrammation)
ABC166 en Python A ~ C problème
Numer0n avec des objets fabriqués avec Python
Langage de programmation C à haute efficacité énergétique
Introduction à Protobuf-c (langage C ⇔ Python)
Lors de la lecture d'une structure C ++ avec Cython
Changer la langue affichée dans Django 1.9
Résoudre ABC036 A ~ C avec Python
Démarrez avec SQLite dans un langage de programmation
Comment envelopper C en Python
[Algorithme de langage C] arbre de recherche binaire
Résoudre ABC037 A ~ C avec Python
Langage C 8 reine résolution de problèmes 3 modèles
Ecrire un test en langue GO + gin
Ecrire un test unitaire de langage C en Python
Appeler le langage C depuis Python (python.h)
Faites quelque chose orienté objet dans le langage GO
[Langage C] Je souhaite générer des nombres aléatoires dans la plage spécifiée
Lignes directrices pour se réincarner dans le monde du développement de programmation Linux (langage C / C ++)
J'ai fait une sorte d'outil de traitement d'image simple en langage Go.