Ich habe einen ungewöhnlichen Sortierfall, bei dem mein Googeln kaum aufgetaucht ist. Hier sind die Parameter:
1) Random-Access-Container. (C ++ Vektor)
2) Im Allgemeinen kleine Vektorgröße (weniger als 32 Objekte)
3) Viele Objekte haben Relationen zueinander, aber sie sind nicht gleich. (Es ist ihnen egal, welche von ihnen zuerst in dem endgültigen sortierten Vektor erscheint, aber sie können sich anders mit anderen Objekten vergleichen.) Um es auf einen dritten Weg zu bringen (wenn es noch unklar ist), kann die Vergleichsfunktion für 2 Objekte zurückkehren 3 Ergebnisse: "Bestellung ist korrekt", "Bestellung muss gekippt werden" oder "egal".
4) Gleichheiten sind möglich, werden aber sehr selten sein. (Aber das würde wahrscheinlich nur wie jede andere "do-not-care" behandelt werden.
5) Vergleichsoperator ist viel teurer als Objektbewegung.
6) Es gibt keine Vergleichsgeschwindigkeitsdifferenz, um festzustellen, ob sich Objekte umeinander kümmern oder nicht. (d. h. ich kenne keinen Weg, um einen schnelleren Vergleich zu machen, der einfach sagt, ob sich die beiden Objekte umeinander kümmern.)
7) Zufällige Startreihenfolge.
Ich habe einen ungewöhnlichen Sortierfall, bei dem mein Googeln kaum aufgetaucht ist. Hier sind die Parameter:
1) Random-Access-Container. (C ++ Vektor)
2) Im Allgemeinen kleine Vektorgröße (weniger als 32 Objekte)
3) Viele Objekte haben Relationen zueinander, aber sie sind nicht gleich. (Es ist ihnen egal, welche von ihnen zuerst in dem endgültigen sortierten Vektor erscheint, aber sie können sich anders mit anderen Objekten vergleichen.) Um es auf einen dritten Weg zu bringen (wenn es noch unklar ist), kann die Vergleichsfunktion für 2 Objekte zurückkehren 3 Ergebnisse: "Bestellung ist korrekt", "Bestellung muss gekippt werden" oder "egal".
4) Gleichheiten sind möglich, werden aber sehr selten sein. (Aber das würde wahrscheinlich nur wie jede andere "do-not-care" behandelt werden.
5) Vergleichsoperator ist viel teurer als Objektbewegung.
6) Es gibt keine Vergleichsgeschwindigkeitsdifferenz, um festzustellen, ob sich Objekte umeinander kümmern oder nicht. (d. h. ich kenne keinen Weg, um einen schnelleren Vergleich zu machen, der einfach sagt, ob sich die beiden Objekte umeinander kümmern.)
7) Zufällige Startreihenfolge.
Was Sie dort haben, ist eine "teilweise Bestellung".
Wenn Sie eine einfache Möglichkeit haben, die Objekte herauszufinden, bei denen die Reihenfolge für ein gegebenes Objekt nicht "egal" ist, können Sie dies mit Basic topologische Sortierung .
Wenn Sie viele "egal" haben (dh wenn Sie nur eine unterquadratische Anzahl von Kanten in Ihrem partiellen Ordnungsdiagramm haben), ist dies viel schneller als gewöhnliches Sortieren - wenn Sie das tun nicht der Algorithmus wird quadratisch sein!
Sie können die Sortierung nicht mit "egal" machen, es ist wahrscheinlich, dass die Reihenfolge der Elemente gestört wird. Beispiel:
%Vor%Selbst wenn es zwischen A und B nicht wichtig ist, muss B größer als A sein, oder einer davon wird falsch sein: B & gt; C oder A & lt; C. Wenn es nie passieren wird, dann müssen Sie sie als gleich behandeln, anstatt es egal.
Ich glaube, eine Auswahlsortierung funktioniert ohne Änderung, wenn Sie das "Do-not-Care" -Ergebnis als behandeln gleich. Natürlich lässt die Performance zu wünschen übrig.
Was auch immer Sie tun werden, unter Ihren Bedingungen würde ich sicherstellen, dass Sie einen großen Stapel von Testfällen erstellen (z. B. ein paar Datensätze bekommen und sie einige tausend Mal mischen), da ich denke, dass es einfach wäre Wählen Sie eine Art, die Ihren Anforderungen nicht entspricht.
Das "egal" ist schwierig, da die meisten Sortieralgorithmen von einer strikten Reihenfolge des Sortierwerts abhängen - wenn A kleiner oder gleich B ist und B kleiner oder gleich C ist es geht davon aus, dass A kleiner oder gleich C ist - in deinem Fall, wenn A sich nicht um B kümmert, aber C interessiert, aber B ist kleiner als C, was liefert du dann für den AB-Vergleich A wird mit C verglichen?
Aus diesem Grund und da es sich um kleine Vektoren handelt, würde ich empfehlen, KEINE der eingebauten Methoden zu verwenden, da ich denke, dass Sie die falschen Antworten erhalten, stattdessen würde ich eine benutzerdefinierte Einfügesortierung erstellen.
Beginnen Sie mit einem leeren Zielvektor, fügen Sie das erste Element ein und suchen Sie dann für jedes nachfolgende Objekt nach den Grenzen, in die es eingefügt werden kann (dh ignorieren Sie das "nicht kümmern", suchen Sie das letzte Element, nach dem es suchen muss) und die erste muss vorher gehen) und fügt sie in die Mitte dieser Lücke ein und verschiebt alles andere entlang des Zielvektors (dh es wächst jedes Mal um einen Eintrag).
[Wenn die Vergleichsoperation besonders teuer ist, sollten Sie besser in der Mitte beginnen und in eine Richtung scannen, bis Sie eine Grenze erreicht haben. Wählen Sie dann, ob die andere Grenze von dieser Grenze oder dem Mittelpunkt aus bewegt wird. .. dies würde wahrscheinlich die Anzahl der Vergleiche reduzieren, aber wenn man liest, was man über seine Anforderungen sagt, kann man zB keine binäre Suche verwenden, um den richtigen Ort zum Einfügen jedes Eintrags zu finden]
Ja, das ist im Grunde O (n ^ 2), aber für ein kleines Array ist das egal, und Sie können beweisen, dass die Antworten richtig sind. Sie können dann sehen, ob andere Arten besser sind, aber wenn Sie nicht eine richtige Reihenfolge für ein bestimmtes Paar zurückgeben können, werden Sie seltsame Ergebnisse bekommen ...
Ich habe einen ungewöhnlichen Sortierfall, bei dem mein Googeln kaum aufgetaucht ist. Hier sind die Parameter:
1) Random-Access-Container. (C ++ Vektor)
2) Im Allgemeinen kleine Vektorgröße (weniger als 32 Objekte)
3) Viele Objekte haben Relationen zueinander, aber sie sind nicht gleich. (Es ist ihnen egal, welche von ihnen zuerst in dem endgültigen sortierten Vektor erscheint, aber sie können sich anders mit anderen Objekten vergleichen.) Um es auf einen dritten Weg zu bringen (wenn es noch unklar ist), kann die Vergleichsfunktion für 2 Objekte zurückkehren 3 Ergebnisse: "Bestellung ist korrekt", "Bestellung muss gekippt werden" oder "egal".
4) Gleichheiten sind möglich, werden aber sehr selten sein. (Aber das würde wahrscheinlich nur wie jede andere "do-not-care" behandelt werden.
5) Vergleichsoperator ist viel teurer als Objektbewegung.
6) Es gibt keine Vergleichsgeschwindigkeitsdifferenz, um festzustellen, ob sich Objekte umeinander kümmern oder nicht. (d. h. ich kenne keinen Weg, um einen schnelleren Vergleich zu machen, der einfach sagt, ob sich die beiden Objekte umeinander kümmern.)
7) Zufällige Startreihenfolge.
Was Sie dort haben, ist eine "teilweise Bestellung".
Wenn Sie eine einfache Möglichkeit haben, die Objekte herauszufinden, bei denen die Reihenfolge für ein gegebenes Objekt nicht "egal" ist, können Sie dies mit Basic topologische Sortierung .
Wenn Sie viele "egal" haben (dh wenn Sie nur eine unterquadratische Anzahl von Kanten in Ihrem partiellen Ordnungsdiagramm haben), ist dies viel schneller als gewöhnliches Sortieren - wenn Sie das tun nicht der Algorithmus wird quadratisch sein!
Sie können die Sortierung nicht mit "egal" machen, es ist wahrscheinlich, dass die Reihenfolge der Elemente gestört wird. Beispiel:
%Vor%Selbst wenn es zwischen A und B nicht wichtig ist, muss B größer als A sein, oder einer davon wird falsch sein: B & gt; C oder A & lt; C. Wenn es nie passieren wird, dann müssen Sie sie als gleich behandeln, anstatt es egal.
Ich glaube, eine Auswahlsortierung funktioniert ohne Änderung, wenn Sie das "Do-not-Care" -Ergebnis als behandeln gleich. Natürlich lässt die Performance zu wünschen übrig.
Was auch immer Sie tun werden, unter Ihren Bedingungen würde ich sicherstellen, dass Sie einen großen Stapel von Testfällen erstellen (z. B. ein paar Datensätze bekommen und sie einige tausend Mal mischen), da ich denke, dass es einfach wäre Wählen Sie eine Art, die Ihren Anforderungen nicht entspricht.
Das "egal" ist schwierig, da die meisten Sortieralgorithmen von einer strikten Reihenfolge des Sortierwerts abhängen - wenn A kleiner oder gleich B ist und B kleiner oder gleich C ist es geht davon aus, dass A kleiner oder gleich C ist - in deinem Fall, wenn A sich nicht um B kümmert, aber C interessiert, aber B ist kleiner als C, was liefert du dann für den AB-Vergleich A wird mit C verglichen?
Aus diesem Grund und da es sich um kleine Vektoren handelt, würde ich empfehlen, KEINE der eingebauten Methoden zu verwenden, da ich denke, dass Sie die falschen Antworten erhalten, stattdessen würde ich eine benutzerdefinierte Einfügesortierung erstellen.
Beginnen Sie mit einem leeren Zielvektor, fügen Sie das erste Element ein und suchen Sie dann für jedes nachfolgende Objekt nach den Grenzen, in die es eingefügt werden kann (dh ignorieren Sie das "nicht kümmern", suchen Sie das letzte Element, nach dem es suchen muss) und die erste muss vorher gehen) und fügt sie in die Mitte dieser Lücke ein und verschiebt alles andere entlang des Zielvektors (dh es wächst jedes Mal um einen Eintrag).
[Wenn die Vergleichsoperation besonders teuer ist, sollten Sie besser in der Mitte beginnen und in eine Richtung scannen, bis Sie eine Grenze erreicht haben. Wählen Sie dann, ob die andere Grenze von dieser Grenze oder dem Mittelpunkt aus bewegt wird. .. dies würde wahrscheinlich die Anzahl der Vergleiche reduzieren, aber wenn man liest, was man über seine Anforderungen sagt, kann man zB keine binäre Suche verwenden, um den richtigen Ort zum Einfügen jedes Eintrags zu finden]
Ja, das ist im Grunde O (n ^ 2), aber für ein kleines Array ist das egal, und Sie können beweisen, dass die Antworten richtig sind. Sie können dann sehen, ob andere Arten besser sind, aber wenn Sie nicht eine richtige Reihenfolge für ein bestimmtes Paar zurückgeben können, werden Sie seltsame Ergebnisse bekommen ...
Was Sie dort haben, ist eine "teilweise Bestellung".
Wenn Sie eine einfache Möglichkeit haben, die Objekte herauszufinden, bei denen die Reihenfolge für ein gegebenes Objekt nicht "egal" ist, können Sie dies mit Basic topologische Sortierung .
Wenn Sie viele "egal" haben (dh wenn Sie nur eine unterquadratische Anzahl von Kanten in Ihrem partiellen Ordnungsdiagramm haben), ist dies viel schneller als gewöhnliches Sortieren - wenn Sie das tun nicht der Algorithmus wird quadratisch sein!
Ich glaube, eine Auswahlsortierung funktioniert ohne Änderung, wenn Sie das "Do-not-Care" -Ergebnis als behandeln gleich. Natürlich lässt die Performance zu wünschen übrig.