[Risolto] Select sort che non funziona

[link19]

Ho il vettore composto dai numeri
10 22 11 44 10 33 55
Con il select sort viene modificato in qst modo:
10 10 22 44 33 55.
Adesso 33 dovrebbe stare al posto di 44 e non capisco xké.

main.cpp
#include "header.h"

int main(int argc, char *argv[])
{   vettore v1, v2, v3;
    int n1, n2, n3;
    char c1[]="file1.txt";
    char c2[]="file2.txt";
    char c3[]="file3.txt";
    leggiDaFile( v1, n1, c1);
    leggiDaFile( v2, n2, c2);
    leggiDaFile( v3, n3, c3);
    stampaVettore( v1, n1);
    stampaVettore( v2, n2);
    stampaVettore( v3, n3);
    selectSort( v1, n1);
    selectSort( v2, n2);
    selectSort( v3, n3);
    stampaVettore( v1, n1);
    system("PAUSE");
    return EXIT_SUCCESS;
}

header.h
#ifndef HEADER_H
#define HEADER_H
#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

typedef int vettore[100];

void leggiDaFile(vettore , int &, char *);
void stampaVettore(vettore , int);
void selectSort(vettore , int );

#endif

header.cpp
#include "header.h"

void leggiDaFile(vettore v, int &n, char *c){
     fstream f;
     f.open( c, ios::in);
     if(!f) cout<<"Impossibile leggere il file\n";
     else{int i=0;
          while(!f.eof()){
                    f>>v[i];
                    i++;
                    n++;
          }n=i;
     }f.close();
}
void stampaVettore(vettore v, int n){
          cout<<"Il vettore e'\n";
          for(int i=0; i<n; i++){
                  cout<<"v["<<i<<"]: "<<v[i]<<endl;
          }
}
void selectSort(vettore v, int n)
  {
      
       for(int i=0; i<n-1; i++)
         {
               int min=v[i];  
               int pos=i;
               for (int j=i+1; j<n; j++)
                   {
                        if (min>v[j])
                               {
                                     min=v[j];
                                     pos=j;
                               }
                       if (pos!=i)
                         {
                                  int app=v[pos];
                                  v[pos]=v[i];
                                  v[i]=app;
                         }
                   }
         }
}

[Kyuss-RA]

e l'11 dove è andatoa finire?

[link19]

Mi sono semplicemente dimenticato di metterlo

[Kyuss-RA]

Originariamente inviata da link19

Mi sono semplicemente dimenticato di metterlo

se vuoi risolvere questo problema ti consiglio di corregere la funzione selectSort facendo in modo di reinizializzare pos=i; ogni volta che fai lo swap;

 
if (pos!=i)
                         {
                                  int app=v[pos];
                                  v[pos]=v[i];
                                  v[i]=app;
                                   pos=i;
                         }

Se non reinizializzi pos ad i ogni volta che scambi il test (pos!=i) avrà sempre successo e scambierai sempre le due stesse caselle fino alla fine di ogni iterazione. Se gli swap che erroneamente fai in più sono pari non te ne accorgi neanche ma quando sono dispari te ne accorgi e infatti col 33 eil 44 te ne sei accorto.

[M.A.W. 1968]

Sintetizzando e con un uso ampiamente intuitivo dei simboli per gli atomi, il codice dell'inner loop entro la tua versione della selectSort si trova in questa disdicevole situazione di ridondanza logica:

  for (int j = i+1; j < n; ++j)    
  {
    if (A)
    {
        ...
        B
    }
    if (B)
    {
        ...
    }
  }

Tale semantica di invarianza conduce in modo immediato ad applicare l'elementare regoletta di eliminazione - che equivale, con ogni evidenza, al seguente codice, ancora errato:

               for (int j = i+1; j < n; ++j)
               {
                   if (min > v[j])
                  {
                      int app;

                      min = v[j];
                      pos = j;

                      app    = v[pos];
                      v[pos] = v[i];
                      v[i]   = app;
                  }
              }

E' infatti ancora errato (e se funzionasse, sarebbe poco efficiente) l'approccio allo swap effettuato in tale posizione, sugli elementi non corretti. Così quasi quasi si riduce questo nobile algoritmo ad un banale bubblesort !


Proporrei per quella funzione un codice classico, che appare risolutivo del problema segnalato:

    for (int i = 0; i < (len -1); ++i) {
        int minpos = i;
        int min    = v[i];

        for (int j = i +1; j < len; ++j) {
            if (min > v[j]) {
                minpos = j;
                min    = v[j];
            }
        }

        int swp = v[i];
        v[i] = v[minpos];
        v[minpos] = swp;
    }

