Sortierverfahren Qsort in C

combi

Hi!

Ich habe schon im Internet danach gesucht, habe aber nichts richtiges gefunden. Ich hoffe, mir kann jemand weiterhelfen. Brauche ein Quellcode-Beispiel zum Sortierverfahren in C. Bekomme es einfach nicht hin. Habe langsam keine Idee mehr, wie ich dieses Verfahren programmieren kann. Bin noch Anfänger.
Vielen Dank!

TheTester

Keine Idee wie du es programmieren sollst? Dann hier mal der ultimative Tipp.

----Teile und Herrsche----

bye

tt

DrZoidberg

TheTester schrieb:

Keine Idee wie du es programmieren sollst? Dann hier mal der ultimative Tipp.

----Teile und Herrsche----

"divide and conquer"
conquer heisst erobern und nicht herrschen auch wenn "divide and conquer" meistens mit "teile und herrsche" übersetzt wird.
Den Grund dafür kannst du hier nachlesen:
http://de.wikipedia.org/wiki/Teile_und_herrsche

Diese Übersetzung ist aber nicht wörtlich und passt nicht für das Quicksort Verfahren. Ich sehe zumindest nicht wo da irgendwas beherrscht wird.

TheTester

aha...

also ich sehe bei wikipedia folgendes
Teile und herrsche - lateinisch: divide et impera

gehen wir mal davon aus das imperator vielleicht sowas wie kaiser oder ähnliches heisst dann könnte man das ja synonym mit herrscher verwenden was wieder zur folge hat das impera vielleicht herrsche heisst

bei divide und conquer könnte man ja auch sagen conquer könnte auch als "bezwingen" übersetzt werden

wenn ich das jetzt mal alles auf das problem umlege könnte es am ende sein sowas wie teile das problem auf und bezwinge es...oder teile das problem auf und beherrsche es
in dem sinne könnte man sagen ich beherrsche das problem, ich kann damit umgehen, weis wie es zu lösen ist
das is vielleicht sowas wie eine situation beherrschen... oder eroberst du die situation wenn dir beim fahren vielleicht dein auto ausbricht? nein du beherrschst das problem

mal ganz davon abgesehen seh ich auch nicht wo ich bei quicksort was erobern soll

aber um dich nicht ganz unglücklich zu machen da ich ja gesagt habe das conquer auch sowas wie bezwingen heissen kann könnte man ja synomym ich bezwinge einen berg bzw. ich erobere einen berg verwenden... mal über tausend ecken vermutet ist das problem der berg und du eroberst ihn
auf unseren sachverhalt könnte man auch sagen hey du hast das problem erobert...du hast den aufstieg auf den berg gemeistert du hast das problem gelöst

und natürlich darf man das alles sprachlich nicht so eng fassen da das ja sowieso nur ein prinzip ist aber wenn ich das direkt auf quicksort runterbreche kann ich durch aus sagen ich teile die immer wieder die eingabe und löse damit das problem
dann hab ich es bezwungen bzw. beherrsche es...erobern klingt in dem kontext genauso blöde vielleicht ist es ja im englischen falsch übersetzt worden...oder was am naheliegendsten ist sie haben gar kein wort dafür, für diese art des herrschens

punkt schluss aus ende

japro

eine ziemlich umfangrieche version:

const int threshold = 32;

void swap(int *a, int *b)
{
   int xchg = *a;
   *a = *b;
   *b = xchg;
}

int* medianOfThree(int *a, int *b, int *c)
{
   if(*a < *b)
      if(*b < *c)
         return b;
      else if(*a < *c)
         return c;
      else
         return a;
   else
      if(*a < *c)
         return a;
      else if(*b < *c)
         return c;
      else
         return b;
}

int* minElement(int A[], int size)
{
   int i;
   int *min = &A[0];
   for(i=0;i<size;++i)
      if(A[i] < *min)
         min = &A[i];
   return min;
}

void insertionSort(int A[], int size)
{
   int i;
   swap(&A[0], minElement(A, threshold));
   for(i=2;i<size;++i)
   {
      int v = A[i], j = i-1;
      while(A[j] > v)
      { A[j+1] = A[j]; --j; }
      A[j+1] = v;
   }
}

int partition(int A[], int l, int r)
{
   swap(&A[l], medianOfThree(&A[l], &A[(r+l)/2], &A[r]));
   int v = A[l];
   int i = l+1;
   int j = r;

   for(;;)
   {
      while(A[i] < v)
         ++i;
      while(A[j] > v)
         --j;

      if(i >= j)
         break;

      swap(&A[i], &A[j]);
      ++i; --j;
   }
   swap(&A[j], &A[l]);
   return j;
}

