Je cherche sur le tri par fusion et j'ai trouvé deux types de fonctions.
La première utilise la récursivité comme celle-ci.
#include <stdio.h>
#define MAX 30
int main() {
int arr[MAX], temp[MAX], i, j, k, n, size, l1, h1, l2, h2;
printf("Enter the number of elements : ");
scanf("%d", &n);
for (i = 0; i < n; i++) {
printf("Enter element %d : ", i + 1);
scanf("%d", &arr[i]);
}
printf("Unsorted list is : ");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
/* l1 lower bound of first pair and so on */
for (size = 1; size < n; size = size * 2) {
l1 = 0;
k = 0; /* Index for temp array */
while (l1 + size < n) {
h1 = l1 + size - 1;
l2 = h1 + 1;
h2 = l2 + size - 1;
/* h2 exceeds the limlt of arr */
if (h2 >= n)
h2 = n - 1;
/* Merge the two pairs with lower limits l1 and l2 */
i = l1;
j = l2;
while (i <= h1 && j <= h2) {
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= h1)
temp[k++] = arr[i++];
while (j <= h2)
temp[k++] = arr[j++];
/** Merging completed **/
/*Take the next two pairs for merging */
l1 = h2 + 1;
}/*End of while*/
/*any pair left */
for (i = l1; k < n; i++)
temp[k++] = arr[i];
for (i = 0; i < n; i++)
arr[i] = temp[i];
printf("\nSize=%d \nElements are : ", size);
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
}/*End of for loop */
printf("Sorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}/*End of main()*/
Et puis, j'ai pensé récursif la fonction n'est pas bonne pour les grands tableaux. Cette fonction provoque de nombreux appels récursifs dans ce cas. Je pense que c'est une mauvaise façon de programmer. (En fait, je n'aime pas la récursivité.)
Donc, j'ai trouvé une autre façon, une fonction de tri par fusion sans récursivité:
#include <stdio.h>
void merge(array, low, mid, high) {
int temp[MAX];
int i = low;
int j = mid + 1;
int k = low;
while ((i <= mid) && (j <= high)) {
if (array[i] <= array[j])
temp[k++] = array[i++];
else
temp[k++] = array[j++];
}/*End of while*/
while (i <= mid)
temp[k++] = array[i++];
while (j <= high)
temp[k++] = array[j++];
for (i = low; i <= high; i++)
array[i] = temp[i];
}/*End of merge()*/
void merge_sort(int low, int high) {
int mid;
if (low != high) {
mid = (low + high) / 2;
merge_sort(low, mid);
merge_sort(mid + 1, high);
merge(low, mid, high);
}
}/*End of merge_sort*/
Je pense que c'est mieux que d'utiliser la récursivité. Cette fonction réduit la récursivité à une série de boucles for et while ! Bien sûr, ils se sont comportés différemment. Je pense qu'une fonction récursive n'est pas bonne pour le compilateur. Ai-je raison?
3 Réponses :
En supposant des implémentations optimisées, le tri par fusion itératif ascendant est un peu plus rapide que le tri par fusion récursif descendant, car il ignore la génération récursive des index. Pour les tableaux plus grands, la surcharge supplémentaire de haut en bas est relativement faible, O (log (n)), par rapport au temps global de O (n log (n)), où dans les deux cas, la plupart du temps est passé à faire une fusion qui peut être identique à la fois de bas en haut et de haut en bas. Le tri par fusion de haut en bas utilise l'espace de pile O (log (n)), tandis que les deux utilisent l'espace de travail O (n). Cependant, presque toutes les implémentations de bibliothèques de tri stable sont une variante du tri de fusion itératif ascendant, comme un hybride de tri par insertion et de tri par fusion ascendant.
Lien vers une réponse montrant un tri de fusion de haut en bas optimisé, utilisant une paire de fonctions mutuellement récursives pour contrôler la direction de la fusion afin d'éviter la copie des données:
La mise en œuvre de Mergesort est lente
Lien vers une réponse qui inclut un tri rapide, un tri par fusion de bas en haut à 2 voies et un tri par fusion de bas en haut à 4 voies:
Merci pour votre réponse. J'ai lu votre lien, et ce sont des messages très utiles pour moi. Puis-je poser des questions hors sujet sur votre lien? J'ai lu le lien Mergesort est lent . Et je suis confus au sujet du commentaire du post.
Votre code size_t rr = (ll + ee) >> 1 . Quelqu'un commente cela peut provoquer un débordement. Enfin, il se retire à ce sujet .. Mais je ne comprends pas à propos de int ne peut pas avoir une taille> SIZE_MAX / (sizeof (int)) et il a également dit qu'il n'y avait pas de débordement dans < code> ee + ll si sizeof (int)> 1 . que signifient ces choses?
J'ai cherché à ce sujet, je pensais que la taille du tableau était proportionnelle à la mémoire. Ensuite, int peut utiliser plus de 32 bits ou plus. Suis-je bien compris ???
@JINU_K - En mode 32 bits, size_t est normalement un entier non signé de 32 bits. Pour que (ll + ee) déborde, la somme de ll + ee doit être supérieure à 2 ^ 32 == 4 Go, ce qui signifierait que le tableau aurait besoin de> = 2 ^ 31 = 2 Go d'éléments avant que le débordement puisse se produire. Étant donné que cet exemple particulier triait des entiers 32 bits, 2 Go d'éléments nécessiteraient 8 Go d'espace, ce qui ne serait pas possible dans un environnement 32 bits. Cela pourrait être possible si vous triez un tableau de 2 Go de caractères, et j'utilise l'alternative de size_t rr = ll + (ee-ll) / 2; , en supposant que le compilateur optimisera la division par 2 vers la droite décalage.
@JINU_K - en mode 64 bits, size_t est normalement un entier non signé de 64 bits, donc le dépassement ne peut pas se produire, car il nécessiterait un tableau avec> = 2 ^ 63 éléments.
Merci pour votre aimable réponse. Comme vous le dites, size_t rr = (ll + ee) >> 2 ne peut pas être débordé, car les int non signés ont un énorme MAX_SIZE (32 bits nécessitent 2 ^ 31 Array et 64 bits ont besoin de plus) . Donc, la plupart des fonctions ne peuvent pas toutes les utiliser ... n'est-ce pas?
@JINU_K - pour un environnement 32 bits, size_t est généralement un entier 32 bits non signé. Pour obtenir un débordement, un tableau a besoin de> = 2 ^ 31 == éléments de 2 Go. Cela pourrait être possible pour un tableau de char , en supposant un environnement 32 avec plus de 2 Go d'espace utilisateur. Cependant, l'utilisation du tri rapide sur un tableau de caractères n'a pas beaucoup de sens lorsque le comptage du tri serait un algorithme beaucoup plus rapide.
Vous avez un peu raison. Le tri de fusion itératif de bas en haut est plus rapide que le tri de fusion de haut en bas récursif. Les deux méthodes sont bonnes pour le compilateur;) mais la méthode récursive prend plus de temps à compiler.
La méthode récursive prend plus de temps à se compiler ... Pas vraiment. les deux fonctions se compilent également rapidement, l'approche récursive est en fait plus petite (moitié moins de code), donc il se peut qu'elle soit compilée plus rapidement, mais la différence serait extrêmement petite. De plus, le temps de compilation n'a pas d'importance: le temps d'exécution est la mesure de la performance.
@chqrlie Comme vous le dites, est-il plus important de construire une bonne logique de code? Et je n'aime pas la fonction recrusive, parce que si une fonction recrusive appelle deux recrues ou plus, cela provoque une augmentation expotentielle, j'ai pensé. Et la plupart des fonctions de logique récurrente en ont appelé plus d'un. J'ai très peur à ce sujet ... Suis-je trop inquiet?
@chqrlie et vous avez mal orthographié votre at-mention
@JINU_K: veuillez noter que vous avez mal orthographié récursif et récursivité. La programmation en C nécessite une bonne compréhension des algorithmes. En effet, les fonctions récursives peuvent poser des problèmes si le nombre d'appels imbriqués est trop élevé, mais dans le cas du tri par fusion, le niveau de récursivité est borné par log2 (N), donc seulement quelques dizaines pour les grands tableaux. Les programmes itératifs peuvent également se comporter de manière incorrecte, avec des boucles infinies et tous les programmes peuvent avoir un comportement indéfini et de nombreux autres bogues. Une approche récursive simple est parfois plus facile à comprendre qu'un ensemble plus compliqué de boucles imbriquées.
oh je me suis mal orthographié à propos de récursif-> récursif merci !! Et j'ai réalisé que je devais en apprendre davantage sur la complexité de l'espace-temps. Vos réponses et vos réponses sont une bonne lecture pour moi :)
Votre code pour l'approche récursive du tri par fusion a des problèmes:
merge n'a pas les types d'argument. merge_sort high car l'index du dernier élément est sujet aux erreurs et ne permet pas les tableaux vides. Vous devriez plutôt passer l'index au premier élément au-delà de la fin du tableau, de sorte que haut - bas soit le nombre d'éléments dans la tranche à trier. De cette façon, le premier appel à merge_sort peut prendre 0 et la taille du tableau. int temp [MAX]; pour chaque appel récursif. Gaspillage car la taille peut être beaucoup plus grande que nécessaire, entraînant un débordement potentiel de la pile, et incorrecte si haut - bas + 1 est plus grand que MAX conduisant à l'écriture au-delà de la fin de le tableau, provoquant un comportement indéfini. Cette fonction merge_sort s'appellera elle-même récursivement au plus log 2 (haut - bas) fois, chaque appel allouant un tableau local temporaire. Le nombre d'appels récursifs n'est pas le problème, seulement 30 pour 1 milliard d'enregistrements, mais les tableaux locaux le sont! Si vous essayez de trier un grand tableau, il se peut qu'il n'y ait pas assez d'espace sur la pile pour une copie de ce tableau, et encore moins de copies multiples, conduisant à un comportement indéfini, probablement un plantage.
Notez cependant que l'approche itérative que vous avez trouvée pose le même problème car elle alloue également temp [MAX] avec le stockage automatique.
La solution consiste à allouer un tableau temporaire à partir du tas au niveau du top et passez-le à la fonction récursive.
Voici une version améliorée:
#include <stdio.h>
static void merge(int *array, int *temp, int low, int mid, int high) {
int i = low;
int j = mid;
int k = 0;
while (i < mid && j < high) {
if (array[i] <= array[j])
temp[k++] = array[i++];
else
temp[k++] = array[j++];
}
while (i < mid)
temp[k++] = array[i++];
while (j < high)
temp[k++] = array[j++];
for (i = low, k = 0; i < high; i++, k++)
array[i] = temp[k];
}
static void merge_sort_aux(int *array, int *temp, int low, int high) {
if (high - low > 1) {
int mid = (low + high) / 2;
merge_sort_aux(array, temp, low, mid);
merge_sort_aux(array, temp, mid, high);
merge(array, temp, low, mid, high);
}
}
int merge_sort(int *array, int size) {
if (size > 1) {
int *temp = malloc(size * sizeof(*temp));
if (temp == NULL)
return -1;
merge_sort_aux(array, temp, 0, size);
free(temp);
}
return 0;
}
// call from main as merge_sort(arr, MAX)
J'ai compris que c'est le problème avec mon code. Merci. La gestion de la mémoire est très importante pour la fonction récursive. Je dois donc définir Temp Array sur Dynamic et libérer de la mémoire.
En général, je partage votre opinion qu'il est préférable d'utiliser des boucles plutôt que la récursivité. Ce dernier peut poser des problèmes si vous utilisez de grandes listes et que vous débordez la pile. Quoi qu'il en soit, votre question est basée sur une opinion et donc hors sujet ici.
Oh, je ne savais pas que ce sujet est hors sujet ... Bref, merci pour votre commentaire.
Pour une collection de N éléments à trier, vous obtenez une profondeur de récursivité de ~ log_2 (N). Cela signifie que, même si vous deviez trier tous les mots de tous les articles de Wikipédia , vous Je me retrouverais avec une profondeur de récursion de quelques dizaines ...
@ πάνταῥεῖ - Puisque le tri par fusion de bas en haut peut être démontré plus rapide que le tri par fusion de haut en bas, je ne considérerais pas cela comme une opinion.