Structur Arrays sortieren

[Hunter666]

Hallo, ich hab da nen Problem

also ich hab eine Structur

struct mita
{
    String name;
    int id;
}pers[200];

so, jetzt möchte ich diese 200 personen sortieren lassen und zwar nach alphabetischer reienfolge des Namens, aber ohne die ID der zugehörigen person zu ändern.
Da wir 70000 dieser Datensätze aufeinmal sortieren müssen, ist Bubblesort dafür etwas zu langsam. Ich habs mit folgendem probiert:

int scmp(const void *s1, const void *s2)
{
return(strcmp((const char*)s1, (const char*)s2));
}

void main()
{
qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), scmp);
}

das war ein Vorschlag eines anderen Forum, der aber nur
char arr[6][4];
strings verarbeitet.

Ich kann aber net die ID´s dazu so speichern, dass ich die Personen sortiert ausgeben kann und doch "unsortiert" gespeichert habe (ID).

Versteht jemand mein Problem?
Könnt ihr mir helfen? Ich weiß ist wahrscheinlich irgendein simpler sortieralgorhitmus doch ich komm einfach net weiter

[AndreasW]

Hi,

Du solltest dich ein wenig mehr mit der STL beschäftigen. Die ist für so was bestens geeignet. Hier ein paar Anregungen und Einstiegshilfen:

Anstatt eines festen Arrays von 200 nimmt man am besten ein Dynamisches Array. Hierzu kommt (zum Beispiel) aus der STL die List oder ein vector in Frage. Ich zeige die die Handhabung nun an Hand eines Beispieles mit einem vector.

Kämpfen wir uns mal schrittweise an dein Problem ran.

Grundlage:

Ein Momofelder auf ein Formular und ein Button, dann:

#include "Unit1.h"
#include <vector>
#include <algorithm>
#include <string>

//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
using namespace std;
//------------------------------------------------------------

TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
vector<string> S;
S.push_back("Andreas");
S.push_back("Norbert");
S.push_back("Ralf");
S.push_back("Michael");
S.push_back("Bernhard");

std::sort(S.begin(),S.end());
 vector<string>::const_iterator Iter=S.begin();
 do
 {
        Memo1->Lines->Add(String((*Iter).c_str())) ;
 }
 while(++Iter != S.end()) ;
}
//---------------------------------------------------------------------------

Das wäre ein Beispiel, in dem Ein Vektor sortiert werden soll. Sicherlich möchten wir aber nicht immer so sortieren. Oder, wie in deinem Fall ist eine Sortierung von einer Membervariablen der Item-Klasse abhängig.

Nun das Beispiel nur anders rum sortiert:

Dazu müssen wir ein Funktionsobjekt erstellen, welches bei komplizierteren Dingen die STL unterstützen soll. Diese Funktionsobjekte nennt man auch Prädikate.
Es gibt zwei Grund-Arten von Prädikaten.
1. unary_function -> ein Übergabe-Parameter
2. binary_function -> zwei Übergabe-Parameter
Wir wollen zwei Strings vergleichen, damit wir feststellen können, welcher größer ist. Deshalb brauchen wir zwei Übergabeparameter, in denen die beiden Strings übergeben werden. Das es ein String ist, ist egal, da es eine Templatefunktion ist. Der Aufruf sieht dann so aus:

#include "Unit1.h"
#include <vector>
#include <algorithm>
#include <string>

//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
using namespace std;
//------------------------------------------------------------
struct TPerson
{
String Name;
int     ID;
};
//------------------------------------------------------------
// hier ein Prädikat (Funktionsobjekt) welches die eigentliche Sortierung vornehmen soll
template<class T> struct mycom:public binary_function<T,T,bool>
{
  bool operator () (const T& Value1,const T& Value2)const {return Value1>Value2;};
};
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
vector<string> S;
S.push_back("Andreas");
S.push_back("Norbert");
S.push_back("Ralf");
S.push_back("Michael");
S.push_back("Bernhard");

std::sort(S.begin(),S.end(),mycom<string>()); // sortieren mit dem Funktionsobjekt
Iter=S.begin();
 do
 {
        Memo2->Lines->Add(String((*Iter).c_str())) ;
 }
 while(++Iter != S.end())     ;
}
//---------------------------------------------------------------------------

