Quel est le moyen le plus rapide (en théorie du moins) de trier un tas?

Question

Un segment de mémoire est une liste dans laquelle les éléments suivants s'appliquent:

l[i] <= l[2*i] && l[i] <= [2*i+1]

pour 0 <= i < len(list)

Je recherche un tri sur place.

Answer 1

Eh bien, vous êtes déjà à mi-chemin d'un tri dans le tas, car vos données sont dans un tas. Vous devez juste implémenter la deuxième partie de l'algorithme de tri de tas. Cela devrait être plus rapide que d'utiliser quicksort sur le tableau de segments de mémoire.

Si vous vous sentez courageux, vous pourriez essayer d'implémenter smoothsort , ce qui est plus rapide que heapsort pour des données presque triées.

Answer 2

Utilisez simplement le tri par tas. C'est en place. Ce serait le choix le plus naturel.

Vous pouvez aussi simplement utiliser votre segment de mémoire et le trier avec un autre algorithme. Ensuite, vous reconstruisez votre segment de mémoire à partir de la liste triée. Quicksort est un bon candidat car vous pouvez être sûr qu'il ne fonctionnera pas dans l'ordre le plus défavorable de l'ordre O (n & # 178;) simplement parce que votre segment de mémoire est déjà pré-trié.

Cela peut être plus rapide si votre fonction de comparaison est coûteuse. Heap-Sort ont tendance à évaluer la fonction de comparaison assez souvent.

Answer 3

Trier un type de tas in-situ ressemble à un travail pour le Tri par tas .

Je suppose que la mémoire est contrainte, une application intégrée peut-être?

Answer 4

Puisque vous avez déjà un segment de mémoire, ne pouvez-vous pas simplement utiliser la deuxième phase du sorte de segment de mémoire ? Cela fonctionne et devrait être agréable et efficace.

Answer 5

Pour le tri sur place, le moyen le plus rapide suit. Méfiez-vous des erreurs off-by-one dans mon code. Notez que cette méthode donne une liste triée inversée qui doit être non inversée à l'étape finale. Si vous utilisez un max-heap, ce problème disparaît.

L’idée générale est claire: permutez le plus petit élément (index 0) avec le dernier élément du tas, masquer cet élément jusqu’à ce que la propriété heap soit restaurée, réduisez la taille du tas de un, puis répétez-le.

Ce n'est pas le moyen le plus rapide pour le tri non sur place, comme l'explique David Mackay ici - vous pouvez faire mieux en plaçant un élément plus susceptible d’être le plus petit en haut du tas au lieu d’un élément de la rangée du bas.

La complexité temporelle est la pire éventualité: T (n.log n) - n itérations avec éventuellement log n (la hauteur du tas) passent par la boucle while.

for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
  {
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
  {
    if (l[i] > l[left])
      {
    swapidx = left;
      }
  }
else
  {
    if (l[i] > l[right])
      {
    swapidx = right;
      }
  }

if (swapidx == i)
  {
    // Found right place in the heap, break.
    break;
  }
swap( l, i, swapidx );
i = swapidx;
  }}

// Now reverse the list in linear time:
int s = 0; 
int e = len(l)-1;
while (e > s)
  {
    swap( l, s, e );
    s++; e--:
  }

Answer 6

Lisez les éléments du haut du tas, l'un après l'autre. Fondamentalement, ce que vous avez alors est un tri en tas.