STL sort schlagen

japro

ich versuch gerade das stl sort zu schlagen genaugenommen hab ichs schon geschaft... (jedenfalls geringfügig schneller als das vom mingw)
hat noch wer ideen zum optimieren?

template<class T> void subSort(T *begin,T *end)//quicksort das zur groben sortierung verwendet wird
{
 T med[3] = {*begin, *(begin+1), *end};
 med[1]=(med[0]<med[1])?med[1]:med[0];
 med[1]=(med[1]<med[2])?med[1]:med[2];
 T vgl = med[1];

 T *obegin = begin, *oend = end;
 do
 {

  while(*begin < vgl) ++begin;
  while(*end > vgl) --end;
  if (begin <= end)
  {
   T tmp = *begin;
   *begin = *end;
   *end = tmp;

   ++begin;
   --end;
  }

 }while(begin <= end);

 if ((end-obegin) > 32) subSort(obegin,end);
 if ((oend-begin) > 32) subSort(begin,oend);
}

template<class T> void mysort(T *begin,T *end) //eigentlich sortier funktion
{
 end--; //für aufrufkompatibilität zu stl sort
 subSort(begin,end);

 for(++begin ; begin<=end ; begin++) //insertion zum aufräumen
 {
  T vgl = *begin;
  T *temp = begin;
  while(*(temp-1) > vgl)
  {
   *temp = *(temp-1);
   temp--;
  }
  *temp = vgl;
 }
}

[ Dieser Beitrag wurde am 02.07.2002 um 16:29 Uhr von japro editiert. ]

volkard

Finde ne Doku zu Intro-Sort. Und gib sie mir dann auch. Erst dann haben wir ne Chance.

SideWinder

Frage: Welchen Sortieralgorihtmus benützt eigentlich std::sort() - ist da einer durch den Standard vorgegeben, oder gehts hier nur um Geschwindigkeit?

E: So wie ich das gesehen habe, verwendet japro zumindest eine Kombi zwischen Quick-Sort und Intersection-Sort.

@volkard: Ob der gute alte BubbleSort hier was zu suchen hat? Man könnte ihn zumindest einmal antreten lassen ... der war zumindest schon bis ans Limit geschraubt.

MfG SideWinder

[ Dieser Beitrag wurde am 28.06.2002 um 23:31 Uhr von SideWinder editiert. ]

volkard

Antreten lassen?
ok.
Sorry, ist bestimmt wieder nonstandard MS-Code. Hab ich mal für mich gebaut und grad ausgegraben.
Also zum Messen hatt ich das hier

#include <iostream>
#include <windows.h>
#include <time.h>
#include <algorithm>
using namespace std;

void copy(int *dst,int size,int *src)
{
        for(int i=0;i<size;++i)
                dst[i]=src[i];
}
void merge_imp(int *feld,int startA,int startB,int startC,int *tmpFeld)
{
        int schreibIndex=0;
        int posA=startA;
        int posB=startB;

        while(!(posA==startB && posB==startC))//solange nicht A und B leer sind
        {
                if(posA==startB)//Wenn A leer ist, aus B lesen
                        tmpFeld[schreibIndex++]=feld[posB++];
                else if(posB==startC)//Wenn B leer ist, aus A lesen
                        tmpFeld[schreibIndex++]=feld[posA++];
                else//Ansonsten den kleinsten lesen
                        if(feld[posA]<feld[posB])//Wenn bei A der kleinere ist, aus A lesen
                                tmpFeld[schreibIndex++]=feld[posA++];
                        else//Sonst aus B lesen
                                tmpFeld[schreibIndex++]=feld[posB++];
        }
}
void merge(int *feld,int startA,int startB,int startC,int *tmpFeld)
{
        merge_imp(feld,startA,startB,startC,tmpFeld);
        copy(&feld[startA],startC-startA,tmpFeld);
}
void mergesort(int *feld,int startA,int startC,int *tmpFeld)
{
        if(startC-startA<=1)
                return;
        int startB=(startA+startC)/2;
        mergesort(feld,startA,startB,tmpFeld);
        mergesort(feld,startB,startC,tmpFeld);
        merge(feld,startA,startB,startC,tmpFeld);
}
void mergesort(int *feld,int size)
{
        int *tmpFeld=new int[size];
        mergesort(feld,0,size,tmpFeld);
        delete tmpFeld;
}

