eigene methode die mir std::vector sortiert

hi@all
ich will einen mir selber eine methode proggen die mir den std::vector sortiert!
wie kann ich das angehen? läuft das auch so mit speicherbereich kopieren usw???

cu

otze

pseudocode:

int i=0;//entweder
bool changes=true;
while(i<Vector.size()&&changes){
    changes=false;
    if(vector[i]<vector[i+1]){
         std::swap(vector[i],vector[j]);
         changes=true;
    }
    ++i;
}
int i=Vector.size();//oder
bool changes=true;
while(i>0&&changes){
    changes=false;
    if(vector[i+1]<vector[i]){
         std::swap(vector[i],vector[j]);
         changes=true;
    }
    --i;
}

is nur schnell zusammengeschrieben, um das prinzip zu verdeutlichen, auf stil oder performance hab ich jetzt mal net so geachtet^^

achja, dieser suchalgorithmus ist der einfachste, aber er kommt nicht gut mit sehr großen mengen klar,die zeit wächst linear zur anzahl der objekte im Container, da er immer mindestens einmal komplett durchlaufen muss.
normalerweise läuft er aber n+1mal durch, wobei n die anzahl der durchgänge sind, in denen noch was geändert werden konnte.

kleiner tipp: wenn du hinten objekte einfügst, dann sollteste auch rückwerts durch den Vector laufen-sonst haste am ende einen fast exponentialen anstieg der suchzeit-und das will niemand .

Maxi

Und warum denn überhaupt ne eigene Methode?
Bubblesort ist sehr langsam, ich dachte immer das hätte sogar ne quadratisch Durclaufdauer oder so..

Die STL, was macht die eigentlich? QuickSort?

HumeSikkins

Maxi schrieb:

Die STL, was macht die eigentlich? QuickSort?

std::sort ist nur im Zeitverhalten spezifiziert, nicht aber der genau Algorithmus. Viele Implementationen benutzen Introsort.

ich will einen mir selber eine methode proggen die mir den std::vector sortiert!

Was spricht gegen std::sort(vec.begin(), vec.end())?

volkard

otze schrieb:

kleiner tipp: wenn du hinten objekte einfügst, dann sollteste auch rückwerts durch den Vector laufen-sonst haste am ende einen fast exponentialen anstieg der suchzeit-und das will niemand .

naja, wenn ich die worte "suchen" und "sortieren" mal freundlich dahingehend auslege, daß du mit "suchen" eher "einsortieren" und mit "sortieren" eigentlich nen funktionierenden algo meinst, muß ich nur dem "fast exponentiell" widersprechen.
sagen wir mal, es wird hinten angefügt und von vorne nach hinten läuft die innere sortierschleife. die macht pro schleifendurchlauf eine wirksame vertauschung. wir brauchen also ca n vergleiche für einen wirksame vertauschung und ca n^2 vergleiche um das neue element einzufügen und ca .5*n^3 um alles zu sortieren. anderenfalls (mit der schleife von hinten nach vorne) schaffen wir in einem lauf der inneren schleife alle notwendigen vertauscheungen. wir brauchen also ca n vergleiche, um das neue feld einzufügen und ca .5*n^2, um alles zu sortieren. lassen wir mal beisemal .5 weg und vergleichen das mit dem exponentiellen 0.001*2^n mal.

n	n^2	n^3	.001*2^n
1	1	1	0
2	4	8	0
3	9	27	0
4	16	64	0
5	25	125	0
6	36	216	0
7	49	343	0
8	64	512	0
9	81	729	0
10	100	1000	1
20	400	8000	1048
50	2500	125000	1,1259E+12
100	10000	1000000	1,26765E+27
1000	1000000	1E+9	1,0715E+298
10000	1E+8	1E+12	viel
100000	1E+10	1E+15	viel
1000000	1E+12	1E+18	viel

exponentielles wachstum ist böse, grausam und gemein. richtig fies. ich hab netterweise dem exponentiellen wachstum nen vorfaktor von 0.001 gegeben, als würde dieser sortieralgo auf nem rechner mit 1000Ghz antreten gegen die anderen algos auf nem rechner mit 1Ghz. und es bringt nix. irgendwo zwischen 20 und 50 kann man ihn langsam vergessen und bei 100 isser schon so lahm, daß er länger braucht. als der rechner lebt, auf dem er laufen sollte.

das wort "exponentiell" ist so unerhört schrecklich, daß es nicht leichtfertig verwendet werden sollte um einen ein wenig tapsigen kubischen alsgo zu beschimpen.

hi@all:
wie ist std::list sort denn prog. auch QuickSort????
vielleicht sollte man das beispiel in QuickSort ändern, sonst gibts e keinen allgo. der besser ist, also schneller?

cu

Hab mal vor einiger Zeit nen Alg. programmiert. Evtl. hilfts weiter:

//---------------------------------------------------------------------------
int TBase::StringComp(int Srcs, int Dest) //Vergleismethode für Strings
{
char StringA[WORDSIZE];
char StringB[WORDSIZE];

strncpy(StringA,Array[Srcs].Name,WORDSIZE);
strncpy(StringB,Array[Dest].Name,WORDSIZE);

LowerCase(StringA);
LowerCase(StringB);

return strcmp(StringA, StringB);
}
//---------------------------------------------------------------------------
void TBase::Sortiere(int links, int rechts) // Quicksort
{
int ptr1 = links;
int ptr2 = rechts;
int x = links + (rechts - links)/2;   // Mittleres Element

do
 {
  while(StringComp(ptr1, x) < 0) ptr1++;
  while(StringComp(ptr2, x) > 0) ptr2--;
  if(ptr1 > ptr2)
   {
    break;
   }
  swap(Array[ptr1],Array[ptr2]);
 } while(++ptr1 <= --ptr2);
if(links < ptr2)
 {
  Sortiere(links, ptr2);
 }
if(ptr1 < rechts)
 {
  Sortiere(ptr1, rechts);
 }
}
//---------------------------------------------------------------------------

See ya.