Tri d'un vecteur par ordre décroissant dans deux plages

Disons que j'ai un vecteur d'entiers:

std::vector<int> indices;
for (int i=0; i<15; i++) indices.push_back(i);

Ensuite, je le trie par ordre décroissant:

sort(indices.begin(), indices.end(), [](int first, int second) -> bool{return indices[first] > indices[second];})
for (int i=0; i<15; i++) printf("%i\n", indices[i]);

Cela produit les éléments suivants:

14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

Maintenant, je veux que les chiffres 3, 4, 5 et 6 soient déplacés à la fin et garder l'ordre décroissant pour eux (de préférence sans avoir à utiliser sortpour la deuxième fois). C'est à dire, voici ce que je veux:

14
13
12
11
10
9
8
7
2
1
0
6
5
4
3

Comment dois-je modifier la fonction de comparaison du std::sortpour y parvenir?

Votre fonction de comparaison est incorrecte car les valeurs que vous obtenez en tant que firstet secondsont les éléments du std::vector. Il n'est donc pas nécessaire de les utiliser comme indices. Donc, vous devez changer

return indices[first] > indices[second];

à

return first > second;

Maintenant, concernant le problème que vous essayez de résoudre ...

Vous pouvez laisser 3, 4, 5 et 6 hors de comparaison avec d'autres éléments et toujours les comparer les uns aux autres:

std::sort(
    indices.begin(), indices.end(),
    [](int first, int second) -> bool {
        bool first_special = first >= 3 && first <= 6;
        bool second_special = second >= 3 && second <= 6;
        if (first_special != second_special)
            return second_special;
        else
            return first > second;
    }
);

Démo

Les fonctions de la bibliothèque d'algorithmes standards comme iota, sort, find, rotateet copyrendrait la vie plus facile. Votre exemple se résume à:

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iterator>


int main()
{
  std::vector<int> indices(15);
  std::iota(indices.begin(), indices.end(), 0);
  std::sort(indices.begin(), indices.end(), std::greater<>());

  auto a = std::find(indices.begin(), indices.end(), 6);
  auto b = std::find(indices.begin(), indices.end(), 3);
  std::rotate(a, b + 1, indices.end());

  std::copy(indices.begin(), indices.end(), std::ostream_iterator<int>(std::cout, "\n"));
  return 0;
}

Production:

14
13
12
11
10
9
8
7
2
1
0
6
5
4
3

auto a = std::lower_bound(indices.begin(), indices.end(), 6, std::greater<int>{});
auto b = a + 4;

Solution 1

Approche simple avec un comparateur non linéaire .

inline constexpr bool SpecialNumber(const int n) noexcept {
  return n < 7 && 2 < n;
}

void StrangeSortSol1(std::vector<int>* v) {
  std::sort(v->begin(), v->end(), [](const int a, const int b) noexcept {
    const bool aSpecial = SpecialNumber(a);
    const bool bSpecial = SpecialNumber(b);

    if (aSpecial && bSpecial) return b < a;
    if (aSpecial) return false;
    if (bSpecial) return true;
    return b < a;
  });
}

Solution 2

Utilisation de std::algorithms (partition)!

inline constexpr bool SpecialNumber(const int n) noexcept {
  return n < 7 && 2 < n;
}

void StrangeSortSol2(std::vector<int>* v) {
  auto pivot = std::partition(v->begin(), v->end(), std::not_fn(SpecialNumber));
  std::sort(v->begin(), pivot, std::greater{});
  std::sort(pivot, v->end(), std::greater{});
}

Considérations sur les performances

Il peut sembler que la deuxième solution est plus lente en raison de la surcharge de la partition. Ce n'est probablement pas le cas, en raison de la prédiction du cache et des branches manquantes dans les processeurs modernes.

Référence