[gelöst] Schnell Sortieren mit QMap oder QHash?

[24dan]

Hi, habe vor folgendes Beispiel schnell zuordnen

• Liste1 [3,5,3,5,6,8]
  Liste2 [200,300,400,300,300,700]
  Liste3 [ab,zu,auf,an,wo,wer]

(Die Anzahl der Elemente der Listen ist immer gleich groß.)

Nach folgenden Bedingungen soll sortiert werden

1. Liste 3 Nach Liste1 (groß -> klein) ordnen
2. Zahlen in Liste1 mehrfach vorhanden = nach entsprechenden Elementen (index!) von Liste2 ordnen (groß -> klein)
3. Zahlen in Liste2 auch mehrfach vorhanden = nach index ordnen (groß -> klein)

Ergebnis würde in diesem Beispiel so aussehen:

Code: Alles auswählen

a.) Liste1 sortiert
b.) Liste1 [3,3] mit Liste2 Elementen [200,400] also Ergebnis << ab << auf;
c.) Liste1 [5,5] mit Liste2 Elementen [300,300] also Ergebnis << zu << an;
d.) Liste1 [6] also Ergebnis << wo;
e.) Liste1 [8] also Ergebnis << wer;

Ergebnis = [ab, auf, zu, an, wo, wer]

FRAGE:Kann ich diese mühselige Aufgabe nicht auch einfacher machen mit QMap oder einem QHash? Gibt es nicht die Möglichkeit einfach eine virtuelle Tabelle aufzubauen und dann nach x Kretarien zu sortieren?

[Christian81]

Entweder eine QMap und dann über die Elemente iterieren oder qSort() und damit eine QList sortieren.

[upsala]

Keine Ahnung, wie du sortieren willst, aber schon mal mit qSort probiert?

[24dan]

Also an beide vielen Dank qsort und ein paar suchen bei google habe es gebracht.

Idee:

Ich stecke die Parameter für die Sortierung einfach in richtiger Reihenfolge für die einzelnen Indizes der Elemente in je einen String und die alle in eine List. Dann setze ich qsort drauf an und siehe da.....

Schon fertig.

Hier die Lösung:

Code: Alles auswählen

    QStringList test, ende;
    test.append("5:300*1");
    test.append("4:300*2");
    test.append("4:300*3");
    test.append("4:200*4");
    qDebug()<<test;
    test.sort();

("4:200*4", "4:300*2", "4:300*3", "5:300*1")

Jetzt ziehe ich mir die Indizes für die Liste3 aus jedem String raus und schon haben wirs.....

[franzf]

Zahl -> String -> Zahl ist aber nicht sonderlich performant.
Denkst du es wäre möglich, die drei Zahlen in einen Struct zu packen und dafür dann entsprechende Vergleichsoperatoren anzubieten?

[24dan]

Also zu meiner Überraschung funktioniert das mit Zahl -> String auch nicht da qsort die String "Zahlen" nicht sieht und somit auch 210 kleiner ist als 56.

Also qsort QStringList ist nicht möglich.

@franzf Also ich versuche es gerade mal mit QVector<QPair(int x, int y)>
Kannst Du mir genauer erklären was Du Dir bei struct und Vergleichsoperatoren gedacht hast?

Mein Hauptproblem ist die Alten Indizes nach dem qsort noch zu wissen.
Wenn ich das hinbekomme mir die zu merken und schnell mit den sortiertem Wert in Verbindung zu bringen...

[franzf]

Kannst Du mir genauer reklären was Du Dir bei struct und Vergleichsoperatoren gedacht hast?

Code: Alles auswählen

struct Sortogramm {
  int zahl1;
  int zahl2;
  string wort;
};

// qSort() braucht operator<
bool operator<(const Sortogramm& left, const Sortogramm& right) {
  if( left.zahl1 == right.zahl1 ) {
    if( left.zahl2 == right.zahl2 ) {
      return true; //ich belass es einfach unsortiert
    } else {
      return left.zahl2 < right.zahl2;
    }
  } else {
    return left.zahl1 < right.zahl1;
  }
}

