Sortieren eines Vektors in absteigender Reihenfolge innerhalb von zwei Bereichen

14

Angenommen, ich habe einen Vektor von ganzen Zahlen:

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

Dann sortiere ich es in absteigender Reihenfolge:

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]);

Dies ergibt Folgendes:

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

Jetzt möchte ich, dass die Zahlen 3, 4, 5 und 6 an das Ende verschoben werden und die absteigende Reihenfolge für sie beibehalten wird (vorzugsweise ohne sie zum sortzweiten Mal verwenden zu müssen). Dh hier ist was ich will:

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

Wie soll ich die Vergleichsfunktion des ändern std::sort, um dies zu erreichen?

Yury
quelle
4
return indices[first] > indices[second]Meinst du nicht return first < second;?
acraig5075
2
Für eine einfache absteigend sortieren, std::greateraus <functional>kann anstelle des Lambda verwendet werden. In Bezug auf Ihre Frage ist es möglicherweise am einfachsten, einen ausführlicheren Vergleicher zu schreiben, der sicherstellt, dass Ihre Werte so vergleichen, wie Sie es möchten.
Zwischen
4
@ acraig5075, in absteigender Reihenfolge sollte es sein return first > second.
ks1322
1
@ acraig5075 Ich habe das Gefühl, etwas zu vermissen, oder kennen die Leute den Unterschied zwischen aufsteigend und absteigend nicht ?
Zwischen
3
Vielleicht suchen Sie std :: rotate ?
Super

Antworten:

8

Ihre Vergleichsfunktion ist falsch , da die Werte , die Sie erhalten , wie firstund secondsind die Elemente der std::vector. Daher müssen sie nicht als Indizes verwendet werden. Sie müssen sich also ändern

return indices[first] > indices[second];

zu

return first > second;

Nun zu dem Problem, das Sie zu lösen versuchen ...

Sie können 3, 4, 5 und 6 aus dem Vergleich mit anderen Elementen herauslassen und sie trotzdem miteinander vergleichen:

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;
    }
);

Demo

Nussknacker
quelle
@NutCracker Ja, ich stimme zu, dass es schöner ist, zuerst das oberste Kriterium zu haben.
Heap Overflow
5

Funktionen aus der Standard - Algorithmen - Bibliothek wie iota, sort, find, rotateund copywürden das Leben leichter machen. Ihr Beispiel lautet:

#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;
}

Ausgabe:

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


@TedLyngmo in den Kommentaren macht den guten Punkt, dass es verbessert werden könnte / sollte mit:

auto a = std::lower_bound(indices.begin(), indices.end(), 6, std::greater<int>{});
auto b = a + 4;
acraig5075
quelle
auto b = a + 4;ist falsch (wenn Sie die Konsistenz mit dem vorherigen Snippet beibehalten möchten). Es sollte sein, auto b = a + 3;weil in der std::rotateSie verwendenb + 1
Biagio Festa
3

Lösung 1

Einfacher Ansatz mit einem nichtlinearen Komparator.

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;
  });
}

Lösung 2

Mit 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{});
}

Leistungsüberlegungen

Es kann so aussehen, als ob die zweite Lösung aufgrund des Overheads der Partition langsamer ist. Wahrscheinlich nicht, weil in modernen Prozessoren Cache- und Fehlverzweigungsvorhersagen vorliegen.

Benchmark

Biagio Festa
quelle
Jeder gute Compiler sollte sich in das verwandeln n <= 6 && 3 <= n , was für die Ziel-CPU am besten funktioniert, damit Sie durch die Einführung der Zahlen 2 und 7 nichts als mögliche Verwirrung gewinnen - und warum anstelle einer Referenz einen Zeiger auf den Vektor verwenden?
Ted Lyngmo
Verwenden Sie nicht "const int number" als Argumentfunktion
Antoine Morrier
1
@AntoineMorrier Warum?
Heap Overflow
@HeapOverflow Weil es das gleiche ist, ohne const zu verwenden :).
Antoine Morrier
@AntoineMorrier Ich denke nicht, dass es das gleiche ist. Sagt das constdem Leser nicht, dass die Funktion den Wert nicht ändert? In diesem speziellen Fall eines Einzeilers mag es klar sein, aber im Allgemeinen ist es nicht.
Heap Overflow