Quicksort

[Der_Honk]

Hi,

ich bin relativ ungelernt im Umgang mit C++, Pointer usw.
Deshalb habe ich auch Probleme, eine einigermaßen saubere Quicksort-Implementierung zu schreiben, könnte mir jemand weiterhelfen? Bitte...

#include "stdafx.h"
#include "myfunctions.h"

int counter = 4;

void meridian_of_three( int *left, int *right)
{
	int* m_index = left + ((right - left)/2);
	int buffer;

	if( (*left) > (*right))
	{buffer = *left; *left = *right; *right = buffer;}

	if( (*left) > (*m_index))
	{buffer = *left; *left = *m_index; *m_index = buffer;}

	if( (*m_index) > (*right))
	{buffer = *m_index; *m_index = *right; *right = buffer;}

	printf( "\nMOT Links: %i, Rechts: %i, Meridian: %i\n", *left, *right, *m_index );
}

void quicksort(int *left, int *right)
{
	if( left >= right ) return; // nur ein Element übergeben

	// Ansonsten sind mehrere Elemente übergeben worden
	meridian_of_three( left, right);

	int pivot = *right;
	int buffer;
	int *lptr = left - 1, *rptr = right + 1;
	do{
		do{ ++lptr; }while( *lptr <= pivot );
		do{ --rptr; }while( *rptr >= pivot );
	if( lptr > rptr) break;
		int buffer = *lptr;
		*lptr = *rptr;
		*rptr = buffer;
	}while(true);

	buffer = *lptr;
	*lptr = *right;
	*right = buffer;
	printf( "\nLeft: %p(%i), lptr: %p(%i)\n", left, *left, lptr, *lptr);
	printf( "\nRight: %p(%i), rptr: %p(%i)\n", right, *right, rptr, *rptr);
	printf( "\nDistanz: %i\n", lptr - 1 - left);
	//quicksort( left, lptr - 1);
	quicksort( lptr + 1, right);
	quicksort(left, lptr - 1);
}

Das Problem ist wohl die auftretende Bereichsüberschreitung. Argh.

Ich übergeben einen Zeiger auf das erste und das letzte Array-Element.

Gruß

Michael

/edit: sfds

[Walli]

Kannst du bitte Codetags einfügen?
Btw, sollte es nicht median_of_three heißen?

[Der_Honk]

Hi,

sorry, bin hier neu im Forum, deshalb habe ich das nicht entsprechend kenntlich gemacht, danke an den Editor.

Ob es nun Median oder Meridian heißt, Meridian ist laut Wikipedia nun auch nicht gerade abwägig by the way, bringt mich leider in Bezug auf die Lösung des Problems kein Stück voran.

Kann mir jemand weiterhelfen?

Michael

[Erhard Henkes]

// siehe http://sattas.homeunix.net/zeugs/quicksort.pdf

#include <iostream>
#include <ctime>
#include <conio.h>
using namespace std;

const int MAX = 10000000;
int daten[MAX];

void quicksort( int von, int bis )
{
  int links = von, rechts = bis, mitte, zwischen;
  mitte = ( von + bis ) / 2;
  do{
      for(;daten[links] < daten[mitte]; links++);
          for(;daten[mitte] < daten[rechts]; rechts--);
              if(links <= rechts) 
              { 
                  //Tausch durchfuehren
                  zwischen = daten[links];
                  daten[links] = daten[rechts];
                  daten[rechts] = zwischen;
                  links++;
                  rechts--;
              }
    }
    while (links <= rechts);
    if(von < rechts) quicksort(von, rechts);
    if(links < bis)  quicksort(links, bis);
}

int main()
{
  clock_t t1,t2;
  double ts;
  srand(time(NULL));

  for(int i=0;i<(MAX);i++) 
  {
    daten[i] = rand()%MAX;
  } 

  t1=clock();
  quicksort(0,MAX-1); 
  t2=clock();

  ts=(t2-t1)/static_cast<float>(CLOCKS_PER_SEC);
  cout << "\tZeit: " << ts << " QuickSort Test" << endl;
  cout<<endl;       

  getch();
}

Die STL bietet bereits einen fertigen Algorithmus sort(begin,end) an, der auf Quicksort beruht, z.B. für vector, deque. list hat eine eigene Funktion sort().

Wenn du "sehen" willst, wie sort(begin,end) arbeitet:

#include <algorithm>    
#include <iostream>
#include <conio.h>
#include "Xint_Sonde.h"
/*
Klasse Xint findet man z.B. hier:
http://www.c-plusplus.net/forum/viewtopic.php?t=85532&postdays=0&postorder=asc&start=10
*/
using namespace std;

int main () 
{
    const int N = 5;
    Xint x[N];
    for(int i=0;i<N;++i)
    {
        x[i].setNum(N-i);
    }    
    for(int i=0;i<N;++i)
    {
        cout << x[i].getNum() << endl;
    }    
    cout << endl << endl;
    sort(&x[0],&x[N]);
    for(int i=0;i<N;++i)
    {
        cout << x[i].getNum() << endl;
    }    
    Xint::statistik(cout);   
    getch();
}