ostream& operator<<( ostream& os, const Sortogramm& s ) {
  os << s.wort;
  return os;
}

int main() {
  std::vector<Sortogramm> vec;
  qSort(vec);
  foreach( const Sortogramm& s, vec ){
    cout << s << endl;
  }
}

Keine AHnung ob du dir das so vorgestellt hast mit dem Sortierkriterium.

[24dan]

Ja genau so habe ich mir dass vorgestellt.

Also ich habe es jetzt mit QVector auch nicht hinbekommen und mich für folgende Variante entschieden:

Wobei l_bst_s zw_s die Zahlen enthalten und l_textfolge meinen zu sortierenden Text...

Code: Alles auswählen

        QList <QList<unsigned long> > l_sort2;
        QList <unsigned long> dummy;
        unsigned long i = 0;
        foreach(unsigned long zw_s, l_zw_s){
            dummy << l_bst_s.at(i)<< zw_s << i;
            l_sort2 << dummy;
            i++;
            dummy.clear();
        }

        bool fertig;
        do{
            unsigned long i = 1;
            fertig = true;
            foreach(QList<unsigned long> l_list, l_sort2){
                if(i<l_sort2.length()){
                    // Ebene Buchstabenanzahl
                    if(l_list.at(0)>l_sort2.at(i).at(0)){
                        l_sort2.move(i-1,i);
                        fertig = false;
                    }
                    else if(l_list.at(0)==l_sort2.at(i).at(0)){
                        // Ebene Zw
                        if(l_list.at(1) > l_sort2.at(i).at(1)){
                            l_sort2.move(i-1,i);
                            fertig = false;
                        }
                        else if(l_list.at(1)==l_sort2.at(i).at(1)){
                            // Ebene Position im Text
                            if(l_list.at(2) > l_sort2.at(i).at(2)){
                                l_sort2.move(i-1,i);
                                fertig = false;
                            }
                        }
                    }
               i++;
               }
            }
        }while( !fertig );

        QStringList l_wertfolge2;
        foreach(QList<unsigned long> l_list, l_sort2) l_wertfolge2.append(l_textfolge[ l_list[ 2 ] ]);

[franzf]

Das war SO aber nicht meine Idee!
Du führst drei Listen, die irgendwie zusammengehören. Warum also die zusammengehörigen Daten nicht in einen Datensatz (struct) legen. Dann wird aus einem furchtbaren, fehleranfälligen Monster ein netter kleiner "operator<". Ist es denn ein absolut unausweichliches Muss, da drei separate Listen zu führen? Bzw. welche Bedingungen hast du für das Projekt und dessen Realisierung?

[24dan]

Ohhh je....

Also ja Du hast Recht. Ich stöhne nur auf weil das viel Zeit braucht um verstehen was hier gemacht werden soll.
Kurz: Ich habe schon einen eigene Klasse (struct) angelegt von der ich jeweils dann Objekte (Elemente meiner Listen) bilde und die Daten darin verwalte.

Fazit: Ich sollte wohl diese Klasse mit einer Methode ausstatten in der die Sortierung stattfinden kann.

Hier mal ein Teil meiner Verwendeten Klasse:

Code: Alles auswählen

//! Klasse für die Auswertung
class TEIL
{

//public slots:
public:
    TEIL *next;
    TEIL *first;

    TEIL();
    ~TEIL();
    // Hier sind die Zahlen 1 bis  3
    unsigned long i_zw;
    unsigned long i_owa;
    unsigned long i_owb;
stuff..

 // FUNKTIONEN DER KLASSE TEIL
    unsigned long kodieren (QChar bst,
                  unsigned long i_ow_beta );
    TEIL * getFirst(void);
    TEIL * getNext(void);
    void setFirst(TEIL *ptrOberebene,
                  TEIL *ptrUnterebene);
    TEIL * setNext(TEIL *erster,
                   TEIL *neu);
    void setNULL( TEIL *ptrZuruecksetzten );
    void aufAddieren(TEIL *ptrOberebene);

stuff..



// Hierher gehört eigentlich auch:
void sortieren();