Quick Sort decrescente

di il
11 risposte

Quick Sort decrescente

Buongiorno, studiando per bene il Quick Sort mi sono chiesto come si potesse invertire l'ordine.
Ho provato quindi a "invertire" cercando di usare il più possibile la logica come già fatto per metodi d'ordinamento ingenui, ma senza risultati.
RIngrazio in anticipo chiunque mi darà una mano!

Codice quick sort crescente:

void quickSort(int vet[], int inf, int sup){
  int sx,dx;
  int pivot,temp;
  sx=inf;
  dx=sup;
  pivot=vet[(inf+sup)/2];            

  while (sx<=dx){                  
    while (vet[sx]<pivot) 
      sx++;                        
	while (vet[dx]>pivot) 
      dx--;                        
      if (sx<dx) {                       
	  temp = vet[sx];
          vet[sx] = vet[dx];
          vet[dx] = temp;
      }    
      if (sx<=dx){                   
          sx++;                        
	  dx--;
    }
  } 

  if (inf<dx) 
    quickSort(vet,inf,dx);         
  if (sx<sup) 
    quickSort(vet,sx,sup);         
} 

11 Risposte

  • Re: Quick Sort decrescente

    Semplice (ma NON cosi' semplice): devi fare DUE cose:

    1) invece di confrontare DIRETTAMENTE vet[sx] con pivot (questo confronto usa l'ORDINE NATIVO dell'oggetto confrontato) devi usare una FUNZIONE COMPARATRICE
    2) all'algoritmo, OLTRE al vettore, devi passare la FUNZIONE COMPARATRICE

    *) OVVIAMENTE modificare il codice di conseguenza.

    Che cosa fa la FUNZIONE COMPARATRICE?
    e' una funzione, di DUE argomenti (diciamo "compare(x,y)" ), che deve ritornare

    -1 se x < y
    0 se x = y
    +1 se x > y

    Se la funzione segue pedissequamente l'ordine NATURALE degli oggetti confrontati, l'algoritmo ritorna gli oggetti ordinati ESATTAMENTE come prima
    Ora la cosa diventa semplice: se vuoi invertire l'ordinamento, BASTA che passi una funzione comparatrice con confronta al contrario.

    La cosa NON E' semplice (e' semplice, ma non cosi' ovvia per chi e' alle prime esperienze): bisogna, in qualche modo, passare ad livello PIU' ALTO di astrazione: dal confronto diretto, ad UNA FUNZIONE CHE CONFRONTA
  • Re: Quick Sort decrescente

    migliorabile ha scritto:


    Semplice (ma NON cosi' semplice): devi fare DUE cose:

    1) invece di confrontare DIRETTAMENTE vet[sx] con pivot (questo confronto usa l'ORDINE NATIVO dell'oggetto confrontato) devi usare una FUNZIONE COMPARATRICE
    2) all'algoritmo, OLTRE al vettore, devi passare la FUNZIONE COMPARATRICE

    *) OVVIAMENTE modificare il codice di conseguenza.

    Che cosa fa la FUNZIONE COMPARATRICE?
    e' una funzione, di DUE argomenti (diciamo "compare(x,y)" ), che deve ritornare

    -1 se x < y
    0 se x = y
    +1 se x > y

    Se la funzione segue pedissequamente l'ordine NATURALE degli oggetti confrontati, l'algoritmo ritorna gli oggetti ordinati ESATTAMENTE come prima
    Ora la cosa diventa semplice: se vuoi invertire l'ordinamento, BASTA che passi una funzione comparatrice con confronta al contrario.

    La cosa NON E' semplice (e' semplice, ma non cosi' ovvia per chi e' alle prime esperienze): bisogna, in qualche modo, passare ad livello PIU' ALTO di astrazione: dal confronto diretto, ad UNA FUNZIONE CHE CONFRONTA
    Ho visto la risposta solo ora perchè non è arrivata la notifica via mail
    Allora, diciamo che probabilmente sono ancora troppo agli inizi per qualcosa di questo genere, ma già che ci sono perchè non provare:
    analizzando bene il tutto mi verrebbe in mente di, invece che eseguire:
    
    while(v[sx]<pivot)
        sx++;
    
    eseguire una cosa di questo tipo:
    
    sx+=compare(sx,piovt);
    
    con funzione di questo tipo:
    
    int compare(int x, int y) {
        if( x < y )
            return 1;
        else if( x = y )
            return 0;
        else
            return -1;
    }
  • Re: Quick Sort decrescente

    So che non va ancora bene per vari motivi quali il decremento che avverrebbe nel caso di x<y, ma attualmente il mio pensiero mi porta a questo
  • Re: Quick Sort decrescente

    Premetto che pur sapendo della sua esistenza non ho mai approfondito come effettivamente funzionasse il quick sort e che la mia conoscenza al riguardo si limita ad un video appena visto su youtube in cui viene spiegato l'algoritmo a livello teorico.
    Se ho ben capito, al termine della funzione (tralasciamo per il momento la parte iterativa) il pivot scelto dovrà avere alla sua sinistra gli elementi minori e alla sua destra quelli maggiori (trovandosi quindi nella posizione corretta). Ma utilizzando la funzione da te postata sul seguente array

    5 1 2 4 3

    e scegliendo come pivot l'elemento centrale (2 in questo caso), ottengo (ipotizzando di mostrare l'array prima dei due if finali legati alla parte ricorsiva) il seguente array

    2 1 5 4 3

    che evidentemente non rispetta le suddette condizioni.

    Come mai?
  • Re: Quick Sort decrescente

    ...
    che evidentemente non rispetta le suddette condizioni.

    Come mai?
    L'errore è nel codice o nel mio ragionamento?

    In ogni caso ho provato ad implementare l'algoritmo per conto mio:
    #include <iostream>
    #include <ctime>
    
    using namespace std;
    
    void mostra_array(int *v, const unsigned int &n)
    {
        for(unsigned int i = 0; i < n; ++i)
        {
            cout << v[i] << " ";
        }
        cout << endl;
    }
    
    //ORDINE CRESCENTE   ---> ordine =  1
    //ORDINE DECRESCENTE ---> ordine = -1
    void quick_sort(int *v, unsigned int sx, unsigned int dx, const int &ordine)
    {
        unsigned int pivot = sx + rand() % (dx - sx + 1);
        unsigned int SX = sx;
        unsigned int DX = dx;
        while(true)
        {
            while(SX < pivot && ordine * v[SX] <= ordine * v[pivot])
            {
                ++SX;
            }
            while(DX > pivot && ordine * v[DX] >= ordine * v[pivot])
            {
                --DX;
            }
            if(SX == DX)
            {
                break;
            }
            else
            {
                swap(v[SX], v[DX]);
                if(SX == pivot)
                {
                    pivot = DX;
                    ++SX;
                }
                else if(DX == pivot)
                {
                    pivot = SX;
                    --DX;
                }
                else
                {
                    ++SX;
                    --DX;
                }
            }
        }
        if(pivot > sx + 1)
        {
            quick_sort(v, sx, pivot - 1, ordine);
        }
        if(pivot < dx - 1)
        {
            quick_sort(v, pivot + 1, dx, ordine);
        }
    }
    
    int main()
    {
        srand(time(0));
        const int n = 7;
        int v[n] = {5, 3, 2, 4, 1, 9, 4};
        quick_sort(v, 0, n - 1, 1);
        mostra_array(v, n);
        cout << endl;
        quick_sort(v, 0, n - 1, -1);
        mostra_array(v, n);
    }
    Secondo voi va bene? Potrei ottimizzarlo in qualche modo?

    Cmq per quanto riguarda la questione iniziale del topic, non basta cambiare semplicemente il segno della diseguaglianza?! Nel mio codice faccio in questo modo e sembra funzionare bene...
  • Re: Quick Sort decrescente

    Nippolo ha scritto:


    ...
    che evidentemente non rispetta le suddette condizioni.

    Come mai?
    L'errore è nel codice o nel mio ragionamento?

    In ogni caso ho provato ad implementare l'algoritmo per conto mio:
    #include <iostream>
    #include <ctime>
    
    using namespace std;
    
    void mostra_array(int *v, const unsigned int &n)
    {
        for(unsigned int i = 0; i < n; ++i)
        {
            cout << v[i] << " ";
        }
        cout << endl;
    }
    
    //ORDINE CRESCENTE   ---> ordine =  1
    //ORDINE DECRESCENTE ---> ordine = -1
    void quick_sort(int *v, unsigned int sx, unsigned int dx, const int &ordine)
    {
        unsigned int pivot = sx + rand() % (dx - sx + 1);
        unsigned int SX = sx;
        unsigned int DX = dx;
        while(true)
        {
            while(SX < pivot && ordine * v[SX] <= ordine * v[pivot])
            {
                ++SX;
            }
            while(DX > pivot && ordine * v[DX] >= ordine * v[pivot])
            {
                --DX;
            }
            if(SX == DX)
            {
                break;
            }
            else
            {
                swap(v[SX], v[DX]);
                if(SX == pivot)
                {
                    pivot = DX;
                    ++SX;
                }
                else if(DX == pivot)
                {
                    pivot = SX;
                    --DX;
                }
                else
                {
                    ++SX;
                    --DX;
                }
            }
        }
        if(pivot > sx + 1)
        {
            quick_sort(v, sx, pivot - 1, ordine);
        }
        if(pivot < dx - 1)
        {
            quick_sort(v, pivot + 1, dx, ordine);
        }
    }
    
    int main()
    {
        srand(time(0));
        const int n = 7;
        int v[n] = {5, 3, 2, 4, 1, 9, 4};
        quick_sort(v, 0, n - 1, 1);
        mostra_array(v, n);
        cout << endl;
        quick_sort(v, 0, n - 1, -1);
        mostra_array(v, n);
    }
    Secondo voi va bene? Potrei ottimizzarlo in qualche modo?

    Cmq per quanto riguarda la questione iniziale del topic, non basta cambiare semplicemente il segno della diseguaglianza?! Nel mio codice faccio in questo modo e sembra funzionare bene...
    Cambiando il segno infatti non viene risolto il problema perchè non basta. In un algoritmo ingenuo come Insert/Select/Bubble/ecc si èuò fare, ma nel Quick serve un ragionamento più complesso, come chiesto da me nel topic. Comunque si mi sembra un ottimo codice, e hai anche fatto bene (devo abituarmi a farlo anche io) ad usare la notazione prefissa (++var) rispetto a quella postfissa (var++).
  • Re: Quick Sort decrescente

    Cambiando il segno infatti non viene risolto il problema perchè non basta. In un algoritmo ingenuo come Insert/Select/Bubble/ecc si èuò fare, ma nel Quick serve un ragionamento più complesso, come chiesto da me nel topic.
    In realtà, almeno per quanto riguarda il codice che ho postato, sono sicuro che basta invertire le due diseguaglianze per ottenere un ordinamento decrescente. Il ragionamento è semplice, invece di portare a destra del pivot i valori ad esso maggiori porti quelli minori (stessa cosa per i valori da portare a sinistra del pivot)... non capisco perchè dovrebbe servire un ragionamento più complesso, puoi spiegarmelo?

    Considerata la seguente questione che ho sollevato nei miei precedenti post
    Se ho ben capito, al termine della funzione (tralasciamo per il momento la parte iterativa) il pivot scelto dovrà avere alla sua sinistra gli elementi minori e alla sua destra quelli maggiori (trovandosi quindi nella posizione corretta). Ma utilizzando la funzione da te postata sul seguente array

    5 1 2 4 3

    e scegliendo come pivot l'elemento centrale (2 in questo caso), ottengo (ipotizzando di mostrare l'array prima dei due if finali legati alla parte ricorsiva) il seguente array

    2 1 5 4 3

    che evidentemente non rispetta le suddette condizioni.

    Come mai?
    (a cui ancora non è stata data risposta), sinceramente non mi sono soffermato molto sul codice da te postato, quindi non ti so dire con certezza se anche nel tuo caso valga lo stesso ragionamento.
  • Re: Quick Sort decrescente

    Nippolo ha scritto:


    Cambiando il segno infatti non viene risolto il problema perchè non basta. In un algoritmo ingenuo come Insert/Select/Bubble/ecc si èuò fare, ma nel Quick serve un ragionamento più complesso, come chiesto da me nel topic.
    In realtà, almeno per quanto riguarda il codice che ho postato, sono sicuro che basta invertire le due diseguaglianze per ottenere un ordinamento decrescente. Il ragionamento è semplice, invece di portare a destra del pivot i valori ad esso maggiori porti quelli minori (stessa cosa per i valori da portare a sinistra del pivot)... non capisco perchè dovrebbe servire un ragionamento più complesso, puoi spiegarmelo?

    Considerata la seguente questione che ho sollevato nei miei precedenti post
    Se ho ben capito, al termine della funzione (tralasciamo per il momento la parte iterativa) il pivot scelto dovrà avere alla sua sinistra gli elementi minori e alla sua destra quelli maggiori (trovandosi quindi nella posizione corretta). Ma utilizzando la funzione da te postata sul seguente array

    5 1 2 4 3

    e scegliendo come pivot l'elemento centrale (2 in questo caso), ottengo (ipotizzando di mostrare l'array prima dei due if finali legati alla parte ricorsiva) il seguente array

    2 1 5 4 3

    che evidentemente non rispetta le suddette condizioni.

    Come mai?
    (a cui ancora non è stata data risposta), sinceramente non mi sono soffermato molto sul codice da te postato, quindi non ti so dire con certezza se anche nel tuo caso valga lo stesso ragionamento.
    Si, effettivamente soffermandomi sul tuo dovrebbe funzionare. Per la tua domanda alla fin fine è molto simile alla mia, quindi non saprei. Nella risposta di @migliorabile forse qualcosa c'èra
  • Re: Quick Sort decrescente

    Per la tua domanda alla fin fine è molto simile alla mia, quindi non saprei. Nella risposta di @migliorabile forse qualcosa c'èra
    Mi sono guardato meglio il codice che hai postato e confermo che anche in questo caso basta semplicemente invertire le due diseguaglianze.
    Mi sembra strano che tra i vari tentativi che nel primo post dici di aver fatto, tu non abbia provato a farlo.

    Per quanto riguarda il post di migliorabile, tralasciando la FUNZIONE COMPARATRICE, non capisco da dove nasce la questione sull'ORDINE NATIVO dell'oggetto confrontato... un chiarimento sarebbe apprezzato.
  • Re: Quick Sort decrescente

    Per quanto riguarda il post di migliorabile, tralasciando la FUNZIONE COMPARATRICE, non capisco da dove nasce la questione sull'ORDINE NATIVO dell'oggetto confrontato... un chiarimento sarebbe apprezzato.
  • Re: Quick Sort decrescente

    In realtà la cosa più semplice è ordinare e poi invertire il vettore.
    
    quickSort(vettore, 0, dim);
    std::reverse(vettore, vettore + dim);
    
Devi accedere o registrarti per scrivere nel forum
11 risposte