2
votes

possible de déplacer les zéros à la fin du tableau en utilisant uniquement std :: sort ()?

Je travaille sur cette question:

Étant donné un tableau nums, écrivez une fonction pour déplacer tous les 0 à la fin de celui-ci tout en conservant l'ordre relatif des éléments non nuls.

Je sais comment répondre à cette question en effectuant simplement un échange sur place, mais je voudrais également voir s'il est possible de le résoudre avec std :: sort .

Selon cplusplus.com:

la fonction de comparaison pour la fonction de tri est une fonction binaire qui accepte deux éléments de la plage comme arguments, et renvoie une valeur convertible en bool. La valeur renvoyée indique si l'élément passé en tant que premier argument est considéré comme précédant le second dans l'ordre strict strict qu'il définit.

La fonction ne modifiera aucun de ses arguments.

Cela peut être un pointeur de fonction ou un objet de fonction.

//comments below are based on my understanding
static bool comp(int a, int b){
    //lambda function evaluates to true - no swap, 
    //evaluates to false -swap
    if(a==0) return false;
    if(b==0) return true;
    //if neither a nor b is 0 them do not swap
    return true;
}

void moveZeroes(vector<int>& nums) {
    sort(nums.begin(),nums.end(),comp);
}

le cas de test donné est [0,1,0,3,12

ma sortie est [12,3,1,0,0]

c++ sorting stl

3 commentaires

Cela reviendra à l'interprétation de la norme. Il est indiqué que la fonction comp doit appliquer un ordre strict strict. Il est clair que comp (4, 5) sera true , mais comp (5, 4) sera également Sois sincère. Cela rompt techniquement l'ordre strict strict, mais étant donné ce cas d'utilisation, je ne pense pas que le comportement soit tout à fait indéfini.

@Chad C'est un ordre strict et faible. Les valeurs 4 et 5 sont équivalentes aux fins du tri souhaité, donc lorsqu'elles sont comparées dans l'un ou l'autre ordre, elles doivent renvoyer false.

Bien qu'il ne soit pas directement posé dans cette question, l'algorithme prévu pour une tâche comme celle-ci serait std :: partition ou std :: stable_partition .

3 Réponses :

0
votes

L'ordre de tri que vous souhaitez utiliser est simplement que les zéros sont "supérieurs" à toutes les valeurs non nulles et égaux aux autres zéros. Toutes les autres valeurs non nulles sont "inférieures" à zéro et sont équivalentes à toute autre valeur non nulle.

Construisez correctement la fonction de comparaison, puis vous pouvez l'utiliser dans un appel à std :: stable_sort pour réaliser ce que vous essayez de faire.

0 commentaires

6
votes

Vous aviez presque raison. Dans votre fonction comparateur, vous devez renvoyer false pour ne pas les échanger. Remplacez également std :: sort par std :: stable_sort pour conserver les valeurs dans l'ordre d'origine.

static bool comp(int a, int b)
{
    //lambda function evaluates to true - no swap, 
    //evaluates to false -swap
    if(a==0) return false;
    if(b==0) return true;
    //if neither a nor b is 0 them do not swap
    return false;
}

void moveZeros(std::vector<int>& nums)
{
    std::stable_sort(nums.begin(),nums.end(),comp);
}

LIVE DÉMO

2 commentaires

Ou plus succinctement, il suffit de return (a! = 0) && (b == 0);

Ou simplement return b == 0; ;

1
votes

Comme l'a souligné Drew Dormann, la partition stable est l'algorithme approprié. Voici le code:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> data { 0, 1, 0, 3, 12 };

    std::stable_partition(
        data.begin(), data.end(), [](int n) { return n != 0; });

    for (auto i : data)
        cout << i << ' ';

    cout << endl;
}

Le résultat est 1 3 12 0 0

0 commentaires