PROBLEMA C++: Quicksort ricorsivo che non va

[_Achille]

Salve ragazzi. Devo creare un Quicksort (in realtà no, ma devo adattarlo a un puntatore a funzione bool che sostituirà le condizioni per poterlo adattare ad un ordinamento crescente o decrescente), ho creato una classe ma non funzionava, quindi per testare il codice ho preferito riportarlo in un unico file molto semplificato. Il codice è questo:

#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <iomanip>
using std::setw;
#include <cstdlib>

void quickSort(int [], const size_t);

void partition(int [], const size_t, const size_t);

int main()
{
  
    int num[] = {37, 2, 6, 4, 89, 8, 10, 12, 68, 45};
    size_t size = sizeof(num)/sizeof(int);
  
    quickSort(num, size);
  
    for(int i=0; i<size; i++)
      
        cout << num[i] << setw(3);
  
}

void quickSort(int array[], const size_t arraySize)
{
  
    if(arraySize>1)
  
        partition(array, 0, arraySize);
}

void partition(int array[], const size_t begin, const size_t end)
{
  
    int i=end;
    int pos=begin;
    int temp;
  
    while(i!=pos)
    {
      
        if(i>pos)
        {
          
            if(array[pos]>array[i])
            {
              
                temp=array[pos];
                array[pos]=array[i];
                array[i]=temp;
              
                temp=pos;
                pos=i;
                i=temp;
              
            }
          
            --i;
        }
      
        else {
      
            if(array[pos]<array[i])
            {
              
                temp=array[pos];
                array[pos]=array[i];
                array[i]=temp;
              
                temp=pos;
                pos=i;
                i=temp;
              
            }
          
            ++i;
          
        }
          
    }
  
    if(begin>end) {
      
        partition(array, begin, pos-1);
        partition(array, pos, end);
      
    }
  
    return;
}

Per funzionare funziona, ma solo la prima passata. 37 raggiunge il suo punto, ma poi la funzione termina senza invocarsi in modo ricorsivo come previsto (o almeno, non noto altri cambiamenti). Nel normale progetto il codice è leggermente più ordinato (funzione swapArray e swapInteger) ma questo è solo per test.
L'output è quello prevedibile manualmente per la prima passata: 12, 2, 6, 4, 10, 8, 37, 89, 68, 45.

 

[DDog29]