//Unbedingt anschauen!!!
//http://hissa.nist.gov/dads/terms.html

//vertauscht zwei int-Zahlen
void swap(int &a,int &b)
{
        int tmp=a;
        a=b;
        b=tmp;
}

//Zeigt Array an
void print(int *a,int SIZE)
{
        for(int i=0;i<SIZE;++i)
                cout<<a[i]<<' ';
        cout<<endl;
}

void standardSort(int *a,int size)
{
        std::sort(a,a+size);
}

//Typ einer Sortierfunktion
//Zweck: Wird dann f│r die Zeiger auf Funktionen gebraucht
typedef void sortFunk(int *a,int size);

//Das ganz normale Bubble-Sort
void bubbleSort(int *a,int size)
{
        for(int r=size-1;r>0;--r)
                for(int l=0;l<r;++l)
                        if(a[l]>a[l+1])
                                swap(a[l],a[l+1]);
}

//Verbesserung: Vorsortierung wird erkannt
//Wie man sieht, ist der Effekt gering und bei gro»en Feldern 
//nicht mehr sp│rbar
void bubbleSort2(int *a,int size)
{
        for(int r=size-1;r>0;)
        {
                int newR=0;
                for(int l=0;l<r;++l)
                        if(a[l]>a[l+1])
                        {
                                newR=l;
                                swap(a[l],a[l+1]);
                        }
                r=newR;
        }
}

//Selection Sort.
//Die Performance ist bemerkenswert!
int findMin(int *a,int size)
{
        int minIndex=0;
        for(int i=1;i<size;++i)
                if(a[i]<a[minIndex])
                        minIndex=i;
        return minIndex;
}
void selectionSort(int *a,int size)
{
        for(int r=0;r<size;++r)
        {
                int minIndex=findMin(a+r,size-r)+r;
                swap(a[minIndex],a[r]);
        }
}

//Insertion Sort
void insertionSort(int *a,int size)
{
        for(int r=1;r<size;++r)
        {
                int l=r-1;
                while(l>=0 && a[l]>a[l+1])
                {
                        swap(a[l],a[l+1]);
                        --l;
                }
        }
}

//heapSort
//Quelle: http://artemis.simmons.edu/~tis/cs232/stl/sources/ReadMe.html 
void adjust_heap (int *start, unsigned heapSize, unsigned position)
{
        while (position < heapSize) {
                // replace position with the larger of the 
                // two children, or the last element
                unsigned int childpos = position * 2 + 1;
                if (childpos < heapSize) {
                        if ((childpos + 1 < heapSize) &&
                                start[childpos + 1] > start[childpos])
                                        childpos += 1;
                        if (start[position] > start[childpos]) {
                                return;
                                }
                        else {
                                swap (start[position], start[childpos]);
                                }
                        }
                position = childpos;
                }
}
void make_heap (int *start, int *stop)
{
        unsigned int heapSize = stop - start;
        for (int i = heapSize / 2; i >= 0; i--)
                        // assume children of node i are heaps
                adjust_heap(start, heapSize, i);
                        // inv: tree rooted at node i is a heap
        // assert: structure is now a heap
}
void sort_heap (int *start, int *stop)
{
        unsigned int lastPosition = stop - start - 1;
        while (lastPosition > 0) {
                swap(start[0], start[lastPosition]);
                adjust_heap(start, lastPosition, 0);
                lastPosition--;
                }
}
void heapSort(int *start, int size)
{       // sort the vector argument using a heap algorithm
        int *stop=start+size;

        // first build the initial heap
        make_heap (start, stop);

        // then convert heap into sorted collection
        sort_heap (start, stop);
}

