schönes quicksort in C :D

Drakos

Wenn ich mich nicht täusche, ist aber heapsort generell nicht langsamer als quicksort, also im best case mind. gleich und im worst case schneller. der irre ich mich da?

japro

Drakos schrieb:

Wenn ich mich nicht täusche, ist aber heapsort generell nicht langsamer als quicksort, also im best case mind. gleich und im worst case schneller. der irre ich mich da?

prinzipiell ist es so das quicksort im bestcase optimal ist und im worstcase quadratisch (katastrophe).
heapsort ist im best- und wordstcase optimal... allerdings hat es eine längere innere schleife deshalb war es, soweit ich mich erinnern kann, bei meinen messungen im average case etwa um faktor 3 langsamer als quicksort.

Drakos

Ahja, das kann sein! Den avarage case hat ich nicht mehr im Kopf.
Aber mit Heapsort biste auf jeden Fall auf der sicheren Seite. Ich persönlich mag quicksort nicht sonderlich.

japro

wo ich schomal dabei bin:
heapsort

void downHeap(int A[], int pos, int size)
{
   int v = A[pos-1];
   while(pos <= size/2)
   {
      int pos2 = pos*2;
      if(pos2 < size && A[pos2-1] < A[pos2])
         ++pos2;
      if(v >= A[pos2-1])
         break;
      A[pos-1] = A[pos2-1];
      pos = pos2;
   }
   A[pos-1] = v;
}

void heapSort(int A[], int size)
{
   int i;
   for(i=size/2;i >= 1;--i)
      downHeap(A, i, size);
   while(size > 1)
   {
      swap(&A[0], &A[size-1]);
      downHeap(A, 1, --size);
   }

}

und introsort

void introSortLoop(int A[], int l, int r, int depth)
{
   while(r-l > threshold)
   {
      if(depth == 0)
      {
         heapSort(&A[l], r-l);
         --depth;
      }
      int p = partition(A, l, r);
      introSortLoop(A, l, p-1, depth);
      l = p+1;
   }
}

void introSort(int A[], int size)
{
   introSortLoop(A, 0, size-1, 2*pow(log(size),2));
   insertionSort(A, size);
}

Hallo,

Jeder Sortierlagorithmus, der auf Vergleichen beruht hat mindestens als Laufzeit O(n*log n). Dies ist die untere Schranke.

Mit Bucketsort, einteilen in Buckets (Fächer), kann wenn die Anzahl der
Buckets (Einteilkategorien) bekannt ist eine Laufzeit von O(2n) erreicht werden!!

japro

MisterX schrieb:

Hallo,

Jeder Sortierlagorithmus, der auf Vergleichen beruht hat mindestens als Laufzeit O(n*log n). Dies ist die untere Schranke.

Mit Bucketsort, einteilen in Buckets (Fächer), kann wenn die Anzahl der
Buckets (Einteilkategorien) bekannt ist eine Laufzeit von O(2n) erreicht werden!!

auch straight radix sort hat eine laufzeit von O(n)

aber solche algorithmen sind immer an bestimmte eigentschaften der schlüssel gebunden. bucketsort setzt voraus, dass alle schlüssel in einem bestimmten intervall sind und straight radix sort funktioniert nur auf integern. d.h. diese verfahren sind keine allzweckverfahren... und demnach nicht übbrall einsetzbar...

volkard

japro schrieb:

Mit Bucketsort, einteilen in Buckets (Fächer), kann wenn die Anzahl der
Buckets (Einteilkategorien) bekannt ist eine Laufzeit von O(2n) erreicht werden!!

lahm. bei geeigneter ordnungsrelation kenn ich einen mit O(2).

Griffin

mit digitalen sortierverfahren schaffste meist auch O(N) bei guter ordnungsrelation

japro

volkard schrieb:

japro schrieb:

Mit Bucketsort, einteilen in Buckets (Fächer), kann wenn die Anzahl der
Buckets (Einteilkategorien) bekannt ist eine Laufzeit von O(2n) erreicht werden!!

lahm. bei geeigneter ordnungsrelation kenn ich einen mit O(2).

^^seltsame art zu quoten...

Jester

Griffin schrieb:

mit digitalen sortierverfahren schaffste meist auch O(N) bei guter ordnungsrelation

Könntest Du ein solches mal zeigen?
Was ist eine gute ordnungsrelation?

a<=b für alle a,b? Dann schaffe ich O(1)!

Es ist nämlich prinzipiell nicht möglich den worst case O(nlog(n)) zu unterschreiten. Im Mittel kann man O(n) (vielleicht sogar besser hinkriegen).
Aber worst-case geht nicht besser als O(nlog(n)), wenn keine Informationen über die Schlüssel vorausgesetzt sind.

edit: besserem deutsch