Le tri de Tableau de Pointeurs en C++

En espérant que je peux obtenir un peu de conseils sur une méthode de tri que j'ai fait.

Le but de ce code est de créer un pointeur de int tableau et trier les pointeurs dans ce tableau par le contenu de l'ordinaire int tableau. Puis à assigner des valeurs d'une variable différente en fonction de l'emplacement de l'original du tableau int.

L'étrangeté je suis en train de vivre avec ce code, c'est que le code de test qui ne devrait pas l'effet de quelque chose d'aussi loin que je sache... EST en fait effectuer le contenu de mes pointeurs.
Peut-être que les valeurs ne changent pas, mais la façon dont je suis en train d'écrire le code de test est à l'origine des erreurs.

 //create array
 int c[8] = {3,1,5,7,8,2,6,4};
 //create pointer array
 int *newptr[8];
 for(int k = 0; k<8; k++)
 {
     newptr[k] = &c[k];
 }
//sort pointer array
for(int j = 0; j<8; j++)
{
    for(; j > -1 && *newptr[j] < *newptr[j+1]; j--)
    {
        int *temp = newptr[j+1];
        newptr[j+1] = newptr[j];
        newptr[j] = temp;
    }
}
//set lookuplocation
int lookuplocation;
for(int i = 0; i<8; i++)
{
    cout << *newptr[i];

    if(newptr[i] == &c[0])
    {
        cout << *newptr[i] << endl;

        //If I use endl or \n to test the pointers values I end up with only
        //a part of the correct data. 

        cout << "\nSuccess!\n";
        lookuplocation = 0;
    }
}
//Also for my last test sometimes the first element gets messed up as well
//test arrays
for(int k = 0; k<8; k++)
{
    cout << "Element " << k << ": " << *newptr[k] << endl;
    cout << "Element " << k << ": " << newptr[k] << endl;
}

votre tri est foiré
Boucles imbriquées avec le même compteur j ? Comment peut-il travailler à tous?
Avez-vous besoin d'écrire le code pour trier le tableau de pointeurs, ou avez-vous besoin de trier un tableau de pointeurs? Veuillez préciser lesquels. Si vous n'avez pas besoin d'écrire votre propre code, la solution est triviale.
"je n'ai pas vraiment appris à les utiliser (conteneurs STL) dans la classe." - bien sûr, vous n'étiez pas, parce que l'ensemble d'entre nous le sait C++ est mieux enseignée par l'enseignement de la "C avec cout" en premier. 😉
Votre code a un bug. Dans le tri boucle, lorsque j==7 l'expression newptr[j+1] accède à un élément après la fin du tableau.

OriginalL'auteur Connor | 2013-08-05

algorithm arrays c++pointers sorting

9

J'ai pensé que quelqu'un pourrait réellement besoin de trier un tableau de pointeurs dans un façon saine:
```
#include <iostream>
#include <array>
#include <algorithm>

int main() {
    std::array<int, 8> arr { 3, 5, 4, 1, 2, 7, 6, 8 };
    std::array<int*, 8> p_arr;

    for (unsigned i = 0; i < 8; ++i) {
        p_arr[i] = &arr[i];
    }

    std::sort(p_arr.begin(), p_arr.end(), [](int* a, int* b) { return *a < *b; });

    for (auto i : p_arr) 
        std::cout << *i;
}
```
Le laid milieu de la boucle est totalement remplacer'able par gamme de plus de zippped gamme, mais je n'ai pas mon propre mise en œuvre avec la référence de la sémantique à l'instant, et je suis trop paresseux pour vérifier la renforcer.¹

Voici un échantillon vivent sur Coliru.

