Sortierverfahren

c147258

volkard schrieb:

ich versteh dich überhaupt nicht. von welchen listen redest du? wollen wir uns nicht darauf einigen, einen std::vectorstd::string> zu sortieren? oder meinetwegen alle zeilen, die über cin ind programm kommen?

//
// EVL - String - Char
//

typedef struct LISTELEMENT_CHAR{
    char *data;
    struct LISTELEMENT_CHAR *next;
}ListElement_char;

Danke...war zu vertieft das ich es vergessen habe das ich die Liste direkt beim reinschreiben sortieren könnte.

Also:
Eingabe (Übergabe von VB)
Datentyp VARIANT in eine doppelt verkettete Liste - unsortiert
nun die Strings (vorher konvertierung von BSTR nach Char in eine einfach verkette Liste während des schreibens schon sortieren (oder erst nachher?)

Danke

Eingabe und das mit der DVL ist schon fix.

Mit Vectoren hab ich leider keine Erfahrung

c147258 schrieb:

nun die Strings (vorher konvertierung von BSTR nach Char in eine einfach verkette Liste während des schreibens schon sortieren (oder erst nachher?)

nachher. beim einsortieren haste O(n^2) und nimmst insertion sort. beim nachher-sortieren haste O(n*log(n)), was ganz erheblich viel schneller bei vielen (sagen wir mal mehr als 100000 elemeten) ist.

Eingabe und das mit der DVL ist schon fix.

ok.
also die eingangsdaten sind als VARIANT in einer DVL.

die schaufelst du ein eine EVL um und machst char* aus den VARIANTs. machste das nur, um zu sortieren, oder ist die EVL auch als ausgangsdaten gefordert? normaler wäre nämlich ein char**. also das, was zwischendurch in meiner funktion (siehe unten) benutzt wird.

ich gehe mal von einer EVL aus, die lauter char* als daten hat. leg einen char** an und kopiere alle char* der EVL dort rein. dann sortiere das zeigerfeld. dann kopiere die zeiger plump von anfang bis ende wieder in die liste rein.

das sortieren wäre optimal mit einem drei-wege-quicksort. aber naja, mir scheint beinahe, du legst keinen riesigen wert darauf, ein oder zwei wochen am besten verfahren zu knobeln und wärst über ein intro-sort (besser als einfaches quicksort) in 5 minuten ganz froh.

//ungetestet, nur so reingehackt.
struct StrLess{
   bool operator()(char const* a,char const* b){
      return strcmp(a,b)<0;
   }
};
void sortiereMeineEVL(ListElement_char* anfang){
//zählen
   int anzahl=0;
   for(ListElement_char* i=anfang;i!=0;i=i->next)
      ++anzahl;

//feld anlegen
   char** feld=new (char*)[anzahl];

//reinkopieren
   anzahl=0;
   for(ListElement_char* i=anfang;i!=0;i=i->next){
      feld[anzahl]=i->data;
      ++anzahl;
   }

//blitzschnell sortieren
   sort(feld,feld+anzahl,StrLess);

//rauskopieren
   anzahl=0;
   for(ListElement_char* i=anfang;i!=0;i=i->next){
      i->data=feld[anzahl]=;
      ++anzahl;
   }

//feld löschen
   delete[] feld;
}

c147258

volkard (forum kaputt?) schrieb:

die schaufelst du ein eine EVL um und machst char* aus den VARIANTs. machste das nur, um zu sortieren, oder ist die EVL auch als ausgangsdaten gefordert?

das mach ich weil ich dachte das es schneller sei das ganze in eine Liste zu schreiben weil ich jedes mal nur ein Element anhänge - da ist die Liste ja bekanntlich schneller "hoff ich halt" - zudem ist ja auch dann das sortieren schneller (siehe deinen Post weiter oben)

volkard (forum kaputt?) schrieb:

normaler wäre nämlich ein char**. also das, was zwischendurch in meiner funktion (siehe unten) benutzt wird.

Danke...werd ich versuchen das ich es hinbekomme

volkard (forum kaputt?) schrieb:

aber naja, mir scheint beinahe, du legst keinen riesigen wert darauf, ein oder zwei wochen am besten verfahren zu knobeln und wärst über ein intro-sort (besser als einfaches quicksort) in 5 minuten ganz froh.

Jop, weil ich ab 31. Juli nicht mehr da bin -> Ferialarbeit

Werde deinen Code mal ausprobieren ..danke!

c147258 schrieb:

das mach ich weil ich dachte das es schneller sei das ganze in eine Liste zu schreiben weil ich jedes mal nur ein Element anhänge - da ist die Liste ja bekanntlich schneller "hoff ich halt" - zudem ist ja auch dann das sortieren schneller (siehe deinen Post weiter oben)

um ein element anzuhängen hat man bei einer liste die kosten von einem new. new ist aber gar nicht so extrem schnell in c++. zeitkomplexität O(n) mit großem faktor.

alternativ könntest du ein array nehmen, und jedesmal, wenn du ein objekt einfügst, einen um ein element größeres array mit new anlegen und alle alten elemente ins neue kopieren und das neue element ans ende schreiben. macht auch nur n mal operator new aufrufen. aber n*(n-1) mal muß ein zeiger kopiert werden. zeitkomplexität O(n^2), also grottenlahm.

alternativ könntest du ein array nehmen, das auch mal ein wenig größer ist, als du sofort brauchst. dan schreibst so lange ins array, bis es voll ist. dann legste ein array an, das DOPPELT so groß ist wie das alte und kopierst die elemete des alten rein und schreibst ab dann wieder hinten dran, bis auch das voll ist und läßt wieder wachsen...
so mußte für 1000000 elemete nur 20-mal wachsen lassen. also nur 20-mal operator new und nur maximal 2000000 mal einen zeiger kopieren. das ist also O(n) mit sehr kleinem faktor. es ist einfach schnell.

zum vergelich zwischen listen und arrays ist also zu sagen, daß arrays einfach schneller sind. nur einen unterschied gibt's: die liste wächst immer gleich schnell. immer einmal new und gut ist's. das array wächst viel schneller, außer ganz selten, da muß das ganze array umkopiert werden. willste also in einem 3d-echtzeit-game was wachsen lassen, würde es beim array manchmal ruckeln, immer wenn das array mal wachsen muss. aber dazwischen wäre es geil schnell, was aber dem benutzer recht egal ist. er braucht gleichmäßige performance und kein ruckeln. wenn der benutzer eh waren muss, bis alles eingelesen ist, dann ist das array vorzuziehen, weil es schneller ist. und überhaupt, für den programmierer ist es auch einfacher. und du hast netterweise die daen dann gleich in einem array vorliegen, was optimal zum sortieren ist.

es gibt noch eine kombination, die noch mehr bringt. kleine arrays, sagen wir mal immer 4k. genauer 1023 nutzzeiger und einen verkettungszeiger. du machst das kleine array voll und wenn es voll ist, wirste, statt es wachsen zu lassen, ein neues kleines array anlegen und es mit dem alten array verketten. also eine verkettete liste, deren daten lauter kleine arrays sind. da haste nur alle 1023 einfügunen einmal new. also ungefähr nx. und braucht auch nix zu kopieren. das ist zum einlesen allein gesehen optimal. aber dann kommt ja wieder das sortieren. du müßtest entweder merge-sort nehmen, weil das für diese datenstruktur ungemein passend ist, würdest dabei aber, schätze ich mal, bei großen datenmengen doch langsamer als introsort sein, oder du müßtest, wie beim bisherigen plan erst umkopieren, und dann wäre die einfache array-lösung wieder besser.

c147258

Vielen Dank für Eure hilfe...

Muss jedoch eine kleine Statusänderung vornehmen:
Wollte heute BSTR in die Liste kopieren - jedoch werden diese immer wieder überschrieben - gleiche Adresse

Somit werde ich Integer/Double Werte welche aus dem VARIANT Datentyp kommen in eine standard Liste reinschreiben - also mit push_front(VARIANT) - somit brauch ich nicht meine eigenen Fkt für die DVL/EVL verwenden und kann auf die Bibliothek zurückgreifen.

Wenn jedoch ein String kommt (sprich BSTR) aus VARIANT werd ich ihn ebenfalls in eine Liste kopieren - jedoch nicht als VARIANT sondern schon als CHAR *.

Bei den Integer/Double werten kopieren ich zur Zeit die ganzen Werte aus der liste in ein Array und dieses wird dann sortiert. Liste ist auch praktisch da ich dann sofort ein Array mit fixer Größe anlegen kann. -
Wie würde ich sonst die größe des Arrays bekommen (bzw. müsste jedes Mal mit malloc/allco Speicher frei geben um das nächste Element reinschreiben zu können..

Bei den Strings/Char* werde ich Volkards Methode anwenden (wenn ich es hinbekomme :D) oder gibt es auch noch andere Vorschläge - einfachere/schnellere
hier müsste ich ja eine Matrix anwenden, jedoch hätte das auch keinen Sinn - da die Char * nicht immer genau gleich lang sind und somit würde unnötig Speicher freigegeben.

Danke!

c147258

c147258 schrieb:

Somit werde ich Integer/Double Werte welche aus dem VARIANT Datentyp kommen in eine standard Liste reinschreiben - also mit push_front(VARIANT) - somit brauch ich nicht meine eigenen Fkt für die DVL/EVL verwenden und kann auf die Bibliothek zurückgreifen.

hmm..dacht ich zuerst das mit der Standard Liste - jedoch drängt die Zeit, und das alles wieder umzustellen :(...zudem kenn ich mich bei meiner Liste bzgl. Pointer zugriff besser aus - bei der anderen Liste müsste ich das ja mit einem Iterator machen

Danke

c147258

@volkard

Wäre dir sehr dankbar wenn du mir nochmals helfen könntest

//feld anlegen
char** feld= new (char*)[anzahl];

error C2143: Syntaxfehler : Fehlendes ';' vor '['
error C2143: Syntaxfehler : Fehlendes ';' vor '['

void insertionSort(int numbers[], int array_size)
{
  int i, j, index;

  for (i=1; i < array_size; i++)
  {
    index = numbers[i];
    j = i;
    while ((j > 0) && (numbers[j-1] > index))
    {
      numbers[j] = numbers[j-1];
      j = j - 1;
    }
    numbers[j] = index;
  }
}

//blitzschnell sortieren
sort(feld, feld+anzahl, StrLess);

error C2275: "StrLess" : Ungültige Verwendung dieses Typs als Ausdruck

Wie müsste ich nun die Sort Funktion umschreiben, damit es funktioniert?
(meine Vorschläge kommen gleich)

insertionSort(feld, feld+anzahl, StrLess);

Warum wird hier feld + anzahl gerechnet?

Wäre dir sehr dankbar...irgendwie fehlt es mir an der Logik

Polofreak

Hab zwar nicht alles gelesen, aber du scheinst Probleme mit dem Quicksort zu haben, ich hätte dir ein kleines Template das ich momentan verwende.

Und schau doch mal hier
allerdings hat da das Quicksort bei mir nicht funktioniert, aber erklärt ist es nicht schlecht.

c147258

Hallo,

Danke - Quicksort funktioniert jedoch schon, aber mit InterationSort gibts probleme - siehe letzten Post oben von mir ...

c147258

Hallo
ist es möclich eine einfach verkettete Liste mit einem Array(Mehrdimensional) zu vergleichen?

//
// EVL - String - Char
//

typedef struct LISTELEMENT_CHAR{
    char *data;
    struct LISTELEMENT_CHAR *next;
}ListElement_char;

void insertionSort(char **string, int array_size)
{
  int i, j;
  char *index = NULL;

  for (i=1; i < array_size; i++)
  {
	strcpy(index, string[i]);
    //index[0] = string[i];
    j = i;
    while ((j > 0) && (strcmp(string[j-1], index)))
    {
	  strcpy(string[j], string[j-1]);
      //string[j] = string[j-1];
      j = j - 1;
    }
	strcpy(string[j], index);
    //string[j] = index;
  }
}

Wie jedoch sollte der Aufruf lauten?

insertionSort(temp_char->data, counter);

Denke nicht das es möglich ist, oder?
Wie sollte ich es sonst vergleichen?

Danke