DOMANDA Bubble sort in array C++

[BigMarioss]

Buongiorno ragazzi mi servirebbe una mano... Al suo quarto passaggio il ciclo interno fa diventare j = N-1 pari ad indice [0], ma quindi che succede alla condizione dell'if ( a[j-1] )? Non è possibile che diventi indice [-1]... e poi un'altra cosa, non riesco a capire il nesso che c'è tra i e j... quando il ciclo interno terminerà, il ciclo esterno aumenterà i a indice [1], ma cosa comporta questo? I numeri non sono già stati controllati tutti?

#define MAX 4

int main(){

int a[MAX] = {8, 20, 9, 7};
  int i, N, j, temp;


for (i=0; i < N-1; i++){
    for (j = N - 1; j > i; j--){
      if (a[j-1] > a[j]){
        temp = a[j-1];
        a[j-1] = a[j];
         a[j] = temp;
      }
    }
  }

 

[_Achille]

Usa [ CODE = C ] [/CODE] (senza spazi) per inserire codice.
Stai usando MAX e N. Usa una dei due. Così.

const int n = 10;
int array[n];

i va da 0 a 2.
j va da 3 a i +1
Ci saranno queste sequenze per j
3 2 1
3 2
3

 

[stemare]

C'è qualcosa che non va nel codice

Al suo quarto passaggio il ciclo interno fa diventare j = N-1 pari ad indice [0], ma quindi che succede alla condizione dell'if ( a[j-1] )? Non è possibile che diventi indice [-1]...

infatti al quarto passaggio ti andrebbe in errore, non può funzionare.

non riesco a capire il nesso che c'è tra i e j... quando il ciclo interno terminerà, il ciclo esterno aumenterà i a indice [1], ma cosa comporta questo? I numeri non sono già stati controllati tutti?

L'unica cosa di cui sei certo dopo il primo giro del ciclo interno, è che il numero minore (nel tuo caso 7) si troverà in posizione 0, quindi aumenti la i e rifai il giro saltando il primo numero.
Dopo il secondo giro sarai sicuro che in posizione 1 avrai il numero successivo, quindi 8, e così via...

 

[BigMarioss]

C'è qualcosa che non va nel codice


infatti al quarto passaggio ti andrebbe in errore, non può funzionare.


L'unica cosa di cui sei certo dopo il primo giro del ciclo interno, è che il numero minore (nel tuo caso 7) si troverà in posizione 0, quindi aumenti la i e rifai il giro saltando il primo numero.
Dopo il secondo giro sarai sicuro che in posizione 1 avrai il numero successivo, quindi 8, e così via...

Ragazzi non ho capito...

 

[stemare]

Forse un'animazione del genere ti fa capire meglio come funziona il bubble sort rispetto alle parole.
https://cathyatseneca.github.io/DSAnim/web/bubble.html

Così dovresti capire anche a cosa serve il ciclo esterno.

 

[BigMarioss]

Forse un'animazione del genere ti fa capire meglio come funziona il bubble sort rispetto alle parole.
https://cathyatseneca.github.io/DSAnim/web/bubble.html

Così dovresti capire anche a cosa serve il ciclo esterno.

Sì ma io l'ho capito il funzionamento, il problema è nella pratica... arrivo ad un punto in cui al suo quarto passaggio il ciclo interno fa diventare j = N-1 pari ad indice [0], ma quindi che succede alla condizione dell'if ( a[j-1] )? Non è possibile che j verifichi un indice [-1]... o sbaglio?

E poi ho notato che il dato 7 situato nella cella [3] non verrà mai calcolato perchè c'è N-1... vi prego aiutatemi a capire

 

[stemare]

Sì ma io l'ho capito il funzionamento, il problema è nella pratica... arrivo ad un punto in cui al suo quarto passaggio il ciclo interno fa diventare j = N-1 pari ad indice [0], ma quindi che succede alla condizione dell'if ( a[j-1] )? Non è possibile che j verifichi un indice [-1]... o sbaglio?

Non è possibile che j sia 0 all'interno del ciclo perché c'è la condizione "j > i".
Al quarto giro, quando j = 0, la condizione "j > i" ossia "0 > 0" non è più vera e il processo esce dal ciclo.

E poi ho notato che il dato 7 situato nella cella [3] non verrà mai calcolato perchè c'è N-1... vi prego aiutatemi a capire

premesso che non ho capito dove inizializzi N, in ogni caso N non dovrebbe essere 4 giusto? quindi N-1 = 3, e quindi la cella [3] viene presa in considerazione al primo giro del ciclo interno.

 

[_Achille]

C'è qualcosa che non va nel codice


infatti al quarto passaggio ti andrebbe in errore, non può funzionare.


L'unica cosa di cui sei certo dopo il primo giro del ciclo interno, è che il numero minore (nel tuo caso 7) si troverà in posizione 0, quindi aumenti la i e rifai il giro saltando il primo numero.
Dopo il secondo giro sarai sicuro che in posizione 1 avrai il numero successivo, quindi 8, e così via...

A me non sembra scorretto (tranne per N e MAX). J non andrà mai a 0, quindi j-1 non sarà mai -1

 

[stemare]

A me non sembra scorretto (tranne per N e MAX). J non andrà mai a 0, quindi j-1 non sarà mai -1

Sì, purtroppo ho dato la prima risposta un po' di fretta, c'è la condizione che impedisce a j di andare a 0.

 

[BigMarioss]

Ragazzi potete anche cancellare la discussione, ho risolto... sono io che sono stupido! In pratica avevo scritto in un foglio:

Dato 1=8
Dato 2= 20
Dato 3= 9
Dato 4= 7

Cosa facevo io? In pratica, quando andavo ad analizzare il primo indice, confondevo il fatto che gli indici vengono visualizzati da 0 a 3 e non da 1 a 4! Quindi associavo ad esempio l'indice 3 (l'ultimo) al dato 3 (penultimo).... non so se mi spiego!

 

[_Achille]

Ragazzi potete anche cancellare la discussione, ho risolto... sono io che sono stupido! In pratica avevo scritto in un foglio:

Dato 1=8
Dato 2= 20
Dato 3= 9
Dato 4= 7

Cosa facevo io? In pratica, quando andavo ad analizzare il primo indice, confondevo il fatto che gli indici vengono visualizzati da 0 a 3 e non da 1 a 4! Quindi associavo ad esempio l'indice 3 (l'ultimo) al dato 3 (penultimo).... non so se mi spiego!

In realtà l’indice non va mai a 4...

 

[BigMarioss]

In realtà l’indice non va mai a 4...

appunto, è proprio questo che sbagliavo