so, nun ist der vector anders herum sortiert. Nun kommt das Problem der struktur. Wenn man mal drüber nachdenkt ist es ja eigentlich kein Problem mehr. Aber egal. Hier das Beispiel:

//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
#include <vector>
#include <algorithm>
#include <string>

//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
using namespace std;
//------------------------------------------------------------
struct TPerson
{
String Name;
int     ID;
};
//------------------------------------------------------------
struct sort_by_name:public binary_function<TPerson,TPerson,bool>
{
  bool operator () (const TPerson& Value1,const TPerson& Value2)const {return Value1.Name<Value2.Name;};
};
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
vector<TPerson> S;

TPerson a,b,c,d,e;

a.Name="Andreas";
a.ID=2;
S.push_back(a);
b.Name="Norbert";
b.ID=3;
S.push_back(b);
c.Name="Ralf";
c.ID=4;
S.push_back(c);
d.Name="Michael";
d.ID=5;
S.push_back(d);
e.Name="Bernhard";
e.ID=6;
S.push_back(e);

std::sort(S.begin(),S.end(),sort_by_name());
vector<TPerson>::const_iterator Iter=S.begin();
 do
 {
        Memo2->Lines->Add((*Iter).Name) ;
 }
 while(++Iter != S.end())     ;
}
//---------------------------------------------------------------------------

da kann man noch viele schöne Dinge mehr machen. Dieses soll für dich nur ein Anstoß sein, dich doch in die Höhle des Löwen zu wagen, auch wenn es anfangs als schwere trockene Materie daherkommt.

[AndreasW]

da du mit sicherheit auch nach Personen suchen möchtest, hab ich dir ein Beispiel geschrieben, welches das Prädikat als Klasse implementiert.

Natrülcih kann man sowas auch beliebig anders benutzen. Die Anwendungsmöglichkeiten sind enorm vielfältig:

//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
#include <vector>
#include <algorithm>
#include <string>

//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
using namespace std;
//------------------------------------------------------------
struct TPerson
{
String Name;
int     ID;
};
//----------------------------------------------------------------------
class TPersonsuche :public unary_function <TPerson,bool>
{
 private:
 String FGesuchtePerson;
 public:
 explicit TPersonsuche (const String& APerson) :FGesuchtePerson(APerson){}
 bool operator () (const TPerson& TheTestPerson) const
        {
                return TheTestPerson.Name==FGesuchtePerson;
        }
}  ;
//----------------------------------------------------------------------

TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
vector<TPerson> S;

TPerson a,b,c,d,e;

a.Name="Andreas";
a.ID=2;
S.push_back(a);
b.Name="Norbert";
b.ID=3;
S.push_back(b);
c.Name="Ralf";
c.ID=4;
S.push_back(c);
d.Name="Michael";
d.ID=5;
S.push_back(d);
e.Name="Bernhard";
e.ID=6;
S.push_back(e);
vector<TPerson>::const_iterator Iter;

Iter=find_if(S.begin(),S.end(),TPersonsuche("Michael"));
if(Iter !=S.end())
        Memo1->Lines->Add("Found with ID:" + IntToStr((*Iter).ID));
else
        ShowMessage("Not found :(");
}
//---------------------------------------------------------------------------

[Hunter666]

danke schön, hast dir ja wikrlich sehr viel arbeit gemacht.
werd mir des jetzt alles mal genauer anschauen mit online hilfe und so ... ich denk des klappt dann auch...

[Hunter666]

also, ich hab das jetzt wirklich versucht nachzuverfolgen und so, aber es funktioniert in meinem falle einfach nicht.
Hier mal der Code:

//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
#include <vector>
#include <algorithm>
#include <string>
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
using namespace std;

struct mitarbeiter
{
int     ID;
char    Name[15];
};
mitarbeiter pers[70000];

struct sort_by_name:public binary_function<mitarbeiter,mitarbeiter,bool>
{
  bool operator () (const mitarbeiter& Value1,const mitarbeiter& Value2)const {return Value1.Name<Value2.Name;};
};

TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)
{
        mitarbeiter *ppers[70000];
        vector<mitarbeiter> S;
strcpy(pers[0].Name, "Andreas");
pers[0].ID=2;
S.push_back(pers[0]);
strcpy(pers[1].Name, "Norbert");
pers[1].ID=3;
S.push_back(pers[1]);
strcpy(pers[2].Name, "Ralf");
pers[2].ID=4;
S.push_back(pers[2]);
strcpy(pers[3].Name, "Michael");
pers[3].ID=5;
S.push_back(pers[3]);
strcpy(pers[4].Name, "Hallo");
pers[4].ID=6;
S.push_back(pers[4]);

std::sort(S.begin(),S.end(),sort_by_name());
vector<mitarbeiter>::const_iterator Iter=S.begin();
 do
 {
        Memo1->Lines->Add((*Iter).Name) ;
 }
 while(++Iter != S.end())     ;
}

Er führt es zwar aus, aber sortieren tut er es nur rückwärts, d.h. er fängt mit pers[4].name an und gibt die Namen der Reihenfolge nach rückwärts aus.
Kann mir da nochmal jemand helfen?

[AndreasW]

Hi,

das liegt daran, dass er char Name[15] binär sortiert.

mit char:

Hallo
Michael
Ralf
Norbert
Andreas

mit string:

Andreas
Hallo
Michael
Norbert
Ralf

Du must eine Klasse/Typ nehmen, das die Operatoren < > überschrieben hat, oder selbst ein Typ nehmen und die Operatoren überschreiben.
Bei string uns AnsiString sind die Operatoren überschrieben. Deshalb kannst du besser std::string oder AnsiString nehmen.

Dieses Problem taucht bei den Grundtypen aber glaub ich nur bei literalen auf.

Überigens brauchst du das Array dafür nicht mehr.

Hier nochmal das Beispiel mit string:

//---------------------------------------------------------------------------

#include <vcl.h> 
#pragma hdrstop 

#include "Unit1.h" 
#include <vector> 
#include <algorithm> 
#include <string> 
//--------------------------------------------------------------------------- 
#pragma package(smart_init) 
#pragma resource "*.dfm" 
using namespace std; 

struct mitarbeiter 
{ 
int     ID; 
string    Name;
}; 
mitarbeiter pers[70000]; 

struct sort_by_name:public binary_function<mitarbeiter,mitarbeiter,bool> 
{ 
  bool operator () (const mitarbeiter& Value1,const mitarbeiter& Value2)const {return Value1.Name<Value2.Name;}; 
}; 

TForm1 *Form1; 
//--------------------------------------------------------------------------- 
__fastcall TForm1::TForm1(TComponent* Owner) 
        : TForm(Owner) 
{ 
} 
//--------------------------------------------------------------------------- 

void __fastcall TForm1::Button1Click(TObject *Sender) 
{
mitarbeiter pers;

vector<mitarbeiter> S;

pers.Name= "Andreas";
pers.ID=2;
S.push_back(pers);
pers.Name= "Norbert";
pers.ID=3;
S.push_back(pers);
pers.Name= "Ralf";
pers.ID=4;
S.push_back(pers);
pers.Name= "Michael";
pers.ID=5;
S.push_back(pers);
pers.Name= "Hallo";
pers.ID=6;
S.push_back(pers);

std::sort(S.begin(),S.end(),sort_by_name()); 
vector<mitarbeiter>::const_iterator Iter=S.begin(); 
 do 
 { 
        Memo1->Lines->Add((*Iter).Name.c_str()) ;
 } 
 while(++Iter != S.end())     ; 
}

[AndreasW]

oder eine Variante mit Pointer:

//---------------------------------------------------------------------------

#include <vcl.h> 
#pragma hdrstop 

#include "Unit1.h" 
#include <vector> 
#include <algorithm> 
#include <string> 
//--------------------------------------------------------------------------- 
#pragma package(smart_init) 
#pragma resource "*.dfm" 
using namespace std; 

struct mitarbeiter 
{ 
int     ID; 
string    Name;
mitarbeiter(int AID,string AName):ID(AID),Name(AName){};  // konstruktor ändern
};

struct sort_by_name:public binary_function<mitarbeiter*,mitarbeiter*,bool>
{ 
  bool operator () (const mitarbeiter* Value1,const mitarbeiter* Value2)const {return Value1->Name<Value2->Name;};
}; 

TForm1 *Form1; 
//--------------------------------------------------------------------------- 
__fastcall TForm1::TForm1(TComponent* Owner) 
        : TForm(Owner) 
{ 
} 
//--------------------------------------------------------------------------- 