//ShellSort
void insertionSortWithStep(int *a,int size,int step)
{
        for(int r=step;r<size;r+=step)
        {
                int l=r-step;
                while(l>=0 && a[l]>a[l+step])
                {
                        swap(a[l],a[l+step]);
                        l-=step;
                }
        }
}
void shellSort(int *a,int size)
{
        int step=size/2;
        while(step>0)
        {
                for(int i=0;i<step;++i)
                        insertionSortWithStep(a+i,size-i,step);
                step/=2;
        }
}
void shellSort2(int *a,int size)
{
        int step=1;
        while(step<size)
                step=3*step+1;

        step/=3;
        while(step>0)
        {
                for(int i=0;i<step;++i)
                        insertionSortWithStep(a+i,size-i,step);
                step/=3;
        }
}

//QuickSort
//Eine ausgesprochen trickreiche Implementierung
void quickSort_imp(int *a,int l,int r)
{
        if(r<=l)
                return;
        int i=l-1;
        int j=r;
        int v=a[r];
        for(;;)
        {
                while(a[++i]<v);
                while(a[--j]>v);
                if(i>=j)
                        break;
                swap(a[i],a[j]);
        }
        swap(a[i],a[r]);
        quickSort_imp(a,l,i-1);
        quickSort_imp(a,i+1,r);
}
void quickSort(int *a,int size)
{
        int minIndex=findMin(a,size);
        swap(a[0],a[minIndex]);
        quickSort_imp(a,1,size-1);
}

void quickSort2_impR(int *l,int *r)
{
        if(r<l+25) return;
        int *i=l-1;
        int *j=r;
        for(;;)
        {
                while(*++i<*r);
                while(*--j>*r);
                if(i>=j) break;
                swap(*i,*j);
        }
        swap(*i,*r);
        quickSort2_impR(l,i-1);
        quickSort2_impR(i+1,r);
}
void quickSort2_imp(int *l,int *r)
{
        if(r<=l) return;
        int *i=l-1;
        int *j=r;
        for(;;)
        {
                while(*++i<*r);
                while(j>=l && *--j>*r);
                if(i>=j) break;
                swap(*i,*j);
        }
        swap(*i,*r);
        quickSort2_imp(l,i-1);
        quickSort2_impR(i+1,r);
}

void quickSort2(int *a,int size)
{
        quickSort2_imp(a,a+size-1);
        for(int *r=a+2;r<a+size-1;++r)
                for(int *l=r;*(l-1)>*l;--l)
                        swap(*l,*(l-1));
}

void mergesort2(int *feld,int startA,int startC,int *tmpFeld)
{
        if(startC-startA<=25)
        {
                quickSort(feld+startA,startC-startA);
                return;
        }
        int startB=(startA+startC)/2;
        mergesort2(feld,startA,startB,tmpFeld);
        mergesort2(feld,startB,startC,tmpFeld);
        merge(feld,startA,startB,startC,tmpFeld);
}
void mergesort2(int *feld,int size)
{
        int *tmpFeld=new int[size];
        mergesort2(feld,0,size,tmpFeld);
        delete tmpFeld;
}
//Testet, ob Array sortiert ist
bool isSorted(int *a,int SIZE)
{
        for(int i=0;i<SIZE-2;++i)
                if(a[i]>a[i+1])
                        return false;
        return true;
}

void fillRandom(int *a,int SIZE)
{
    for(int i=0;i<SIZE;++i)
        a[i]=rand();
}

typedef __int64 i64;

i64 getTime()
{
    LARGE_INTEGER time;
    QueryPerformanceCounter(&time);
    return time.QuadPart;
}
typedef void sortFunk(int *a,int size);
i64 checkTimeOnce(sortFunk *sf,int *a,int size)
{
    i64 start=getTime();
    (*sf)(a,size);
    i64 stop=getTime();
    return stop-start;
}
double prozentAbweichung(i64 min,i64 max)
{
    i64 diff=max-min;
    if(diff==0)
        return 0;
    return 100.0/(min/diff);
}

