Mi suggerite l'algoritmo? [Java]

[djadry]

ok mi rivolgo a demos per il codice che mi ha lui stesso suggerito:

in questa riga di codice,

for (j = min = i; j < array.length; j++)	//ciclo interno, ripete n - i volte

posso semplicemente scrivere j = 0, giusto?


qui

if (array[j] < array[min])

si presuppone che entrambi gli array siano stati riempiti un precedente ciclo for?


nelle istruzioni successive non ho capito che senso ha assegnare a tmp = array[i], in quanto comunque la variabile è già a 0 e sarà modificata 2 istruzioni dopo. per il resto le istruzioni mi tornano (ci ho messo qualche minuto a capire), proverò a compilare più tardi

[demos88]

Originariamente inviato da djadry

ok mi rivolgo a demos per il codice che mi ha lui stesso suggerito:

in questa riga di codice,

for (j = min = i; j < array.length; j++)	//ciclo interno, ripete n - i volte

posso semplicemente scrivere j = 0, giusto?

No, j deve essere inizializzato all'indice del primo numero della sottosequenza non ordinata, ovvero i (il cui incremento è gestito dal for esterno). Perchè tu, cerchi il minore tra i numeri che non sono ancora ordinati, quelli già ordinati li lasci stare (e si trovano tra l'indice 0 e i-1)

Originariamente inviato da djadry

qui

if (array[j] < array[min])

si presuppone che entrambi gli array siano stati riempiti un precedente ciclo for?

l'array è uno solo e si chiama appunto "array", solo che accedi a indici diversi.
L'array, prima dell'algoritmo viene riempito e passato come parametro della funzione selectionSort(int[] array)

Originariamente inviato da djadry

nelle istruzioni successive non ho capito che senso ha assegnare a tmp = array[i], in quanto comunque la variabile è già a 0 e sarà modificata 2 istruzioni dopo. per il resto le istruzioni mi tornano (ci ho messo qualche minuto a capire), proverò a compilare più tardi

Come detto sopra, stiamo lavorando su un unico array, quindi se sovrascrivo un valore dentro all'array, perdo quello precedente. Tmp mi serve per ricordarmi che valore c'era in array[i], e lo scambio con array[min], quindi:
prima faccio una copia di array[i] in tmp
poi copio array[min] in array[i]. A questo punto all'indice min e i ho lo stesso valore, però io devo rimettere dentro il valore che ho sostuito, e lo rimetto in array[min], quindi
array[min] = tmp
Tutto questo perchè il selection sort è un algoritmo in-place, lavora quindi sulla struttura dati stessa, spiegazione su wikipedia: http://it.wikipedia.org/wiki/Algoritmo_in_loco

[djadry]

ah ok, capito. ho letto attentamente la voce su wiki.

questo funziona giusto, non avevo ben realizzato stessi usando un algoritmo completamente diverso!


...unica cosa è che mi sono fossilizzato sul far funzionare il Bubble Sort; ora ho trovato questo esempio di codice: http://it.wikibooks.org/wiki/Impleme...mi/Bubble_sort


ci riprovo un'altra volta ora, grazie per la pazienza :S

[demos88]

Originariamente inviato da djadry

...unica cosa è che mi sono fossilizzato sul far funzionare il Bubble Sort; ora ho trovato questo esempio di codice: http://it.wikibooks.org/wiki/Impleme...mi/Bubble_sort


ci riprovo un'altra volta ora, grazie per la pazienza :S

Cosa non ti è chiaro del bubblesort?
Il nome stesso (bubble) suggerisce il metodo in cui lavora, l'algoritmo lavora sempre secondo il concetto di substringa ordinata e non ordinata, solo che quella ordinata non è all'inizio ma alla fine.
Il nome "bubble" dipende dal fatto che l'algoritmo parte dall'inizio della sequenza di valori e fa "salire" come una bolla i valori maggiori (come nell'esempio, ma possono anche essere i minori per avere ordinamento decrescente) fino alla cima.
Nell'algoritmo che hai visto in quel sito, che riporto:

 public void bubbleSort(int[] x) 
    {
    int temp = 0;
    int j = x.length-1;
    while(j>0) 
      {
      for(int i=0; i<j; i++) 
        {
        if(x[i]>x[i+1])   //scambiare il '>' con '<' per ottenere un ordinamento decrescente
          {
          temp=x[i]; 
          x[i]=x[i+1];
          x[i+1]=temp;
          }
        }
      j--; 
      }
    }

j è l'indice che deve essere riempito con il valore maggiore tra i non ordinati, mentre i è l'indice che cerca il valore maggiore.
Concettualmente è simile al selection sort, solo che ad ogni comparazione, se la disuguaglianza è vera, sposta un elemento in modo da "avvicinarlo" alla sequenza ordinata. Esempio:
5 8 1 6 4 3
1° ciclo:
j = 5, i = 0; 5 >= 8 ? no, quindi non fare nulla
5 8 1 6 4 3
j = 5, i = 1; 8 >= 1 ? si, quindi inverti 8 con 1
5 1 8 6 4 3
j = 5, i = 2; 8 >= 6 ? si, quindi inverti 8 con 6
5 1 6 8 4 3
j = 5, i = 3; 8 >= 4 ? si, quindi inverti 8 con 4
5 1 6 4 8 3
j = 5, i = 4; 8 >= 3 ? si, quindi inverti 8 con 3
5 1 6 4 3 8
j = 5, i = 5; i = j -> ciclo finito, gli elementi da j in poi sono ordinati (j è ancora uguale a 5)
5 1 6 4 3 8
j--
2° ciclo:
5 1 6 4 3 8
j = 4, i = 0; 5 >= 1? si, quindi inverti 5 con 1
1 5 6 4 3 8
j = 4, i = 1; 5 >= 6 ? no, quindi non fare nulla
1 5 6 4 3 8
j= 4, i = 2; 6 >= 4 ? si, quindi inverti 6 con 4
1 5 4 6 3 8
j = 4, i = 3; 6 >= 3 ? si, quindi inverti 6 con 3
1 5 4 3 6 8
j = 4, i = 4; i = j -> ciclo finito, gli elementi da j in poi sono ordinati (j = 4)
1 5 4 3 6 8
3° ciclo:
penso ti sia chiaro...