if(begin>end) {

Prova a mettere < da quanto ho capito non ti richiama il partiziona dopo la prima volta?

dopo il primo partizionamento hai inizio =0 e fine =al size.. mi sembra che non cambi valori delle variabili quindi vuol dire non richiama mai il partiziona, se metti minore dovrebbe andare..

 

[_Achille]

Ah giusto! Che stupido!
Ora va bene.
Comunque dava un problema quando l'array da ordinare era opposto, ovvero errore di segmentazione. Ho aggiunto un if per prevenire ciò:

void Quicksort::partition(int array[], const size_t begin, const size_t end, bool (*compare)(const int, const int))
{
   
    int i=end;
    int pos=begin;
   
    while(i!=pos)
    {
       
        if(i>pos)
        {
           
            if((*compare)(array[pos], array[i]))
            {
               
                swapArray(&array[pos], &array[i]);
               
                swapInteger(&pos, &i);
               
            }
           
            --i;
        }
       
        else {
       
            if((*compare)(array[i], array[pos]))
            {
               
                swapArray(&array[pos], &array[i]);
               
                swapInteger(&pos, &i);
               
               
            }
           
            ++i;
           
        }
           
    }
   
    if(begin<end && pos!=end)
    {
       
        partition(array, begin, pos-1, compare);
        partition(array, pos+1, end, compare);
    }
    else if(begin<end)
   
        partition(array, begin+1, pos-1, compare);
   
}

Il codice deriva dal progetto vero e proprio. Uso come sostituzione al bool due ordinamenti, uno ascend l'altro descend. Prototipi e funzioni:

bool ascend(const int, const int);

bool descend(const int, const int);

bool ascend(const int a, const int b)
{
   
    return a>b;
}

bool descend(const int a, const int b)
{
   
    return b>a;
}

Tecnicamente con descend dovrebbe sistemarsi in modo decrescente ma da errore di segmentazione. È un errore o una limitazione della funzione partition() vera e propria?

 

[DDog29]

In teoria l'errore di segmentazione si ottiene quando si cerca di accedere ad un area di memoria alla quale non si hanno i permessi.. .In questo caso purtroppo non posso aiutarti, aspettiamo altre risposte.Ora sono curioso di conoscere la soluzione.. nel frattempo se hai urgenza puoi fare con gli if come hai detto tu..
Oppure ancora in alternativa potresti far uso del polimorfismo riscrivendo il quick per l'ordinamento inverso, facendo ad esempio in questo modo:

QuickSort( array, inizio,fine,crescente);
QuickSort(array ,inizio, fine);

Scusa il pseudocodice impreciso ma penso che sia la maniera più chiara per spiegarlo. Utilizzi l'overload aggiungendo una variabile in più per il quick di ordinamento crescente, che sia un int, un char o un bool e l'altro lo lasci invariato o viceversa.. anche se ciò ti costringe ad avere due metodi

 

[_Achille]

In teoria l'errore di segmentazione si ottiene quando si cerca di accedere ad un area di memoria alla quale non si hanno i permessi.. .In questo caso purtroppo non posso aiutarti, aspettiamo altre risposte.Ora sono curioso di conoscere la soluzione.. nel frattempo se hai urgenza puoi fare con gli if come hai detto tu..
Oppure ancora in alternativa potresti far uso del polimorfismo riscrivendo il quick per l'ordinamento inverso, facendo ad esempio in questo modo:

QuickSort( array, inizio,fine,crescente);
QuickSort(array ,inizio, fine);

Scusa il pseudocodice impreciso ma penso che sia la maniera più chiara per spiegarlo. Utilizzi l'overload aggiungendo una variabile in più per il quick di ordinamento crescente, che sia un int, un char o un bool e l'altro lo lasci invariato o viceversa.. anche se ciò ti costringe ad avere due metodi

Potrei sì sovraccaricare, ma sfortunatamente non andrei a sfruttare un array di puntatori a funzione per ascend e descend (e volevo esercitarmi su questo).
Altra modifica che intendevo fare è togliere i —i e ++i e metterli in un loro if a parte, visto che se i dovesse scambiarsi con pos la prima volta (con pos=0 e i=end) allora —i mi farebbe diventare i=-1 il che può causare errore di segmentazione.

 

[_Achille]

Direi che ora dovrei aver fatto:
Codice della funzione di partizione:

//Prototipo:
void partition(int [], const size_t, const size_t, bool (*)(const int, const int));

void Quicksort::partition(int array[], const size_t begin, const size_t end, bool (*compare)(const int, const int))
{

    int i=end;
    int pos=begin;

    while(i!=pos)
    {

        if(i>pos)
        {

            if((*compare)(array[pos], array[i]))
            {
        
                swap(&array[pos], &array[i]);
        
                swap(&pos, &i);
        
            }
        }

        else {

            if((*compare)(array[i], array[pos]))
            {
        
                swap(&array[pos], &array[i]);
        
                swap(&pos, &i);
            
            }
        }

        if(i>pos)
            --i;
        else
            ++i;
        
    
    }

    if(begin<end && pos!=end && pos!=begin)
    {

        partition(array, begin, pos-1, compare);
        partition(array, pos+1, end, compare);

    }

   // Ho dovuto aggiungere queste eccezioni quando l'insieme da partizionare in due ha come pivot begin o end perciò il
   //secondo insieme è insieme vuoto perciò non succesivamente ordinabile e partizionabile
    else if(begin<end && pos!=begin)

        partition(array, begin, end-1, compare);

    else if(begin<end)

        partition(array, begin+1, end, compare);


}

Codice delle funzioni di ordinamento:

//Prototipi:
bool ascend(const int, const int);

bool descend(const int, const int);

bool ascend(const int a, const int b)
{

    return a>b;
}

bool descend(const int a, const int b)
{

    //Notare che la precedente b>a mi dava problemi
    return a<b;
}

La funzione è chiamata automaticamente dal costruttore

Se qualcuno ha qualche idea riguardo errori o comunque parti migliorabili?