Newsgroup: it.comp.lang.c++
Titolo: Quick Sort su un vettore

Mi dite cosa ho sbagliato nell'ordinare un vettore utilizzando il metodo 
quick sort?
void BiLista::ordina(int vettore [ ], int inf, int sup)
 {
   int i, j;
   char pivot, temp;
    if(inf < num_elem)
     {
      i = inf;            //estremo inferiore
      j = sup;            //estremo superiore
      pivot = sup / 2;    //centro del vettore
      do
       {
        while(vettore[i] < vettore[pivot])
         i++;
        while(vettore[pivot] < vettore[j])
         j--;
        if(i <= j)
         {
           //I due valori vengono scambiati
           temp = vettore[i];
           vettore[i] = vettore[j];
           vettore[j] = temp;
           i++;
           j--;
         }
        }
       while(i <= j);
      ordina(vettore, inf , j);
      ordina(vettore, i , sup);
     }
  int x;
  for (x=1; x <=num_elem; x++)
  cout << "elemento " << x << ": " << vettore[x] << "\n";
  system("pause");
 }
N.B
Non viene visualizzato niente, il programma si chiude immediatamente anche 
se ho inserito system("pause") 

 quick sort?
       if(inf < num_elem)  >>>  if(inf < sup)
...
         if(i <= j) >>>  if(i < j)
...
while(i <= j); >>> while(i < j);
...
      ordina(vettore, inf , j-1);
      ordina(vettore, i+1 , sup);
Visto che č un esercizio, a te scoprire perchč..

 se ho inserito system("pause") 
Probabilmente tenta di accedere a qualche elemento fuori dall'array.
Se dopo le correzioni agli indici il problema rimane, prova a inserire
stampe intermedie per vedere cosa sta succedendo.
        Mauro

 ha scritto nel messaggio
news:cj8pp8$8ch$1...@mammooth.localnet...
Soluzione:
void ordina(int vettore [ ], int inf, int sup)
{
int i, j;
int pivot, temp; //xche char?
if(inf < sup)
{
    i = inf;             //estremo inferiore
    j = sup+1;       //estremo superiore
    pivot = sup / 2; //centro del vettore << questa scelta non è ottimale!
vedi teoria quicksort
    do {
            do i++;while (vettore[i] < vettore[pivot]);  //usa il do qui,
deve farlo almeno 1 volta
            do j--;while (vettore[pivot] < vettore[j]);
            if (i<j){
                        //I due valori vengono scambiati
                        temp = vettore[pivot];
                        vettore[pivot] = vettore[j];
                        vettore[j] = temp;
                        //puoi anche togliere i++ e j-- coi "do" di sopra
                    }
            } while (i < j);
            ordina(vettore, inf , j-1);
            ordina(vettore, i+1, sup);
   }
}
Guarda
http://www.vialattea.net/esperti/inform/qsort.htm
Ciao
Andrea

Grazie per avermi risposto.
Ho provato ad inserire le modifiche consigliate, ma gli elementi non vengono 
ordinati correttamente.
Ad esempio, se un array è composto da: 5 3 4 9 0, li "ordina" nel seguente 
modo: 5 3 0 9 4.
Siccome, in realtà, quell'array mi serve per ordinare una lista 
bidirezionale, con struttura elem (valore, precedente, successico);
Vi inserisco anche la funzione che copia nell'array la lista... non si mai, 
potrebbe nascere da lì l'errore.
------------------------------------------------------
//Copia tutti gli elementi della lista in un array
void BiLista::lista_array()
 {
  elem* p = testa;
  int vettore[num_elem];
  int i = 0;
  while (p != NULL)
   {
    vettore[i] = p->val;
    p = p->next;
    i++;
   };
  ordina(vettore, 0, num_elem-1);
  for (int x=0; x <=num_elem-1; x++)
   cout << "elemento " << x << ": " << vettore[x] << "\n";
 };
//Funzione per ordinare la lista
void BiLista::ordina(int vettore [ ], int inf, int sup)
 {
  int i, j;
  int pivot, temp;
  if(inf < sup)
   {
    i = inf;
    j = sup+1;    //Perchè sup+1?
    pivot = sup / 2;
    do
     {
      do
       {i++;}
      while (vettore[i] < vettore[pivot]);
      do
      {j--;}
      while (vettore[pivot] < vettore[j]);
      if (i<j)
      {
       temp = vettore[pivot];
       vettore[pivot] = vettore[j];
       vettore[j] = temp;
      }
    } while (i < j);
    ordina(vettore, inf , j-1);
    ordina(vettore, i+1, sup);
   }
}
------------------------------------------------------ 

Grazie per i tuoi consigli.
Lo so che esiste una funzioni che fa ciň che voglio,
ma devo ordinare questo array per esercirzio...
....perchč vettore e array sono due cose differenti? 

 modo: 5 3 0 9 4.
Chiedo scusa... in effetti l'algoritmo postato sopra è sbagliato... mi
spiace ma non l'ho provato!
Questo dovrebbe essere corretto:
void QuickSort(int vettore [ ], int inf, int sup)
{
   int pivot, i, j,temp;
   i = inf;
   j = sup; //il sup +1 vale solo nel caso che come pivot prendi
vettore[inf]!
   pivot = vettore[(inf+sup) /2]; //calcolato fuori dal ciclo
   do
  {
    while (vettore[j] > pivot)
         --j; //in effetti è meglio il while, altrimenti si rischia di non
ordinare bene nel caso di array già ordinati... sorry! :)
    while (vettore[i] < pivot)
          ++i;
   if(i <= j)
    {
       temp = vettore[j];
       vettore[j] = vettore[i];
       vettore[i] = temp;
       ++i;
       --j;
    }
} while(j >= i);
   if (inf<j) //evita un'allocazione in + nello stack
      QuickSort(vettore,inf,j); //ok senza -1
   if (i<sup) //evita un'allocazione in + nello stack
      QuickSort(vettore, i, sup); //ok senza +1
}
Ciao
Andrea