i64 checkTime(sortFunk *sort,const int *a,int size)
{
    const double MAX_ABWEICHUNG=1;
    const int TIMES_SIZE=10;
    i64 times[TIMES_SIZE];
    for(int i=0;i<TIMES_SIZE;++i)
        times[i]=_I64_MAX;
    int *data=new int[size];
    do
    {
        for(i=0;i<size;++i)
            data[i]=a[i];
        i64 t=checkTimeOnce(sort,data,size);
        if(!isSorted(data,size))
            throw "Fehler";
        if(t<times[TIMES_SIZE-1])
        {
            int i=TIMES_SIZE-1;
            times[i]=t;
            while(i>0 && times[i]<times[i-1])
            {
                swap(times[i],times[i-1]);
                --i;
            }
            for(int x=0;x<TIMES_SIZE;++x)
                cout<<int(times[x])<<' ';
            cout<<prozentAbweichung(times[0],times[TIMES_SIZE-1])<<' '<<'\r';
        }
    }while(prozentAbweichung(times[0],times[TIMES_SIZE-1])>MAX_ABWEICHUNG);
    delete[] data;
    return times[0];
}
struct SortAlgorithm
{
    sortFunk *funk;
    const char *name;
    int overcount;
};
void table(int max,int step,SortAlgorithm *sorts,int sortsSize)
{
    cout<<"Anzahl\t";
    i64 maxI=_I64_MAX;
    for(int i=0;i<sortsSize;++i)
    {
        sorts[i].overcount=0;
        int *a=new int[max];
        fillRandom(a,max);
        cout<<sorts[i].name<<'\t';
        i64 t=checkTime(sorts[i].funk,a,max);
        if(t<maxI)
        {
            maxI=t;
        }
        delete[] a;
    }
    cout<<'\n';
    for(int size=step;size<=max;size+=step)
    {
        cerr<<size<<endl;
        cout<<size<<'\t';
        time_t start=clock();
        int *a=new int[size];
        fillRandom(a,size);
        for(int i=0;i<sortsSize;++i)
        {
            if(sorts[i].overcount<10)
            {
                i64 t=checkTime(sorts[i].funk,a,size);
                if(t<maxI*2)
                    cout<<int(t)<<'\t';
                else
                {
                    ++sorts[i].overcount;
                    cout<<int(maxI*2)<<'\t';
                }
            }
            else
                cout<<int(maxI*2)<<'\t';
        }
        cout<<endl;
        delete[] a;
    }
}
#define lengthof(x) (sizeof(x)/sizeof(x[0]))
#define S(x) {x,#x}

#include "vSort.h"

void __cdecl main()
{
    SortAlgorithm sorts[]={
        S(bubbleSort),
        S(bubbleSort2),
        S(heapSort),
        S(insertionSort),
        S(mergesort),
        S(mergesort2),
        S(quickSort),
        S(quickSort2),
        S(selectionSort),
        S(shellSort),
        S(shellSort2),
        S(standardSort),
        S(vSort)
    };
    srand(time(0));
//  SetThreadPriority(GetCurrentThread(),THREAD_PRIORITY_BELOW_NORMAL);
//  SetPriorityClass(GetCurrentProcess(),HIGH_PRIORITY_CLASS);
//  for(int i=0;i<20;)
    try
    {
        table(10000,10,sorts,lengthof(sorts));
    }
    catch(char *msg)
    {
        cout<<msg<<endl;
        cin.get();
    }
}

Und ins Rennen geschickt hab ich den hier:

inline void sort(int &a,int &b)
{
    if(a>b)
        swap(a,b);
}
inline void sort(int &a,int &b,int &c)
{
    sort(a,b);
    sort(b,c);
    sort(a,b);
}

template<bool LEFT_GUARDED>
void vInsertionSort(int *a,int *size)
{
    for(int *r=a+1;r<size;++r)
    {
        int *l=r-1;
        if(LEFT_GUARDED)//Wenn sicher ist, da▀ links vom Feld nicht-gr÷▀ere
            //Werte die Suche beenden
            while(*l>*(l+1))
            {
                swap(*l,*(l+1));
                --l;
            }
        else
            while(l>=a && *l>*(l+1))
            {
                swap(*l,*(l+1));
                --l;
            }
    }
}

