[C++] quicksort

[riemann_01]

Ciao a tutti!
Per quale motivo il seguente algoritmo di ordinamento, da me scritto, non funziona correttamente? Non riesco a trovare l'errore. Chi puo' darmi una mano? Grazie in anticipo!!

// quicksort.cc

#include <iostream>
using namespace std;

template <class T>
inline void my_swap(T& x, T& y)
{
	T temp = x;
	x = y;
	y = temp;
}

template <class T>
void fill(T* seq, int size)
{
	for(; size > 0; --size, ++seq) 
		cin >> *seq;
}

template <class T>
void print(T *seq, int size)
{
	for(; size > 0; --size, ++seq)
		cout << *seq << endl;
}

// trova l'elemento di confronto
template <class T>
T find_pivot(T* lm, T* rm)
{
	T val = *(lm + (rm - lm) / 2);
	return val;
}

// effettua la partizione
template <class T>
T* partition(T* lm, T* rm, T pivot)
{
	while(lm < rm) {
		while(*lm < pivot)
			++lm;
		while(*rm > pivot)
			--rm;
		if(lm < rm) {
			my_swap(*lm,*rm);
			++lm;
			--rm;
		}
	}
	return lm;
}

// algoritmo di ordinamento
template <class T>
void quicksort(T* seq, T* lm, T* rm)
{
	T pvt = find_pivot(lm,rm), *p;
	if(lm < rm) {
		p = partition(lm,rm,pvt);
		quicksort(seq,lm,p-1);
		quicksort(seq,p+1,rm);
	}
}

// prova
int main()
{
	int a[10];
	
	cout << "Insert 10 integers (to confirm press ENTER)\n";
	fill(a,10);
	cout << "Sorted sequence\n";
	quicksort(a,&a[0],&a[10-1]);
	print(a,10);
}

Insert 10 integers (to confirm press ENTER)
100
10
200
-100
-200
-101
100
-23
0
23
Sorted sequence
-200
10
-101
-100
-23
0
23
100
100
200

----------------------------------------------
Program exited successfully with errcode (0)
Press the Enter key to close this terminal ...

[trallallero]

// quicksort.cc

void quicksort(T* seq, T* lm, T* rm)
{
	T pvt = find_pivot(lm,rm), *p;
	if(lm < rm) {
		p = partition(lm,rm,pvt);
		quicksort(seq,lm,p-1);
		quicksort(seq,p+1,rm);
	}
}

cosi' ad occhio p-1 e p+1 potrebbero sforare.

in un array da lm a rm
p-1 potrebbe essere < lm
p+1 > rm ...

io aggiungerei un controllo tipo (solo per debuggure)

      if ( (p-1) < lm )
         cout << "MINORE" << endl;
      if ( (p+1) > rm )
         cout << "MAGGIORE" << endl;

spero ti serva a qualcosa

[Qu@ker]

Il pivot li' in mezzo all'array da' qualche problema quando tenti di riordinare.
Spesso in questi casi lo si sposta alla fine dell'array, si ordina il resto e poi
si mette il pivot nella posizione 'giusta'.
Faccio un esempio sulla falsariga del tuo:

#include <iostream>
#include <algorithm>
using namespace std;

template <class T>
void fill(T* seq, int size)
{
	for(; size > 0; --size, ++seq) 
		cin >> *seq;
}

template <class T>
void print(T *seq, int size)
{
	for(; size > 0; --size)
		cout << *seq++ << " ";
	cout << endl;
}

template <class T>
inline
T* find_pivot(T* lm, T* rm)
{
	return (lm + (rm - lm) / 2);
}

template <class T>
T* partition(T* inizio, T* fine, T *pivot)
{
        T *lm = inizio, *rm = fine-1;
        swap(*pivot, *fine);
        for (;;) {
	        while(*lm < *fine)
			++lm;
		while(*rm > *fine) 
			if (--rm == inizio)
				break;
		if (lm >= rm)
			break;
                swap(*lm, *rm);
                ++lm;
                --rm;
        }
        std::swap(*lm, *fine);

        return lm;
}

template <class T>
void quicksort(T* seq, T* lm, T* rm)
{
	if (rm <= lm)
		return;
	T *p = partition(lm,rm,find_pivot(lm,rm));
	quicksort(seq,lm,p-1);
	quicksort(seq,p+1,rm);
}

int main()
{
	int a[10];
	
	cout << "Insert 10 integers (to confirm press ENTER)\n";
	fill(a,10);
	cout << "Sorted sequence\n";
	quicksort(a,&a[0],&a[9]);
	print(a,10);
}

bash-3.00$ ./qsort
Insert 10 integers (to confirm press ENTER)
100 10 200 -100 -200 -101 100 -23 0 23
Sorted sequence
-200 -101 -100 -23 0 10 23 100 100 200
bash-3.00$

[riemann_01]

Grazie ai vostri consigli sono riuscito a rilevare l'errore.
Riporto la versione corretta.

// quicksort.h

#include <iostream>
using namespace std;

template <class T>
void fill(T *seq, int dim)
{
	for(; dim > 0; --dim, ++seq)
		cin >> *seq;
}

template <class T>
void print(T *seq, int dim)
{
	for(; dim > 0; --dim, ++seq)
		cout << *seq << endl;
}

template <class T>
inline void swap(T *x, T *y)
{
	T temp = *x;
	*x = *y;
	*y = temp;
}

template <class T>
void quicksort(T *seq, T *lm, T *rm)
{
	if(rm > lm) {
		T *i = lm - 1, *j = rm - 1, *pivot = rm;
		
		for(;;) {
			while(*(++i) < *pivot);
			while((*j > *pivot) && (--j >= lm));
			if(i < j)
				::swap(i,j);
			else
				break;
		}
		::swap(i,rm);
		quicksort(seq,lm,i-1);
		quicksort(seq,i+1,rm);
	}
}

// quicksort.cc

#include "quicksort.h"

const int SIZE = 10;

int main()
{
	int d[SIZE];
	
	cout << "Insert " << SIZE << " integers (to confirm press ENTER)\n";
	fill(d,SIZE),
	cout << "Sorting...\n";
	quicksort(d,&d[0],&d[SIZE-1]);
	print(d,SIZE);
}