Actualisation de l'algorithme. Pourquoi heapsort est un algorithme d'insort?

Je ne vois pas pourquoi le tri sélectif est considéré comme un algorithme de tri sur place .

Je veux dire qu'une structure de données supplémentaire remplie avec les éléments du tableau à trier, c'est-à-dire un tas, est utilisée pour aider à l'extraction de la valeur min et au processus de tri.

Alors peut-être que je me méprends sur la définition de inplace ici?

Mais par exemple par insertion, il est évident qu'il s'agit d'un algorithme in situ, c'est-à-dire qu'aucune mémoire supplémentaire n'est nécessaire pour les éléments.

Alors pourquoi est-il considéré comme étant en place?

Je veux dire qu'une structure de données supplémentaire remplie avec les éléments du tableau à trier, c'est-à-dire un tas, est utilisée pour aider à l'extraction de la valeur min et au processus de tri.

Non. Le tableau est transformé pour se conformer à la contrainte de tas sans utiliser plus de O (1) de mémoire supplémentaire. (En fait, tout ce dont vous avez besoin est de mémoire supplémentaire suffisante pour contenir un élément du tableau, à des fins d'échange, plus un booléen ou deux et une variable de boucle ou deux).

Ok, d'un point de vue technique, il se peut que le heapsort soit généralement expliqué comme utilisant un tas séparé, mais il est parfaitement possible de l'implémenter en place.

Il se peut que vous manquiez la compréhension fondamentale qu'un tableau peut être utilisé pour spécifier la disposition d'une arborescence.

Supposons que vous ayez un arbre binaire et qu'un nœud intérieur se trouve à l'index i du tableau. Ensuite, l'index du tableau du parent et des enfants de ce nœud peut être trouvé par:

Parent(i) = floor(i/2)
Left child(i) = 2i
Right child(i) = 2i + 1

Voir:

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

Étant donné que le tas peut être conservé et organisé entièrement dans un tableau, le heapsort peut s'exécuter sur place en déplaçant des éléments à l'intérieur du tableau d'entrée. En effet, le tas est construit et manipulé à l'aide du tableau d'entrée d'origine.

Si, comme vous le dites, il fallait vraiment une structure supplémentaire pour construire le tas, alors heapsort ne serait en effet PAS un algorithme de tri sur place.

Cependant, ce n'est pas le cas. Vous pouvez créer le tas sur le même tableau que vous souhaitez trier, et après cela, vous appliquez l'algorithme heapsort, afin qu'il trie sur place.

En informatique, un algorithme sur place (ou en latin in situ) est un algorithme qui transforme les entrées à l'aide d'une structure de données avec une petite quantité constante d'espace de stockage supplémentaire. L'entrée est généralement remplacée par la sortie lors de l'exécution de l'algorithme. Un algorithme qui n'est pas en place est parfois appelé non en place ou hors place.

Wikipedia - Algorithme sur place

Il est considéré comme étant en place car ses exigences d'espace sont négligeables (constantes ou nulles du tout si vous utilisez des opérations au niveau du bit pour échanger des éléments). MergeSort, par exemple, n'est pas en place car le jeu d'entrée n'est pas modifié à chaque itération de l'exemple de recherche.

La meilleure façon d'illustrer les différences entre les algorithmes en place et les algorithmes hors lieu est probablement de regarder le code d'inversion de chaîne C / C ++ suivant qui le fait en place (de K&R):

void reverse(char s[])
{
      int c, i, j;

      for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
         c = s[i];
         s[i] = s[j];
         s[j] = c;
      }
}

Si vous lisiez, par exemple, la chaîne d'entrée depuis la fin et placiez les caractères dans un autre tampon, ce serait un algorithme d'inversion de chaîne hors de propos.