Ancora selection sort C++

  • Autore discussione Autore discussione MPG
  • Data d'inizio Data d'inizio
Pubblicità
MPG ha detto:
SCusa io ho 3 specifiche
1) ordinamento crescente
2) ordinamento decrescente
3) ordinamento casuale

Poniamo che i numeri siano 4, 9, 3, 10 , 7
quindi nel primo caso sono è l'ordin eè 3,4, 7,9,10, nel secondo 10,9,7,4,3 nel terzo caso se voglio un ordinamento casuale (es, 9,4,10,7, 3) esiste il modo o l'ordinamento casuale si intende quando usi il rand e vengono dei nuemri casuali e quindi non applichi ne' il selsort ne' il bubble perchè con il rand hai apunti dei numeri a caso?
Clicca per espandere...
Ahhh allora è semplicissimo.
Bisogna usare i vettori <vector> così non bisogna creare copie.
C++: 
#include <vector>
using namespace std;

int main()
{
    const int dim = 5;
    vector<int, dim> vettore;
    //Normale inserimento dei valori, come con un normale vettore fatto con il puntatore...
}
Poi si fa con le funzioni. Una funzione ad esempio è
C++: 
double bubbleSort(vector <int> v, int dim, bool (*cmp)(const int&, const int&))
{
    auto puntoA = high_resolution_clock::now();
     // il resto ma nell’if scrivi
  ...
      if((*cmp)(v[j], v[j+1]))
       ...
}

Quel che vai a fare è passare come parametro la condizione che ti dice come ordinarlo. Sfortunatamente si deve fare passando come parametro una funzione. Quando chiami la funzione scrivi
C++: 
bubbleSort(vettore, dim, &greater<int>) //per ordinamento crescente
bubbleSort(vettore, dim, &less<int>) //per ordinamento decrescente
 
Mamma mia _Achille mi parli sempre di cose nuove..

#include <vector>
o
bubbleSort(vettore, dim, &greater<int>)

Io pensavo di scrivere l'array definita la dimensione e mettendo i valori manualmente o con il rand e applico il selsort o il bubble sort creando l'ordinamento crescente o descrescente, senz aulteriori pensieri.
MI manca solo di capire come creare un ordinamento casuale ....... perchè non so se con sel sort o con bubble sort si puo' creare un ordinamento casuale.
 
MPG ha detto:
Mamma mia _Achille mi parli sempre di cose nuove..

#include <vector>
o
bubbleSort(vettore, dim, &greater<int>)

Io pensavo di scrivere l'array definita la dimensione e mettendo i valori manualmente o con il rand e applico il selsort o il bubble sort creando l'ordinamento crescente o descrescente, senz aulteriori pensieri.
MI manca solo di capire come creare un ordinamento casuale ....... perchè non so se con sel sort o con bubble sort si puo' creare un ordinamento casuale.
Clicca per espandere...
Devi fare troppe copie dell’array... non ti costa nulla scrivere vector <int> vettore. È un tipo, precisamente una classe ed è molto comoda perché viene copiata senza copiare l’indirizzo di memoria per il puntatore (che è il vettore vero e proprio, l’array).
Si usa come i vettori normali, con [].

Puoi con il SelecSort integrare i due insieme, operando su uno con > e con l’altro <. Il BubbleSort fatto da te richiede proprio due cicli diversi, quindi ce ne vanno due.
Resto dell’idea che passare la condizione come parametro è l’idea migliore. Si scrive moooolto meno ed esce una cosa ordinata
 
Dunque parlando con un compagno anche lui farà 3 array piccoli e li ordinerà in 3 programmi diversi e cosi' anche per gli array grandi.
Fin qui si puo' fare senza problemi e fare cose mai fatte poi il prof pensa che le abbiamo copiate da qualche parte e non fatte noi.. quindi meglio fare quello che sappiamo (e quello che mi hai insegnato tu anche...)
Per il discorso ordinamento casuale (lasciano da parte vector etc..) cosi' si puo' fare:

Codice: 
#include <iostream>
#include <algorithm>
#include <ctime>

using namespace std;

int main()
{srand (time (0));
    int i;
    int a[10]={5,21,12,30,44,51,16,71,82,19};

    for (i = 0; i < 10; i++)
    {
        cout << a[i];
    }
    cout << endl;

    random_shuffle(&a[0],&a[10]);

    for (i = 0; i < 10; i++)
    {
        cout << a[i]<<endl;
    }
    cout << endl;
}

C'è questa funzione nuova random_shuffle , pero' è solo questa.
La questione è : con selection sort o bubble sort si puo' e come ordinare casualmente un array, dati i valori dell'array?
Questo è l'ultimo dubbio/problema rimasto...
 
Ultima modifica:
MPG ha detto:
Dunque parlando con un compagno anche lui farà 3 array piccoli e li ordinerà in 3 programmi diversi e cosi' anche per gli array grandi.
Fin qui si puo' fare senza problemi e fare cose mai fatte poi il prof pensa che le abbiamo copiate da qualche parte e non fatte noi.. quindi meglio fare quello che sappiamo (e quello che mi hai insegnato tu anche...)
Per il discorso ordinamento casuale (lasciano da parte vector etc..) cosi' si puo' fare:

Codice: 
#include <iostream>
#include <algorithm>
#include <ctime>

using namespace std;

int main()
{srand (time (0));
    int i;
    int a[10]={5,21,12,30,44,51,16,71,82,19};

    for (i = 0; i < 10; i++)
    {
        cout << a[i];
    }
    cout << endl;

    random_shuffle(&a[0],&a[10]);

    for (i = 0; i < 10; i++)
    {
        cout << a[i]<<endl;
    }
    cout << endl;
}