Aussi, parce que je pense que nous devrions répétez cette opération jusqu'à ce que les débutants comprendre:
- Ne pas réinventer la tri roue (sauf si c'est un jouet de mise en œuvre)
- Essayez d'éviter d'utiliser les pointeurs en C++ si cela est raisonnablement possible.
¹Ce qui est réellement important afin de s'assurer que les deux gammes (dans ce cas, deux tableaux) ont la même longueur. Différents compression des conventions soit exiger que les plages de la même longueur (s'écraser ou de jeter des autres) ou de remplir le vide de données d'une de ces plages d'être trop court. Même si cela semble évident dans un tel programme simple, être prudent dans le monde réel code.

vous devez apprendre la Bibliothèque Standard avant les pointeurs.

OriginalL'auteur Bartek Banachewicz
3

Si votre tableau c[n] a l'intervalle [1 .. n], vous pouvez utiliser l'algorithme suivant qui fonctionne en O(n) le temps de la complexité:
```
for(int j = 0; j < n; j++)
    while(*newptr[*newptr[j] - 1] != *newptr[j])
        std::swap(newptr[*newptr[j] - 1], newptr[j]);
```
L'idée derrière cela est d'attribuer la valeur 1 pour le pointeur newptr[0], 2 pour le pointeur newptr[1], ..., et n du pointeur newptr[n-1]. Il n'y a pas d'algorithme qui est plus efficace (surtout en C++11, depuis std::swap utilisera std::move).

Donc pour int c[8] = {3,1,5,7,8,2,6,4}, vous obtenez (abstraction faite de la référence à la valeur de la table):

1233

Succès!
45678

Mise à jour: Si vous voulez l'ordre inverse:
```
for(int j = 0; j < n; j++)
    while(*newptr[n - *newptr[j]] != *newptr[j])
        std::swap(newptr[n - *newptr[j]], newptr[j]);
```
Pour int c[8] = {3,1,5,7,8,2,6,4}, vous obtenez:

8765433

Succès!
21

Bien que cela fonctionne, il trie le chemin inverse qui j'en suis sûr, peut être facilement corrigé. Mais mon principal problème que je traite avec des est de comprendre si oui ou non je peux faire une comparaison de l'adresse de mon tableau int et les pointeurs. Je suis sûr maintenant que c'est ce qui a été raté mon code.
En fait, je crois que j'ai été d'écraser mes pointeurs.
Vous voulez dire que vous voulez que le script de tri de 8 à 1 au lieu de 8 à 1?
ouais 8 à 1 pas de 1 à 8.
Regarde la réponse que j'ai mis à jour 9 heures.

OriginalL'auteur Kyle_the_hacker

Populaires approche est de mettre en œuvre générique sort fonction qui trie les éléments par comparaison, de sorte que vous pouvez résumé sur les éléments du tableau. Il y a quelques façons:

template<typename ElementType, typename CompType>
void sort(ElementType array[], size_t size, CompType cmp);
template<typename ElementType, typename CompType>
void sort(std::vector<ElementType> & array, CompType cmp);
template<typename IteratorType, typename CompType>
void sort(IteratorType first, IteratorType last, CompType cmp);

Dernière manière est préférable, car vous pouvez résumé par type de conteneur trop.

OriginalL'auteur MAnyKey

0

Changement de cette première:

for(; j > -1 && *newptr[j] < *newptr[j+1]; j--)

en

for(int i=j; i > -1 && *newptr[i] < *newptr[i+1]; i--)

Il semble beaucoup plus efficace..

mais très déroutant. la simplicité est le plus important pour moi à ce point.
ce n'est pas, en réutilisant le même j est source de confusion, en effet, il pourrait faire baisser la j dans votre boucle externe qui n'est probablement pas le but?
Hmm. Maintenant que j'y pense, plus il réduit le montant du traitement des nombres. Il n'est pas nécessaire, mais c'est une bonne idée. Merci!
plus efficace? lien
oui, vous avez raison, il n'aura pas un grand impact, mais il est ridicule de réduire le j dans la boucle externe car il n'y a aucune raison pour que. (quand j'ai écrit "beaucoup" j'ai été incorreclty en supposant que j> 0 à chaque fois)

OriginalL'auteur DDW

Vous devez vous connecter pour publier un commentaire.