Ancora selection sort C++

MPG · 26 Maggio 2018

Il libro è "Programmare con C++" di Cesare Rota.
Ho rifatto il code, mi ero accorto di aver messo un ; nella penultima riga dove c'è il for, ora viene , mi pare tutto ok o no?
Per il discorso che se "n=10 scorrere da 0 a 9 o scorrere da 1 a 10 è la stessa cosa, si tratta sempre di 10 elementi"
ma se metto
i=0;i<n;i++;
qui non è tra 0 e 9
se
i=1;i<n;i++;
sarebbe tra 1 e 9
o sbaglio?
Infatti se metto
i=1;i<n;i++;
il sort non viene....

Codice:

#include <iostream>
#include <ctime>
#include<cstdlib>


using namespace std;


int main()

{int i, j;

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


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;

}
}
}

    for (int i = 0; i <n; i++)
    {
    cout<<vet[i]<<endl;
    }
}

_Achille · 26 Maggio 2018

MPG ha detto:
Il libro è "Programmare con C++" di Cesare Rota.
Ho rifatto il code, mi ero accorto di aver messo un ; nella penultima riga dove c'è il for, ora viene , mi pare tutto ok o no?
Per il discorso che se "n=10 scorrere da 0 a 9 o scorrere da 1 a 10 è la stessa cosa, si tratta sempre di 10 elementi"
ma se metto
i=0;i<n;i++;
qui non è tra 0 e 9
se
i=1;i<n;i++;
sarebbe tra 1 e 9
o sbaglio?
Infatti se metto
i=1;i<n;i++;
il sort non viene....

Codice:

#include <iostream> #include <ctime> #include<cstdlib> using namespace std; int main() {int i, j; srand(time(NULL)); const int n = 5; int vet[n]; int tmp; for(int i=0;i<n;i++) vet[i]=rand(); 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; } } } for (int i = 0; i <n; i++) { cout<<vet[i]<<endl; } }

Scusami eh, ma 0->9 e 1->10 sono due implementazioni diverse...

C++:

for (int i = 0; i < 10; i++); //va da 0 a 9
for (int i = 1; i <= 10; i++); //va da 1 a 10
for (int i = 1; i < 10; i++); //va da 1 a 9

Queste differenze dovresti coglierle da solo ormai...

Se devi accedere agli elementi di un vettore direttamente con i devi usare da 0 a 9, altrimenti uno qualsiasi va bene che venga eseguito 10 volte, anche 100->109 volendo.

E inizia ad usare i TAB e fare ordine al codice che fare debug è quasi impossibile pure in 5 righe così...

MPG · 26 Maggio 2018

_Achille ha detto:
Scusami eh, ma 0->9 e 1->10 sono due implementazioni diverse...

C++:

for (int i = 0; i < 10; i++); //va da 0 a 9 for (int i = 1; i <= 10; i++); //va da 1 a 10 for (int i = 1; i < 10; i++); //va da 1 a 9

Queste differenze dovresti coglierle da solo ormai...

Se devi accedere agli elementi di un vettore direttamente con i devi usare da 0 a 9, altrimenti uno qualsiasi va bene che venga eseguito 10 volte, anche 100->109 volendo.

E inizia ad usare i TAB e fare ordine al codice che fare debug è quasi impossibile pure in 5 righe così...

SI scusa se n=10
per
i=1;i<n;i++;
sarebbe tra 1 e 10
il 9 l'avevo scritto perchè stavo pensando a quel tuo
0 -> n-1 va quanto 1 -> n
Poichè come detto lo psudocodice da seguire era.
per n=1,2....ripeti
pensavo si dovesse mettere
i=1;i<n;i++;
solo che appunto cosi' il sort non viene....

Per discorso debug.. c'è un programma migliore di codeblock per capire meglio gli errori che si fanno nel codice?

MPG · 26 Maggio 2018

Anche qui dovrei metter il tempo di esecuzione , va bene cosi'?

Codice:

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();
    }

DispatchCode · 26 Maggio 2018

MPG ha detto:
SI scusa se n=10
per
i=1;i<n;i++;
sarebbe tra 1 e 10
il 9 l'avevo scritto perchè stavo pensando a quel tuo
0 -> n-1 va quanto 1 -> n
Poichè come detto lo psudocodice da seguire era.
per n=1,2....ripeti
pensavo si dovesse mettere
i=1;i<n;i++;
solo che appunto cosi' il sort non viene....

Si, in quanto nel secondo caso non accedi mai alla locazione 0 (quindi sono diverse).
Ad esempio, per stare sempre un pò sul "teorico", il tuo for esterno compie N iterazioni, mentre quello interno ne compie N-1. Questo perchè nel primo for hai la i che va da 0 ad N; mentre nel secondo caso hai la j che va da i+1 ad N.