C'è questa funzione nuova random_shuffle , pero' è solo questa.
La questione è : con selection sort o bubble sort si puo' e come ordinare casualmente un array, dati i valori dell'array?
Questo è l'ultimo dubbio/problema rimasto...
Clicca per espandere...
Se si definisce un algoritmo di sorting non può essere un algoritmo random.
È un ossimoro, come dire che il bene è male...
 
_Achille ha detto:
Non so se hai capito che un ordinamento non può essere casuale per definizione...
Clicca per espandere...

Ho capito pero' io ribadisco la consegna da fare a casa :
"Creare 3 array "piccoli" e 3 array "grandi" ordinati risp. in ordine crescente, decrescente e casuale. Testare BubbleSort e SelectionSort sugli array annotando i tempi di esecuzione. La codifica degli algoritmi e la tabella con tempi e confronti va stampata su carta. "

Dimmi a questo punto come interpreti un array ordinato in ordine"casuale".. non ho scritto io questa consegna non so che dire...
Per assurdo puo' essere un ordinamento che casualmente puo' essere crescente o decrescente, e cosi' fosse come di fa??
 
MPG ha detto:
Dimmi a questo punto come interpreti un array ordinato in ordine"casuale".. non ho scritto io questa consegna non so che dire...
Per assurdo puo' essere un ordinamento che casualmente puo' essere crescente o decrescente, e cosi' fosse come di fa??
Clicca per espandere...

C'è poco da interpretare... significa un array con elementi disposti in maniera casuale (eg. non ordinato). Se popoli un array con N elementi usando rand(), saranno già disposti in modo casuale, non ordinato.
 
Quindi mettiamo di creare un array (piccolo o grande che sia), per il crescente o decrescente devo io inserire manualmente i numeri perchè non posso usare il rand se lo uso per l' ordinamento diciamo "casuale" giusto?
Ma se cosi fosse dovendo valutare il tempo di esecuzione del sort ed essendo questo sempre 0 se non uso valori di dimensione dell'array tipo 1500 non posso inserire manualmente 1500 valori...
Esempio qui uso il rand per n=1500 se non usassi il rand e devo poi ordinarli dovrei scrivere 1500 numeri mi pare ovviamente improponibile...
Oppure tu pensi di usare sia per l'array crescente che decrescente il rand per dare i valori e poi utilizzare i vari sort per l'ordinamento, mentre per l'ordinamento casuale per "definizione" l'ordine casuale non puo' essere ordinato ed il risultato e quello della randomizzazione (quindi qui non uso nessun sort e non posso calcolare alcun time sort)? Insomma mi pongo questi dubbi....

Codice: 
#include <iostream>
#include <ctime>
#include<cstdlib>
#include <chrono>


using namespace std;
using namespace chrono;


int main()

{int i, j;

srand(time(NULL));
const int n = 1500;
int vet[n];
int tmp;
for(int i=0;i<n;i++)
vet[i]=rand();


auto inizio = high_resolution_clock::now();

for (int i = 0; i < n; i++)

{
      for(int j=i+1; j < n; j++)
{
       if(vet[j]<vet[i])
{

        int tmp =vet[i];
        vet[i]=vet[j];
        vet[j]=tmp;

}
}
}
auto fine = high_resolution_clock::now();
cout <<duration_cast<duration<double>>(fine - inizio).count();
  }

[/CODE}
 
Ultima modifica:
MPG ha detto:
Quindi mettiamo di creare un array (piccolo o grande che sia), per il crescente o decrescente devo io inserire manualmente i numeri perchè non posso usare il rand se lo uso per l' ordinamento diciamo "casuale" giusto?
Ma se cosi fosse dovendo valutare il tempo di esecuzione del sort ed essendo questo sempre 0 se non uso valori di dimensione dell'array tipo 1500 non posso inserire manualmente 1500 valori...
Esempio qui uso il rand per n=1500 se non usassi il rand e devo poi ordinarli dovrei scrivere 1500 numeri mi pare ovviamente improponibile...
Oppure tu pensi di usare sia per l'array crescente che decrescente il rand per dare i valori e poi utilizzare i vari sort per l'ordinamento, mentre per l'ordinamento casuale per "definizione" l'ordine casuale non puo' essere ordinato ed il risultato e quello della randomizzazione (quindi qui non uso nessun sort e non posso calcolare alcun time sort)? Insomma mi pongo questi dubbi....

Codice: 
#include <iostream>
#include <ctime>
#include<cstdlib>
#include <chrono>


using namespace std;
using namespace chrono;


int main()

{int i, j;

srand(time(NULL));
const int n = 1500;
int vet[n];
int tmp;
for(int i=0;i<n;i++)
vet[i]=rand();


auto inizio = high_resolution_clock::now();

for (int i = 0; i < n; i++)

{
      for(int j=i+1; j < n; j++)
{
       if(vet[j]<vet[i])
{

        int tmp =vet[i];
        vet[i]=vet[j];
        vet[j]=tmp;

}
}
}
auto fine = high_resolution_clock::now();
cout <<duration_cast<duration<double>>(fine - inizio).count();
  }

[/CODE}
Clicca per espandere...
Non cambia nulla. Che tu lo metta in ordine casuale o che lo metta già il computer è uguale. Non esiste un ordinamento casuale. In quel caso lo si lascia così come è
 
Pubblicità
Pubblicità
Indietro
Top