[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);
}