void __fastcall TForm1::Button1Click(TObject *Sender) 
{
mitarbeiter* pers;

vector<mitarbeiter*> S;
S.push_back(new mitarbeiter(2,"Andreas"));
S.push_back(new mitarbeiter(3,"Norbert"));
S.push_back(new mitarbeiter(4,"junix"));
S.push_back(new mitarbeiter(5,"Jansen"));
S.push_back(new mitarbeiter(6,"Marcus"));

std::sort(S.begin(),S.end(),sort_by_name());
vector<mitarbeiter*>::iterator Iter=S.begin();
 do 
 { 
        Memo1->Lines->Add((*Iter)->Name.c_str()) ;
 } 
 while(++Iter != S.end())     ; 
}

nicht vergessen den Vector spter durfchzugehen und den Speicherplatz wieder freizugeben.

[Hunter666]

Danke, deine Hilfe war wirklich sehr ... hmm... hilfreich!
Danke schön nochmal geht wirklich unbeschreiblich schneller als Bubblesort

[milkywatch]

AndreasW schrieb:

//---------------------------------------------------------------------------
 
#include <vcl.h> 
#pragma hdrstop 
 
#include "Unit1.h" 
#include <vector> 
#include <algorithm> 
#include <string> 
//--------------------------------------------------------------------------- 
#pragma package(smart_init) 
#pragma resource "*.dfm" 
using namespace std; 
 
struct mitarbeiter 
{ 
int     ID; 
string    Name;
}; 
mitarbeiter pers[70000]; 
 
 
struct sort_by_name:public binary_function<mitarbeiter,mitarbeiter,bool> 
{ 
  bool operator () (const mitarbeiter& Value1,const mitarbeiter& Value2)const {return Value1.Name<Value2.Name;}; 
}; 
 
TForm1 *Form1; 
//--------------------------------------------------------------------------- 
__fastcall TForm1::TForm1(TComponent* Owner) 
        : TForm(Owner) 
{ 
} 
//--------------------------------------------------------------------------- 
 
void __fastcall TForm1::Button1Click(TObject *Sender) 
{
mitarbeiter pers;

vector<mitarbeiter> S;

pers.Name= "Andreas";
pers.ID=2;
S.push_back(pers);
pers.Name= "Norbert";
pers.ID=3;
S.push_back(pers);
pers.Name= "Ralf";
pers.ID=4;
S.push_back(pers);
pers.Name= "Michael";
pers.ID=5;
S.push_back(pers);
pers.Name= "Hallo";
pers.ID=6;
S.push_back(pers);

std::sort(S.begin(),S.end(),sort_by_name()); 
vector<mitarbeiter>::const_iterator Iter=S.begin(); 
 do 
 { 
        Memo1->Lines->Add((*Iter).Name.c_str()) ;
 } 
 while(++Iter != S.end())     ; 
}

Wieso bekommt ihr das alle zum laufen? Ich bekomme da ein:
[C++ Fehler] Unit1.cpp(23): E2303 Typname erwartet
[C++ Fehler] Unit1.cpp(23): E2275 { erwartet
[C++ Fehler] Unit1.cpp(23): E2170 Klasse wurde von Basisklasse 'mitarbeiter' mehr als einmal abgeleitet.
[C++ Fehler] Unit1.cpp(23): E2272 Bezeichner erwartet
[C++ Warnung] Unit1.cpp(24): W8024 Basisklasse 'mitarbeiter' ist auch eine Basisklasse von 'mitarbeiter'.
[C++ Warnung] Unit1.cpp(24): W8024 Basisklasse 'mitarbeiter' ist auch eine Basisklasse von 'mitarbeiter'.

Zeile 23: struct sort_by_name:public binary_function<mitarbeiter,mitarbeiter,bool>

Kann da wer helfen und danke an AndreasW der sich hier wirklich grosse Mühe gegeben hat

[akari]

Hallo

es fehlt noch

#include <functional>

Hättest du auch rausfinden können, indem du mal im Quelltext auf binary_function gehst und F1 drücksts.

bis bald
akari

[milkywatch]

ähm. ja. ähm. ups!
*sich in Ecke verkriech* Peinlich, peinlich!

Auf jedenfall Danke schön!