quicksort problem

Meep Meep

hola leute

hab da ein bloedes problem mit quicksort und ich komme nicht auf den fehler.
sollte eine template version werden.
ermal mein derzeitiger code:

template <class object>
void swap(object &a, object &b)
{
   object temp = a;
   a = b;
   b = temp;
}

template <class object>
void sort(object *t_array, unsigned int left, unsigned int right)
{
   if(left >= right)
      return;

   unsigned int l = left;
   unsigned int r = right;
   object pivot = t_array[(right + left) / 2];

   while(l < r)
   {
      while(t_array[l] <= pivot && l < r) ++l;
      while(t_array[r] >= pivot && r > l) --r;
      if(l >= r)
         break;

      swap(t_array[l], t_array[r]);
      ++l;
      --r;

   }
   sort(t_array, left, l - 1);
   sort(t_array, l + 1, right);
   swap(t_array[l], pivot);
}

nun hab ich ein testarray aus ints gemacht um das mal zu testen:

int-array:

30 82 90 56 17 95 15 48 26 4 58

nun das array nach der sortierung:

4 4 17 17 30 30 30 82 82 95 95

sieht da jemand wo der fehler liegt ?

Meep Meep

leo aka qsch

zeig mal her wie das array nach dem ersten durchlauf aussieht

Meep Meep

sodala

30 82 90 56 17 95 15 48 26 4 95

nach dem ersten duchlauf

Meep Meep

leo aka qsch

bis du dir sicher das das nach dem ersten Durchlauf war??

das sollte eher so aussehen

30 4 26 48 15 95 17 56 90 82 58

da laeuft schon gewalltig etwas schief

Meep Meep

das da was gewaltig schief laeuft weiß ich auch *g

is halt die frage was da nicht stimmt.
irgendwie krieg ich das ueberhaupt nicht auf die reihe

Meep Meep

tuempl

sollen da

swap(t_array[l], pivot);

die inhalte des arrays vertauscht werden? ich glaub schon...sie werdens aber nicht weil du ja nur den wert pivot aus dem array ließt und dadurch hast du den wert dann doppelt: dort wo du ihn hergenommen hast wie du ihn in pivot gespeichert hast und dort wo du ihn mit swap() hintust.

ich hab also