int qt=30;
template<bool LEFT_GUARDED>
void vSortImp(int *l,int *r)
{
    const int MINSIZE=20;
    while(r-l>=20)
    {
        //a) Der Pivot wird ganz rechts gesetzt. Das garantiert die Terminierung 
        //   der ersten while-Schleife
        //b) Median of 3 als Pivot verhindert worst case bei bereits sortierte Liste
        //c) *l<*r garantiert Terminierung der zweiten Schleife
        //Die Punkte b) und c) werden von diesem sort erledigt
        //Ist nat³rlich nur zuverlõssig bei drei verschiedenen Adressen, aber das ist 
        //sicher wegen r-l>=MINSIZE
        sort(*l,*r,*(l+(r-l)/2));
        int *i=l-1;
        int *j=r;
        for(;;)
        {//Partitionierung
            while(*++i<*r);
            while(*--j>*r);
            if(i>=j)
                break;
            swap(*i,*j);
        }
        swap(*i,*r);//Pivot in die Mitte setzen
        j=i;
        {//Abk³rzung bei vielen gleichen Werten gegen worst case
            while(j<r && *(j+1)==*j)
                ++j;
            while(i>l && *(i-1)==*i)
                --i;
        }
        //Nur ein rek Aufruf, und zwar das kleinere Feld
        //zur Beschrõnkung der Rekursionstiefe auf O(log(N))
        if(i-l<r-i)
        {//rechts wird(bleibt) guarded, ich bleibe wie ich war
            vSortImp<true>(j+1,r);
            r=i-1;
        }
        else
        {//links bleibt, wie es war
            vSortImp<LEFT_GUARDED>(l,i-1);
            l=j+1;
            if(!LEFT_GUARDED)
            {//rechts wird(bleibt) guarded, gegebenefalls duch Wechseln der Funktion
                vSortImp<true>(l,r);
                return;
            }
        }
    }
    //ganz kleine Felder mit was anderem machen
    vInsertionSort<LEFT_GUARDED>(l,r+1);
}
void vSort(int *a,int size)
{
    vSortImp<false>(a,a+size-1);
}

Hoffe, man kann die Kommentare einigermaßen verstehen, die waren nur zum selber begreifen, was los ist, nicht für andere.

HumeSikkins

@volkard
Falls du noch einen Text über Introsort benötigst, sag bescheid dann ich schicke dir ne Mail.

volkard

Original erstellt von HumeSikkins:
@volkard
Falls du noch einen Text über Introsort benötigst, sag bescheid dann ich schicke dir ne Mail.

Ja, bitte.

Gregor

@ Japro : Interessantes Sort! Das scheint so ähnlich zu funktionieren, wie ein Sort, das ich mal in Java geschrieben habe. Den entsprechenden Code findest du in diesem Thread : C# und Linux

Dein Sort wird natürlich sehr viel schneller sein, allein schon dadurch, dass du das in C++ geschrieben hast. Aber vielleicht findest du ja in meinem Code noch ein paar gute Ideen, die du auch bei dir einsetzen kannst.

Im Vergleich zu dem Sort aus java.util.arrays braucht mein Code ungefähr 85-90% der Zeit. Da sollten also schon ein paar gute Ideen drin sein. Wie sieht das denn bei dir im Vergleich zum STL-Sort aus?

[ Dieser Beitrag wurde am 29.06.2002 um 00:54 Uhr von Gregor editiert. ]

japro

erstmal muss ich meine aussagen etwas korrigieren :D. bei meinem sort bin ich nämlich nicht sicher ob man es wie das stl sort verwenden kann bezüglich kontainern und iteratoren, besonders wegen volgenden zeilen:

if ((end-obegin) > 32) subSort(obegin,end);
 if ((oend-begin) > 32) subSort(begin,oend);

das geht mit pointern ganz gut aber ich weiss net wie das bei iteratoren ist.
ausserdem dürfte es langsamer sein als das stl sort wenn es auf schon sortierte oder rückwärts sortierte daten losgelassen wird. weil ich bei der median aus drei methode bis jetzt keine möglichkeit sah das mittlere element ziwschen zwei pointer zu finden (pointerarithmetik erlaubt ja kein / und *).
hat da wer ne idee?

achja und was ist Intro-Sort??? noch nie gehört...

volkard

Original erstellt von japro:
**ausserdem dürfte es langsamer sein als das stl sort wenn es auf schon sortierte oder rückwärts sortierte daten losgelassen wird. weil ich bei der median aus drei methode bis jetzt keine möglichkeit sah das mittlere element ziwschen zwei pointer zu finden (pointerarithmetik erlaubt ja kein / und *).
hat da wer ne idee?
**

begin+(end-begin)/2;
Das / geschieht nur auf nem int.

Gregor

@ Volkard : Kann es da nicht passieren, dass die Adresse, die man sich da berechnet - speziell in diesem Fall - auf keinen Objekt-"Anfang" zeigt, sondern irgendwo z.B. in die Mitte des Speicherplatzes, der von einem Objekt belegt wird? Das sollte doch zu Problemen führen, oder?

...sorry, falls die Frage dumm war! Ich kenne mich ja mit C++ und Pointern nicht aus!

japro

nein da im zusammenhang mit pointerarithmetik immer in der einheit der grösse der jeweiligen types gerechnet wird...
d.h.

int zahlen[100];
zahlen+=50;    //hier wird sozusagen zahlen+50*sizeof(int) gerechnet

dadurch sind die sich ergebenden pointer immer an ensprechenden grenzen ausgerichtet (ausser man castet wie wild in der gegend rum etc.)
zu den vergleichen... ich habs bis jetzt nur mit ints gemacht. da hat meine version bei einem array das mit rand() gefüllt wurde etwa nen durschnittlichen vorsprung von 5%... als noch nicht so der haufen...

Gregor

Ja! OK! Danke! Das habe ich verstanden. Mir ist aber noch nicht klar, ob das mit dem "/" auch klappt, da Volkard meinte, dass das auf einem int arbeitet. Naja! Ich werde das schon rauskriegen, wenn ich demnächst anfange, C++ zu lernen.

Ich hatte bei meinem Sort übrigens auch mal die Median-Variante ausprobiert. Ich habe aber inzwischen vergessen, warum ich diese Variante wieder verworfen hatte. Wahrscheinlich war sie mir nicht schnell genug! Es kann aber auch sein, dass ich die Variante mit dem Element in der Mitte des zu sortierenden Bereiches einfach etwas schöner fand. Ich würde diese Variante an deiner Stelle zumindest mal ausprobieren.

Hast du schonmal mit der 32 rumgespielt und sie testweise durch andere Zahlen ersetzt? Das könnte unter Umständen ein paar Prozent Geschwindigkeitszuwachs bringen. ...bei mir war die 18 optimal!

volkard

(end-begin) ist ein int.

japro

Original erstellt von Gregor:
Hast du schonmal mit der 32 rumgespielt und sie testweise durch andere Zahlen ersetzt? Das könnte unter Umständen ein paar Prozent Geschwindigkeitszuwachs bringen. ...bei mir war die 18 optimal!

jup hab sie auf 64 erhöht
ausserdem hab ich die rekursion rausgenommen subSort sieht jetzt wie folgt aus:

