Gegeben eine Menge von Objekten, die 2 Werte haben. Sortieren Sie die Menge nach dem ersten Wert und dann nach dem zweiten Wert

Question

Beispiel:

{2,3},{1,2},(2,2},{3,1},{2,1} to {1,2},{2,1},{2,2},{2,3},{3,1}

Ich denke Folgendes:

Führen Sie eine Mischsortierung für die erste Spalte der Werte durch. Iterieren Sie über die Menge, um festzustellen, ob es in der ersten Spalte doppelte Werte gibt. Wenn ja, reihen Sie sie in eine Liste ein.

Sortieren Sie diese Liste nach der zweiten Spalte und integrieren Sie sie dann in die Hauptmenge. Das scheint zwar machbar zu sein, ist aber zu kompliziert. Dies sollte in O(NlogN) Wenn also jemandem ein schnellerer Algorithmus mit gleicher Komplexität einfällt, der auch noch einfacher ist, bitte melden!

Danke!

Answer 1

Implementieren Sie einfach eine Comparator<T> die zwei beliebige Objekte Ihres Typs vergleicht, indem sie zuerst das erste Feld vergleicht und dann zum zweiten Feld übergeht, wenn die ersten Felder gleich sind. Sie können die Menge dann in eine Liste kopieren, indem Sie Collections.sort und geben Sie ihm die Liste und Ihren Komparator. Es ist nicht nötig, die Sortierung selbst zu implementieren.

Der Komparator würde etwa so aussehen:

public class TwoFieldComparator implements Comparator<Foo>
{
    public int compare(Foo first, Foo second)
    {
        // TODO: null checks
        int firstComparison = Integer.compare(first.x, second.x);
        return firstComparison != 0 ? firstComparison
                                    : Integer.compare(first.y, second.y);
    }
}

Alternativ können Sie Ihre Klasse auch so gestalten, dass sie Comparable<T> auf die gleiche Art und Weise.

Answer 2

Sie müssen eine stabile Sortierung nach der zweiten Spalte und dann noch einmal nach der ersten Spalte durchführen.

Wenn der Bereich der Zahlen bestimmt werden kann, kann O(N) mit einer linearen Sortierung erreicht werden.

EDIT:

Nehmen Sie als Beispiel "Merge Sort" (weil es stabil ist):
1, Führen Sie eine Mischsortierung für die zweite Spalte durch, dann werden die Zahlenpaare nach dem Wert der zweiten Spalte geordnet.
2, Führen Sie erneut eine Mischsortierung für die erste Spalte durch, werden die Zahlenpaare in der Reihenfolge des ersten Spaltenwerts angeordnet. Da die Sortiermethode jedoch stabil ist, bedeutet dies, dass, wenn die erste Zahl gleich ist, auch die zweite Zahl sortiert wird (wir haben dies bei der ersten Sortierung getan).

Somit ist das Zahlenpaar-Array jetzt in Ordnung. Es sind keine weiteren Maßnahmen erforderlich.
Merge Sort ist O(NlogN), also ist 2*O(NlogN) immer noch O(NlogN).

EDIT2:
Nun, ich könnte dieses Problem kompliziert machen. Selbst wenn die Sortiermethode von uns selbst implementiert werden muss, ist es der bequemste Weg, den Vergleichscode von Jon Skeet in den entsprechenden Teil der handgefertigten Sortiermethode einzufügen, solange die Datenstruktur festgelegt wurde.

Answer 3

Wie Sie in einem Ihrer Kommentare erwähnten, handelt es sich um eine Interviewfrage. Die Lösung von John Skeet zeigt, dass Sie sich keine Sorgen machen müssen, wenn Sie zwei Werte in Ihrem Element haben - implementieren Sie einfach den richtigen Komparator.

Angenommen, Sie werden 2011 danach gefragt, dann wäre es gut, wenn Sie herausfinden würden, wie Ihre Sorte verwendet werden soll. Je nach Umgebung, in der diese Sortierung verwendet werden soll, können Sie eine parallele Verarbeitung (mit mehreren Threads) in Betracht ziehen. Dies kann die Wahl des Sortieralgorithmus beeinflussen.