object pivot = t_array[(right + left) / 2

in

object& pivot = t_array[(right + left) / 2

geändert. es kommen keine werte mehr doppelt vor. aber funktioniern tuts trotzdem nicht.

Meep Meep

kennt sich denn niemand mit dem quicksort algo aus ?

vielleicht waere ich ja bei rund um die programmierung besser aufgehoben. wenn dem so ist, bitte mal verschieben

Meep Meep

enno-tyrant

void quicksort(apvector <int> &input_array, int top, int bottom) //uses recursion-calling itself
{
     int middle;
     if(top>bottom)
    {
          middle = partition(input_array, top, bottom);
          quicksort(input_array, top, middle);   //sort top partition
          quicksort(input_array, middle+1, bottom);    //sort bottom partition
     }
     return;
}

int partition(apvector <int> &input_array, int top, int bottom)
{
     int x = input_array[top];
     int i = top - 1;
     int j = bottom + 1;
     int temp;
     do
     {
           do      //move j towards top to the next element less than or equal to x.
           {
                  j - -;
           }while (x > input_array[j]);

          do      //move j towards bottom to the next element greater than or equal to x.
         {
                 i++;
          } while (x < input_array[i]);

          if (i < j)
         { 
                 temp = input_array[i];    //switch elements at positions i and j
                 input_array[i] = input_array[j];
                 input_array[j] = temp;
         }
     }while (i < j);     //loop ends when i and j have met in the middle
     return j;           // j and above represents top partition, below j is bottom partition
}

hiernachzulesen

Meep Meep

re

danke mal fuer den code, aber der scheint auch nicht ganz astrein zu sein.

ich hab den code mal minimal geaendert. wegen den variablenamen.

void quick_sort(unsigned int *list, unsigned int left, unsigned int right)
{
   if(left >= right)
      return;

   unsigned int middle = partition(list, left, right);
   quick_sort(list, right, middle);
   quick_sort(list, middle + 1, left);
}

unsigned int partition(unsigned int *list, unsigned int left, unsigned int right)
{
   unsigned int pivot = list[right];
   unsigned int r = right - 1;
   unsigned int l = left + 1;
   unsigned int temp = 0;

   do
   {
      do
      {
         l--; // (1)
      }  while(pivot > list[l]);
      do
      {
         r++; // (2)
      }  while(pivot < list[r]);
      if(r < l)
      {
         temp = list[r];
         list[r] = list[l];
         list[l] = temp;
      }
   } while(r < l);
   return l;
}

also sortiert wird hier mal garnichts.
ich geh mal davon aus, das mit bottom der erste wert des arrays gemeint ist.
sollte in zeile (1) nicht l++ und in zeile (2) r-- stehen ?

Meep Meep

ness

OK, wenn wir alle so schön am posten sin...:

template<class Iter,class Ftor,class Ftor2>
	void recursive_quicksort(Iter begin,Iter end,Ftor f,Ftor2 p)
	{
		if((end-begin)<2)
			return;
		Iter i=p(begin,end,f);
		recursive_quicksort(begin,i,f,p);
		recursive_quicksort(i+1,end,f,p);
	};

template<class Iter,class Ftor,class Ftor2>
	void iterative_quicksort(Iter begin,Iter end,Ftor f,Ftor2 p)
	{
		std::stack<Iter> s;
		s.push(end);
		s.push(begin);
		Iter l;

		Iter r;
		Iter i;
		while(!s.empty())
		{
			l=s.top();
			s.pop();
			r=s.top();
			s.pop();
			if((r-l)<2);
				continue;
			i=p(l,r,f);			
			s.push(i);
			s.push(l);
			s.push(r);
			s.push(i+1);
		};
	};

/edit: partitionierungsfunktor:

template<class Iter,class Ftor>
	struct std_partition
	{
		Iter operator()(Iter b,Iter e,Ftor f)
		{
			Iter i=b-1;	//Suchzeiger
			Iter j=e-1;	//dito
			typename std::iterator_traits<Iter>::value_type v=*(e-1);
			for(;;)
			{
				while(++i!=e&&f(*i,v));
				while(--j>i&&!f(*j,v));
				if(i>=j)
					break;
				std::iter_swap(i,j);
			};
			std::iter_swap(i,e-1);
			return i;
		};
	};

/edit:
recursive_quicksort braucht zum sortieren von 100000000 ints 4 Sekunden länger als std::sort - 24s.
/edit: mit cutoff für Kleine Daten:

template<class Iter,class Ftor,class Ftor2>
	void recursive_quicksort_2_helper(Iter begin,Iter end,Ftor f,Ftor2 p,unsigned M)
	{
		if((end-begin)<M)
			return;
		Iter i=p(begin,end,f);
		recursive_quicksort_2_helper(begin,i,f,p,M);
		recursive_quicksort_2_helper(i+1,end,f,p,M);
	};

	template<class Iter,class Ftor,class Ftor2>
	void recursive_quicksort_2(Iter begin,Iter end,Ftor f,Ftor2 p,unsigned M)
	{
		if(!((end-begin)<M))
		{
			Iter i=p(begin,end,f);
			recursive_quicksort_2_helper(begin,i,f,p,M);
			recursive_quicksort_2_helper(i+1,end,f,p,M);
		};
		insertionsort(begin,end,f);
	};

mit M=9 - 25s
mit M=13 - 23s
mit M=15 - 24s
std::sort - 20
Da fällt mir ein, ich wollte schon vor längerer Zeit mal ein größeres benchmark machen...