void quickSortLoop(int A[], int l, int r)
{
   while(r-l > threshold)
   {
      int p = partition(A, l, r);
      if(p-l > r-p)
      {
         quickSortLoop(A, p+1, r);
         r = p-1;
      }
      else
      {
         quickSortLoop(A, l, p-1);
         l = p+1;
      }
   }
}

void quickSort(int A[], int size)
{
   quickSortLoop(A, 0, size-1);
   insertionSort(A, size);
}

turing* 0

combi schrieb:

Hi!

Ich habe schon im Internet danach gesucht, habe aber nichts richtiges gefunden. Ich hoffe, mir kann jemand weiterhelfen. Brauche ein Quellcode-Beispiel zum Sortierverfahren in C. Bekomme es einfach nicht hin. Habe langsam keine Idee mehr, wie ich dieses Verfahren programmieren kann. Bin noch Anfänger.
Vielen Dank!

Schau mal in das Buch von Sedgewick: Algorithmen in C.
Dort ist der Quicksort mit ein paar Zeilen programmiert und zwar sehr gut verständlich.

Ich habe versucht, Quicksort und Bubblesort in einen Code zu schreiben, funktioniert aber leidern nicht. Das Programm führt Bubblesort ohne Probleme aus, nur Quicksort überspringt er, als stände da gar kein Code. Quicksort sollte ausgeführt werden, wenn man 2 wählt, geht aber nicht. Weiß jemand woran das liegen könnte und wie man es richtig programmiert?

Hier der Quellcode:

#include <stdio.h>
#include <stdlib.h>
#define MAX 50

int a[MAX];
int rand_seed=10;

/* gibt Zufallszahlen zwischen 0 und 32767 zurück*/
int rand()
{
rand_seed = rand_seed * 1103515245 +12345;
return (unsigned int)(rand_seed / 65536) % 32768;
}

main()
{
int i,t,x,y,wahl;
char weiter[5];

do
{
system("cls");
printf("\n\t\t Sortierverfahren");
printf("\n\t\t~~~~~~~~~~~~~~~~~~");
printf("\n\nWelches Sortierverfahren moechten Sie waehlen? ");
printf("\n\nMoechten Sie Bubble-Sort verwenden, druecken Sie die 1!");
printf("\nMoechten Sie Quick-Sort verwenden, druecken Sie die 2!");
printf("\n\nBitte waehlen!");
printf("\n\n");
scanf("%i",&wahl);

/* füllt das Feld. Am Anfang ist i=0, danach wird getestet, ob i kleiner als die maximale
Zahl die ausgegeben werden soll, ist. Ist dies der Fall, so wird i um eins höher gezählt.*/
for (i=0; i < MAX; i=i+1)
{
a[i]=rand();
printf("%d\n",a[i]);
}

if(wahl==1)
{

/* sortieren der Felder. Ist x kleiner als die maximale Zahl-1, so wird x um eins erhöht./
for (x=0; x < MAX-1; x=x+1)
for (y=0; y < MAX-x-1; y=y+1)
if (a[y] > a[y+1])
{
t=a[y];
a[y]=a[y+1];
a[y+1]=t;
}
/* gibt sortierte Felder solange aus, bis der Maximalwert, der ausgegeben werden sollte,
erreicht ist./
printf("\n\nHier sind die Zahlen in sortierter Reihenfolge!\n");
printf("\n\n");
for (i=0; i < MAX; i=i+1)
printf("%d\n",a[i]);
}

if(wahl==2)
{
int feld[10];
int n;

int quicksort(int low, int high)
{
int h;
int i=low;
int j=high;
int x=feld[(low+high)/2];

do
{
while(feld[i]<x)i=i+1;
while(feld[j]>x)j=j-1;
if(i<=j)
{
h=feld[i];
feld[i]=feld[j];
feld[j]=h;
i=i+1;j=j-1;
}
}while(i<=j);

if(low<j) quicksort(low,j);
if(i<high)quicksort(i,high);

}

int main(int argc,char *argv[])
{
// Zufallsgenerator initialisieren
srand((unsigned) time(NULL));

// Felder mit Zufallszahlen belegen
for(n=0;n<=100;n=n+1)
feld[n]=1+rand()%100;

printf("\nHier stehen die unsortierten Zahlen!");
printf("\n\n");

// Ausgabe der unsortierten Zahlen
for(n=0;n<=100;n=n+1)
printf("%d ",feld[n]);

// Sortieren
quicksort(0,100);
printf("\n");
printf("\nHier stehen die sortierten Zahlen!");
printf("\n\n");
// Ausgabe der sortierten Zahlen
for(n=0;n<=100;n=n+1)
printf("%d ",feld[n]);
scanf("%i",&n);
}
}

printf("\n\n\nMoechten Sie fortfahren? ja/nein ");
scanf("%s",weiter);
}
while (weiter[0]=='j' || weiter[0]=='J');

}