MPG ha detto:
Ho rifatto il code, mi ero accorto di aver messo un ; nella penultima riga dove c'è il for, ma non viene...
Viene una lunga seria di numeri...

Dovresti tenere il codice più ordinato:

C++:

#include <iostream>
#include <ctime>
#include <cstdlib>


using namespace std;

int main()
{
  const int n = 5;
  int i, j;

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

  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;
      }
    }
  }
  
  for (int i = 0; i <n; i++)
  {
    cout << vet[i];
  }

  return 0;
}

Purtroppo sta a te metterti di buona lena, e capire come funzionano le cose. Se stampi con cout, dovresti sapere che il carattere di nuova linea non è presente ma lo devi aggiungere tu. Inoltre stai popolando l'array con elementi casuali senza un range.

MPG · 26 Maggio 2018

Io ho questo ultimo problema guardando la consegna che alla fine è questa:
"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.
"
Come fare il tutto in un singolo esercizio.....
L'array decrescente l'avevo fatto a scuola cosi':

Codice:

#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
using namespace std;

int main()
{
  srand(time(NULL));
  int dim;
  cout<<"Inserisci dim: "<<endl;
  cin>>dim;
  cout<<endl;
int A[dim];
A[dim-1]=100;
cout<<A[dim-1]<<endl;
for(int i=dim-1;i>0;i--)
{
A[i-1]=A[i]-(rand()%10+1);
cout<<A[i-1]<<endl;
}

    return 0;
}

e il crescente cosi':

Codice:

#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
using namespace std;

int main()
{
  srand(time(NULL));
  int dim;
  cout<<"Inserisci dim: "<<endl;
  cin>>dim;
  cout<<endl;
int A[dim];
A[0]=rand()%10;
cout<<A[0]<<endl;
for(int i=1;i<dim;i++)
{
A[i]=A[i-1]+rand()%10+1;
cout<<A[i]<<endl;
}

    return 0;
}

Non so se si possono scrivere meglio, ma come inserisco in unico esercizio questi array decrescente e crescente e quello causale e testo sia sort che selection sort?????
E' un procedimento lungo e complesso per me..

_Achille · 26 Maggio 2018

MPG ha detto:
Io ho questo ultimo problema guardando la consegna che alla fine è questa:
"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.
"
Come fare il tutto in un singolo esercizio.....

Ma perché caz*o il tuo prof ti da il tempo di esecuzione quando manco te lo ha spiegato?!?

L'ideale è creare un matrice 3x2xnumeroDiElementiDelPiccolo e una 3x2xnumeroDiElementiDelGrande. Poi li si passa come parametri ad una funzione selectionSort e bubbleSort. Tipo così.

C++:

for (int i = 0; i < 3; i++)  // 0 -> crescente, 1 -> decrescente, 2 -> casuale
{
   cout << "Tempo con selection: " << selectionSort(matPiccoli[i][0], nPiccoli) << endl; 0->elementi che vanno ordinati per selezione
   cout << "Tempo con bubble: " << bubbleSort(matPiccoli[i][1], nPiccoli) << endl; 1-> elementi che vanno ordinati per bubble
   cout << endl;
}

Le funzioni hanno questo aspetto poi

C++:

double bubbleSort(int *array, size_t dim)
{
    auto puntoA = high_resolution_clock::now();
    //... sorting, puntoB e tempoDiSorting
    return tempoDiSorting;
}

Lavoraccio inutile. E non ho mai lavorato con matrici tridimensionali, quindi non so nemmeno se il passaggio come parametro è coretto...

MPG · 26 Maggio 2018

Ora capisci anche perchè ho problemi di comprensione...
Mettiamo che devi solo creare 3 array "piccoli" e 3 array "grandi" ordinati risp. in ordine crescente, decrescente e casuale senza calcolare il tempo , si puo' fare e come tutto questo in un esercizio? A me pare complesso.. poi pensero' (penseremo) ai tempi...

_Achille · 26 Maggio 2018

MPG ha detto:
Ora capisci anche perchè ho problemi di comprensione...
Mettiamo che devi solo creare 3 array "piccoli" e 3 array "grandi" ordinati risp. in ordine crescente, decrescente e casuale senza calcolare il tempo , si puo' fare e come tutto questo in un esercizio? A me pare complesso.. poi pensero' (penseremo) ai tempi...

Ma no non è il tempo il problema. È tutto il casino. Se devi fare 3 array grandi e 3 piccoli devi farne 12, uno ordinato con Bubble e l’altro con Selection. 6x2=12.
L’ideale è quello che ti ho scritto sopra. Due matrici per tipo