template<class T> void subSort(T *argbegin,T *argend)
{
 T *stack[128]; // 128 sollten reichen da kaum wer mehr als 4 gb sortieren wird
 unsigned stackptr=0;
 stack[stackptr++] = argend;
 stack[stackptr++] = argbegin;

 while(stackptr>0)
 {
  T *begin = stack[--stackptr];
  T *end = stack[--stackptr];

  T med[3] = {*begin, *(begin+(end-begin)/2), *end};
  med[1]=(med[0]<med[1])?med[1]:med[0];
  med[1]=(med[1]<med[2])?med[1]:med[2];
  T vgl = med[1];

  T *obegin = begin, *oend = end;
  do
  {

   while(*begin < vgl) ++begin;
   while(*end > vgl) --end;
   if (begin <= end)
   {
    T tmp = *begin;
    *begin = *end;
    *end = tmp;

    ++begin;
    --end;
   }

  }while(begin <= end);

  if ((end-obegin) > 64)
  {
   stack[stackptr++] = end;
   stack[stackptr++] = obegin;
  }
  if ((oend-begin) > 64)
  {
   stack[stackptr++] = oend;
   stack[stackptr++] = begin;
  }
 }
}

seltsamer weise wird das ganze langsamer wenn ich es inline mache oder in die mysort funktion direkt reinkopiere
leigt vielleicht daran wie der compiler optimiert...

<probier...>

wollts zuerst nicht glauben aber anstatt den median den mittelwert der beiden ersten werte zu nehmen hat noch nen temposchub gebracht... ist nur dann heikel wenn man mit pintern auf objecte arbeitet die überadene operatoren haben für vergeliche sich aber nicht dividieren lassen (mir fällt im moment kein beispiel ein). aber erstmal lass ich den mittelwert drinn. danke für den tip.

Gregor

OK! Ich habe es komplett verstanden, falls es so ist, dass bei end-begin der Abstand der beiden Adressen (in Byte) berechnet wird und dann implizit durch die Größe eines Elements geteilt wird.

Ist das so?

volkard

Original erstellt von japro:
ist nur dann heikel wenn man mit pintern auf objecte arbeitet die überadene operatoren haben für vergeliche sich aber nicht dividieren lassen (mir fällt im moment kein beispiel ein).

string

volkard

Original erstellt von Gregor:
OK! Ich habe es komplett verstanden, falls es so ist, dass bei end-begin der Abstand der beiden Adressen (in Byte) berechnet wird und dann implizit durch die Größe eines Elements geteilt wird.
Ist das so?

JO!

Gerard

Original erstellt von Gregor:
**OK! Ich habe es komplett verstanden, falls es so ist, dass bei end-begin der Abstand der beiden Adressen (in Byte) berechnet wird und dann implizit durch die Größe eines Elements geteilt wird.

Ist das so?**

jup

japro

man beachte den feinen unterschied LOL

Daniel E.

Original erstellt von japro:
**nein da im zusammenhang mit pointerarithmetik immer in der einheit der grösse der jeweiligen types gerechnet wird...
d.h.
int zahlen[100];
zahlen+=50;    //hier wird sozusagen zahlen+50*sizeof(int) gerechnet
**

Das hier ist nicht erlaubt. Ein Array ist kein veränderbarer L-Value und auch kein Zeiger.

Gregor

Moment! Wenn ich das richtig sehe, dann nimmst du jetzt den Median der drei Werte am Anfang, am Ende und in der Mitte des zu sortierenden Bereiches. Lass doch mal den Median ganz weg und nimm einfach den Wert in der Mitte des zu sortierenden Bereiches als Vergleichswert.

Wenn du einen Median nimmst, dann mußt du immer ein paar Vergleiche machen. Die kosten auf jedenfall Zeit. Außerdem kann es sein, dass der Vergleichswert dann der Wert am Anfang oder der Wert am Ende ist. Ich habe nicht genau gesehen, wie das bei dir abläuft, aber bei meinem Algorithmus würde er dann beim Sortieren den Vergleichswert andauernd hin und herschieben, was noch viel mehr Zeit kostet. Es kann aber sein, dass das bei dir anders funktioniert!

Edit : Wenn das mit dem Hin- und Herschieben bei dir nicht der Fall ist, dann sollte die Variante mit Median bei dir wahrscheinlich schneller sein, da das Quicksort dann etwas "gleichmäßiger" abläuft.

[ Dieser Beitrag wurde am 29.06.2002 um 21:41 Uhr von Gregor editiert. ]