J'écris une fonction pour trier un tableau en utilisant le tri de tas. Jusqu'à présent, j'ai:Le tri de tas ne produit pas une sortie correcte
template <typename Item, typename SizeType>
void heap_sort(Item data[], SizeType size) {
vector<int> v(data,data+size);
SizeType unsorted = size;
make_heap(v.begin(),v.end());
while(unsorted > 1) {
--unsorted;
swap(data[0], data[unsorted]);
reheapify_down(data,unsorted);
}
}
et:
template <typename Item, typename SizeType>
void reheapify_down(Item data[], SizeType size) {
SizeType current(0), big_child;
bool heap_ok = false;
while(!heap_ok && 2*current+1 < size) {
if(2*current+2 > size)
big_child = 2*current + 1;
else if(data[2*current+1] > data[2*current+2])
big_child = 2*current+1;
else
big_child = 2*current + 2;
if(data[current] < data[big_child]) {
swap(data[current],data[big_child]);
current = big_child;
}
else
heap_ok = true;
}
}
Quand je lance le programme, il émet un tableau mal trié cependant. Y a-t-il quelque chose qui me manque ou une erreur que j'ai oubliée?
Donnez-nous quelques exemples d'entrée et de sortie. –
Eh bien, mon programme a trié un ensemble aléatoire de valeurs entières à partir de maintenant, mais la sortie d'un tableau aléatoire de taille 10 ressemble à: 0424488971. –
Je vais passer maintenant et mettre en place un tableau de test pour voir ce qu'il produit . –