MPG · 26 Maggio 2018

non so cosa siano le matrici.... e' sempre quello il punto..

MPG · 26 Maggio 2018

Guarda sono veramente fuso.. fare informatica cosi' è dura, bisognerebbe capirla meglio a scuola..
Sono cosi' fuso che ora qui se non voglio mettere i valori che non siano casuali ma in ordinamento crescente (senza usare selection o bubble) ma usando questa codifica cosa devo fare?
Vorrei capire anche nell'array crescente è stato usato a scuola
A[0]=rand()%10; quindi da 0 a 9
A=A[i-1]+rand()%10+1; quindi il rand è da 1 a 10
nell'array descrescente
A[dim-1]=100; e perchè non A[0] invece di usare A[dim -1]
.........
for(int i=dim-1;i>0;i--)
{
A[i-1]=A-(rand()%10+1);

Codice:

#include <cstdlib> #include <ctime> #include <cmath> #include <iostream> using namespace std; int main() { srand(time(NULL)); int dim; cout<<"Inserisci dim: "<<endl; cin>>dim; cout<<endl; int A[dim]; A[0]=rand()%10; cout<<A[0]<<endl; for(int i=1;i<dim;i++) { A[i]=A[i-1]+rand()%10+1; cout<<A[i]<<endl; } return 0; }

_Achille · 26 Maggio 2018

MPG ha detto:
non so cosa siano le matrici.... e' sempre quello il punto..

Sono array a più dimensioni. Sai che un vettore è una specie di “lista”, detta così male. Una matrice di solito intende un array a due dimensioni, ovvero un “rettangolo”. Ci sono le righe e le colonne.
Quella che ti faccio usare è a tre dimensioni, che puoi immaginare come un parallelepipedo. Il primo numero indica se è crescente, decrescente o random mentre la seconda indica se è per BubbleSort o Selection.
Perché differenziare i casi se si usa una funzione? (Se non lo sai se non usi un puntatore o una variabile reference come parametro le modifiche che fai nella funzione non intaccano la variabile). Perché il C è così simpatico da considerare i vettori puntatori e perciò le modifiche lì vengono ben “salvate”!

Quindi ti dichiari la matrice così

C++:

int matricePiccola[3][2][<numeroDiElementiPiccolo>];
int matriceGrande[3][2][<numeroDiElementiGrande>];
//Dove <nDEP> è più piccolo di <nDEG>.

Poi li popoli

C++:

matricePiccola[0][0][0] = matricePiccola[0][1][0] = rand() % 1000;
for (int i = 1; i < <nDEP>; i++)
{
     matricePiccola[0][0][i] = matricePiccola[0][1][i] = matricePiccola[0][0][i - 1] + rand() % 100;
}

//per la decrescenza
matricePiccola[1][0][0] = matricePiccola[1][1][0] = rand() % 1000;
for (int i = 1; i < <nDEP>; i++)
{
     matricePiccola[1][0][i] = matricePiccola[1][1][i] = matricePiccola[1][0][i - 1] - rand() % 100;
}

//per il random
for (int i = 0; i < <nDEP>; i++)
{
     matricePiccola[2][0][i] = matricePiccola[2][1][i] = rand() % 1000;
}

E si rifà la stessa cosa per la matriceGrande, poi si passa l'indirizzo alle funzioni che ti stampano i tempi

MPG · 26 Maggio 2018

MPG ha detto:
Guarda sono veramente fuso.. fare informatica cosi' è dura, bisognerebbe capirla meglio a scuola..
Sono cosi' fuso che ora qui se non voglio mettere i valori che non siano casuali ma in ordinamento crescente (senza usare selection o bubble) ma usando questa codifica cosa devo fare?
Vorrei capire anche nell'array crescente è stato usato a scuola
A[0]=rand()%10; quindi da 0 a 9
A=A[i-1]+rand()%10+1; quindi il rand è da 1 a 10
nell'array descrescente
A[dim-1]=100; e perchè non A[0] invece di usare A[dim -1]
.........
for(int i=dim-1;i>0;i--)
{
A[i-1]=A-(rand()%10+1);

Codice:

#include <cstdlib> #include <ctime> #include <cmath> #include <iostream> using namespace std; int main() { srand(time(NULL)); int dim; cout<<"Inserisci dim: "<<endl; cin>>dim; cout<<endl; int A[dim]; A[0]=rand()%10; cout<<A[0]<<endl; for(int i=1;i<dim;i++) { A[i]=A[i-1]+rand()%10+1; cout<<A[i]<<endl; } return 0; }

A questo punto anche se comprendo che si possa fare con le matrici se non le ho studiate perchè non spiegate io a questo punto creo vari array separati e su quelli testo il bubble sort e selection sort, non si puo' risolvere la questione usando metodi mai insegnati , penso che concordi!
MI potresti solo spiegare i dubbi del modo di ordinare i vettori in maniera crescente o decrescente fatto a scuola ?
Ma poi una cosa se questo è il bubble crescente e il selsort crescente

Codice:

#include <iostream>

using namespace std;

int main()
{


const int n = 3;
int vet[n];
int tmp;
for(int i=0;i<n;i++)
{
    cin>>vet[i];
}
cout<<endl;
bool flag = true;
int stop = n - 1;

while (flag)
{
    flag = false;
    for (int i = 0; i < stop; i++)
        if (vet[i] > vet[i + 1])
        {
                   tmp=vet[i];
            vet[i]=vet[i+1];
            vet[i+1]=tmp;
            flag = true;
        }

    stop = stop - 1;
}
for(int i=0;i<n; i++)
{
    cout<<vet[i]<<endl;
}
}

e questo è il selection sort crescente

Codice:

#include <iostream>
#include <ctime>
#include<cstdlib>


using namespace std;


int main()

{int i, j;

const int n = 5;
int vet[n];
int tmp;
for(int i=0;i<n;i++)
vet[i]=rand();

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;

}
}
}

    for (int i = 0; i <n; i++)
    {
    cout<<vet[i]<<endl;
    }
}