Il loop così congegnato effettua ricorsivamente una ricerca del minimo nella parte di array non ancora ordinata (a "destra") e lo scambia sistematicamente con l'elemento attualmente indirizzato nell'outer loop. Ne consegue un singolo scambio per iterazione... che viene eseguito sempre, anche nel caso limite in cui non sia necessario (filtrabile comunque con estrema semplicità, subordinandone l'esecuzione al confronto tra minpos e i).

[link19]

E se volessi poi eliminare i numeri che si ripetono?

[Kyuss-RA]

Originariamente inviata da link19

E se volessi poi eliminare i numeri che si ripetono?

io farei una apposita funzioncina che si occupa del compattamento tipo questa

void compattaVettore(vettore , int & );

void compattaVettore(vettore v, int &n){
     for(int i=1; i<n; i++) 
     {
        if (v[i]==v[i-1]) {
           for (int j=i; j<n-1; j++) {
                v[j]=v[j+1];
           }n--;
        }
     }
     
}

ovviamente funziona correttamente solo se il vettore è ordinato, quindi avrebbe senso lanciarla solo dopo aver lanciato la funzione selectSort.

[M.A.W. 1968]

Originariamente inviata da Kyuss-RA

io farei una apposita funzioncina che si occupa del compattamento tipo questa...

Una soluzione in per eliminare i duplicati da un piccolo array è una scelta un tantino troppo radicale al giorno d'oggi...

In un contesto non constrained, il problema si risolve banalmente in tempo lineare. E' necessario e sufficiente fare uso di un array di appoggio, sia pure di dimensione fissa e allocato sullo stack anziché nello heap.
Ecco una possibile soluzione quick'n'dirty:

void killDupes(vettore v, int &n)
{
    vettore tmp;
    int vsize = n;
    int last = tmp[0] = v[0];

    for (int j = 1, n = 1; j < vsize; ++j)
    {
        if (last != v[j])
        {
            tmp[n++] = v[j];
            last = v[j];
        }
    }
    memcpy(v, tmp, --n * sizeof(int));
}

Vale inoltre la pena di rilevare che tutto il codice proposto nel presente thread si presenta come C++, ma in realtà fa uso di idiomi e strutture dati tipiche del C per i vettori.

Per motivi piuttosto complessi, qui chiariti in modo sufficientemente approfondito alla luce degli opportuni riferimenti, in C++ gli array del C sono deprecati e dovrebbero cedere il posto alle strutture specializzate (vere e proprie classi OOP) come vector o valarray.

Nulla di male in questo caso, poiché i basilari array C hanno una enorme validità didattica intrinseca nella loro primitiva modellazione della memoria fisica del PC, ma è opportuno esserne consapevoli.

[Kyuss-RA]

Originariamente inviata da M.A.W. 1968

Una soluzione in per eliminare i duplicati da un piccolo array è una scelta un tantino troppo radicale al giorno d'oggi...

In un contesto non constrained, il problema si risolve banalmente in tempo lineare. E' necessario e sufficiente fare uso di un array di appoggio, sia pure di dimensione fissa e allocato sullo stack anziché nello heap.
Ecco una possibile soluzione quick'n'dirty:

void killDupes(vettore v, int &n)
{
    vettore tmp;
    int vsize = n;
    int last = tmp[0] = v[0];

    for (int j = 1, n = 1; j < vsize; ++j)
    {
        if (last != v[j])
        {
            tmp[n++] = v[j];
            last = v[j];
        }
    }
    memcpy(v, tmp, --n * sizeof(int));
}

Vale inoltre la pena di rilevare che tutto il codice proposto nel presente thread si presenta come C++, ma in realtà fa uso di idiomi e strutture dati tipiche del C per i vettori.

Per motivi piuttosto complessi, qui chiariti in modo sufficientemente approfondito alla luce degli opportuni riferimenti, in C++ gli array del C sono deprecati e dovrebbero cedere il posto alle strutture specializzate (vere e proprie classi OOP) come vector o valarray.

Nulla di male in questo caso, poiché i basilari array C hanno una enorme validità didattica intrinseca nella loro primitiva modellazione della memoria fisica del PC, ma è opportuno esserne consapevoli.

Hai stra ragione su tutto. E' che io sono un bagordo della programmazione e non sto a guardare tanto alla complessita computazionale (specie quando so già che n<=100 e lo stesso algoritmo d'ordinamento , come giustamente avevi fatto notare tu, non è proprio il più ottimale) e vado al sodo.
Comunque complimenti hai una cultura informatica impressionante. Knuth ti fa un baffo.

[M.A.W. 1968]

Originariamente inviata da Kyuss-RA

Knuth ti fa un baffo.

Magari ! Donald E. Knuth è un mostro sacro, mi contenterei di avere un briciolo del suo eccezionale talento.

Tuttavia, come si può facilmente rilevare qui oppure qui e soprattutto qui, è un fatto vero che il Gotha della computer science mondiale over 50 si mostra inusualmente privo di barba...