Quicksort zum Sortieren eines Arrays von Objekten nach einem bestimmten Mitglied, C++

class Foo
{
    public:
        int num;
        int other;
};

int main()
{
    Foo bar[10].num = {1, 9, 3, 5, 1, 6, 10, 0, 6, 3};

    //quicksort(bar)

    return 0;
}

Ich will schreiben Sie eine quicksort-Funktion, dass Bestellungen, die 'bar' array 'num' aufsteigend. Nicht ganz sicher, was ist der beste Ansatz zu nehmen, wie ich noch nie eine geschrieben quicksort. Ich sah einige Beispiel-codes, aber ich kann nicht sehen, wie Sie zu ändern für diesen Fall. Ein inplace Sortieren erfolgt durch übergabe von Zeigern auf das erste und Letzte Elemente des Arrays nicht funktioniert, da diese nur sortiert die 'num' - Mitglied nicht das gesamte Objekt. Die Aufteilung der array von Objekten in einen unteren Bereich, einen Hebel und einen oberen Bereich und rekursiv Sortieren jeder sieht vielversprechend aus, aber ich bin mir nicht sicher, wie die übergabe der Werte funktionieren würde...

Jede Hilfe sehr dankbar. Sorry, wenn dies wurde gebeten vor.

  • mögliche Duplikate von c++ - Art mit Strukturen
  • +1 ich denke, es ist durchaus eine Frage wie "was ist, wenn ich etwas komplexer als ein array von Werten"? So kann es nützlich sein, darüber nachzudenken, was genau eine Sortier-Funktion, und was eine compare-Funktion im besonderen. Wie kann die Distanz zwischen komplexen Elemente gemessen werden?
InformationsquelleAutor Rich | 2011-01-02
  1. 10

    Zuerst müssen Sie eine Funktion schreiben(oder Funktor) auf und vergleichen Sie Ihre Objekte durch was auch immer Wert, den Sie wollen. Es sollten zwei Objekte und liefert ein bool. Es sollte true zurückgeben, wenn die erste sollte vor dem zweiten, andernfalls false. Dann pass auf das std::sort.

    struct compare_Foo_by_num
{
    bool operator() (const Foo & lhs, const Foo & rhs) { return lhs.num < rhs.num; }
};

int main()
{
    Foo bar[10];

    std::sort(bar, bar+10, compare_Foo_by_num());
}
    • Der Komparator muss ebenfalls false zurück auf die gleichen Werte, d.h. es sollte wirken wie ein < Betreiber.
    • Das funktioniert Super, danke! Ich werde schauen müssen, wie sich die std::sort funktioniert, wenn ich entscheiden, zu schreiben, meine eigenen, aber das ist gut für das, was ich Schreibe.
    • schreiben Sie Ihre eigene quicksort ist eine schlechte Idee, außer für pädagogische Zwecke
    InformationsquelleAutor Benjamin Lindley
  2. 3

    Können Sie überlastung operator< zu vergleichen und das gewünschte Element aus, und verwenden Sie dann std::sort.

    #include <algorithm>

class Foo
{
public:
    int num;
    int other;
};

bool operator<(const Foo& x, const Foo& y)
{
    return x.num < y.num;
}

int main()
{
    Foo bar[10] = {{1, 5}, {9, 2}, {3, 0}, {5, 7}, {1, 3}, {6, 4}, {10, 8}, {0, 9}, {6, 2}, {3, 5}};
    std::sort(bar + 0, bar + 10);
}

    Beachten Sie, dass Sie benötigen zwei zahlen zu initialisieren Foo, nicht nur die, die Sie interessiert sind bei der Sortierung.

    Wenn Sie nicht können oder nicht wollen, um eine überlastung operator< für Foo andere Optionen umfassen die übergabe eines guten alten C-Stil-Funktion Zeiger oder eine C++ - Stil-Funktion-Objekt als Dritten parameter std::sort.

    InformationsquelleAutor fredoverflow
  3. 1

    Andere alternative ist die Verwendung von std::sort mit einem lambda-Ausdruck:

    int main()
{
    Foo bar[10] = {{1,5},{9,2},{3,0},{5,7},{1,3},{6,4},{10,8},{0,9},{6,2},{3,5}};

    std::sort(bar, bar + 10, [](const Foo &x, const Foo &y) {
        return x.num < y.num;
    });
}
    InformationsquelleAutor Blastfurnace
  4. 0

    Wenn Sie hartnäckig auf der Umsetzung Ihrer eigenen quicksort, schlage ich vor, schauen sich dieses video an, um Ihnen zu helfen, sich besser vorzustellen, der Algorithmus. Wenn Sie habe nie geschrieben, eine quicksort-Sie finden es möglicherweise einfacher zu implementieren, nachdem ich es.
    http://www.youtube.com/watch?v=vxENKlcs2Tw

    InformationsquelleAutor xXhRQ8sD2L7Z
Schreibe einen Kommentar