Come si opera per ordinare gli array casualmente come in consegna? E' un non ordinamento... caspita.
Dovrei usare il metodo di selsort e di bubble sort per un ordinamento pero' casuale ma come??
INsomma per ordinamento crescente e decrescente uso sia selsort che bubble sort, per l'ordinamento casuale??

_Achille · 26 Maggio 2018

MPG ha detto:
A questo punto anche se comprendo che si possa fare con le matrici se non le ho studiate perchè non spiegate io a questo punto creo vari array separati e su quelli testo il bubble sort e selection sort, non si puo' risolvere la questione usando metodi mai insegnati , penso che concordi!
MI potresti solo spiegare i dubbi del modo di ordinare i vettori in maniera crescente o decrescente fatto a scuola ?
Ma poi una cosa se questo è il bubble crescente e il selsort crescente

Codice:

#include <iostream> using namespace std; int main() { const int n = 3; int vet[n]; int tmp; for(int i=0;i<n;i++) { cin>>vet[i]; } cout<<endl; bool flag = true; int stop = n - 1; while (flag) { flag = false; for (int i = 0; i < stop; i++) if (vet[i] > vet[i + 1]) { tmp=vet[i]; vet[i]=vet[i+1]; vet[i+1]=tmp; flag = true; } stop = stop - 1; } for(int i=0;i<n; i++) { cout<<vet[i]<<endl; } }

e questo è il selection sort crescente

Codice:

#include <iostream> #include <ctime> #include<cstdlib> using namespace std; int main() {int i, j; const int n = 5; int vet[n]; int tmp; for(int i=0;i<n;i++) vet[i]=rand(); 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; } } } for (int i = 0; i <n; i++) { cout<<vet[i]<<endl; } }

Come si opera per ordinare gli array casualmente come in consegna? E' un non ordinamento... caspita.
Dovrei usare il metodo di selsort e di bubble sort per un ordinamento pero' casuale ma come??
INsomma per ordinamento crescente e decrescente uso sia selsort che bubble sort, per l'ordinamento casuale??

Non devi ordinarli in modo diverso. Hai 3 array sistemati così e l’ordinamento è sempre lo stesso.
Comunque devi usare le funzioni

MPG · 26 Maggio 2018

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 l'ordine è 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 appunto dei numeri a caso?
Io interpreto che devo creare dati tot numeri un ordinamento casuale (che non sia ne' crescente ne' decrescente..).
Per sempio ho trovato questo:

Codice:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
/*   int a[10]={5,21,12,30,44,51,16,71,82,19};

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

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

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

che si puo' metter anche cosi'

Codice:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    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;
}

che fa un ordinamento casuale ma vedo che poi anche se i numeri no sono ordinati ne' in senso crescente che decrescente viene sempre lo stesso risultato.

Ancora selection sort C++

MPG

Utente Attivo

_Achille

MPG

Utente Attivo

MPG

Utente Attivo

DispatchCode

MPG

Utente Attivo

_Achille

MPG

Utente Attivo

_Achille

MPG

Utente Attivo

MPG

Utente Attivo

_Achille

MPG

Utente Attivo

_Achille

MPG

Utente Attivo