A24: Quicksort

A24: Quicksort

Beitragvon test123 » 15.06.2010 00:17

So hier mal meine Lösung zum Quicksort:
Code: Alles auswählen
void ausgabe(double* feld,int anzahl)
{
  int n = 0;
  for(int i=0;i<=anzahl;i++)
  {
    cout << setw(7) << setprecision(3) << feld[i] << ",";
    n++;
    if(n>18)
    {
      cout << endl;
      n=0;
    }
  }
  cout << endl;
}

void tausche(double* feld,int a, int b)
{
  double temp = feld[a];
  feld[a]=feld[b];
  feld[b]=temp;
}

int partition(double* feld, int anfang, int ende)
{
  double pivot = feld[anfang];
  int l = anfang;
  for(int i=anfang+1; i<=ende; i++)
  {
    if(feld[i]<pivot)
    {
      l=l+1;
      tausche(feld,i,l);
    }
  }
  tausche(feld,anfang,l);
  return l;
}

void quicksort(double* feld,int anfang,int ende)
{
    if (anfang < ende)
    {
          int mitte = partition(feld,anfang,ende);
          quicksort(feld, anfang, mitte);
          quicksort(feld, mitte+1, ende);
     }
}

double* zahlengenerieren(int anzahl)
{
  double* feld= new double[10];
  srand((unsigned int)time(0));
  for(int i=0;i<=anzahl;i++)
    feld[i]=rand()/(double)RAND_MAX;
  return feld;
}


int main()
{
  int anzahl = 1000;
  int anfang = 0;
  double* feld= zahlengenerieren(anzahl);
  cout << "\nUnsortiert:\n";
  ausgabe(feld,anzahl);
  quicksort(feld,anfang,anzahl);
  cout << "\nSortiert:\n";
  ausgabe(feld,anzahl);
}
test123
 
Beiträge: 10
Registriert: 28.10.2009 10:12

Re: A24: Quicksort

Beitragvon Cashdogg » 15.06.2010 15:32

Weis jemand wo ich Änderungen vornehmen muss, damit die Liste nicht absteigend sonder aufsteigend sortiert wird?
Cashdogg
 
Beiträge: 408
Registriert: 20.12.2008 15:05

Re: A24: Quicksort

Beitragvon laxamyri » 15.06.2010 16:54

in der funktion wo du die partitionierung machst gibts die abfrage if(feld[i]<pivot) un da einfach ein > statt <
laxamyri
 
Beiträge: 23
Registriert: 01.07.2009 14:10

Re: A24: Quicksort

Beitragvon Cashdogg » 15.06.2010 17:06

Tatsächlich?! Hmm ich hab schon überall rumgewerkelt, aber den Fall hatte ich vermutlich noch nicht. Danke ;) .
Cashdogg
 
Beiträge: 408
Registriert: 20.12.2008 15:05

Re: A24: Quicksort

Beitragvon test123 » 15.06.2010 22:30

so hier noch ne kleine verbesserung, weils sonst vllt nich zum abbruch kommen würde,
wobei das mit double-zufallswerten sehr unwahrscheinlich is aber egal.
Code: Alles auswählen
void quicksort(double* feld,int anfang,int ende)
{
    if (anfang < ende)
    {
          int mitte = partition(feld,anfang,ende);
          quicksort(feld, anfang, mitte-1);                           //hier mitte-1 statt mitte, so dass die Teile definitiv kleiner werden
          quicksort(feld, mitte+1, ende);
     }
}
test123
 
Beiträge: 10
Registriert: 28.10.2009 10:12


Zurück zu Programmieren

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron