[C++]Modifica Selection Sort

[bigsqualo]

Dovrei fare questa operazione.

Modifica il sort per selezione in modo da interrompersi non appena si scopre che l'insieme dei dati è ordinato.

#include <stdio.h>
#include <stdlib.h>

void selection_sort (int a[], int n);
int main(void)
{
int array[100],i,n;
printf ("Inserisci la lunghezza del vettore: ");
scanf ("%d",&n);
for(i=0; i<n; i++)
{
printf ("Inserire %d numero: ",i+1);
scanf ("%d",&array[i]);
}

selection_sort(array,n);
system ("pause");
return 0;
}

void selection_sort(int a[], int n)
{

int i, j, min;
double t;

for (i=0; i <= n; i++) {
min = i;
for (j= i + 1; j < n; j++)
if (a[j] < a[min])
min = j;

t = a[min];
a[min] = a[i];
a[i] = t;
}
for (i=0; i<n; i++)
{
printf ("Il %d numero e' = %d\n",i+1,a[i]);
}
}

possibili soluzioni?

[YuYevon]

Indentazione. E soprattutto, punto 6 del regolamento.

Comunque, non ti è venuta proprio nessuna idea?

E poi quel codice di C++ non ha praticamente nulla.

[bigsqualo]

quel codice e il selection sort.. ora non posso piu modificare il mio messaggio :'( mi serve na mano :'(

[YuYevon]

Vabbè lascia perdere, all'indentazione ci penseranno i moderatori magari. Te lo dicevo per il futuro.

Quello che intendevo dire sul problema è: ci hai pensato un po' su? Credi di aver trovato almeno una mezza idea a livello concettuale (lasciando stare il codice)? O non ci hai ragionato proprio?

[bigsqualo]

magari si può risolvere con l'uso di una variabile booleana.. che nel primo controllo del ciclo se è ordinato ritorna true e il ciclio si arresta.. ma a livello di codice nn saprei come fare..

[YuYevon]

E' esattamente quello a cui avevo pensato anche io. Probabilmente si potrebbe trovare anche qualcosa di più elegante, ma la soluzione che proponevi tu è valida comunque. Devi semplicemente fare un "controllo in avanti" nel ciclo for interno: se in un qualsiasi momento hai che un a[j-1] risulti essere maggiore di a[j], l'array non è ordinato, quindi non puoi arrestare il ciclo (e quella variabile booleana di cui dicevi magari la setti a "falso", ossia 0). Se invece per ogni j risulta a[j-1] < a[j], allora l'array è ordinato e non hai motivo di procedere oltre. In questo caso, setti a "vero" (1) la variabile booleana ed esci. L'istruzione break può esserti utile per interrompere un ciclo.

[bigsqualo]

e a livello proprio di codice come risulterebbe? poi ci penso e magari posto le 3 4 righe di mofica..

[YuYevon]

Ti ho spiegato come modificare il codice. Più nello specifico:

for (j= i + 1; j < n; j++) {
   if (a[j] < a[min])
      min = j;
}

per ogni j (quindi all'interno di quel ciclo che ho riportato) devi verificare che l'elemento j-esimo risulti maggiore dell'elemento jmeno1-esimo: SE (if) anche solo per una coppia di elementi la proprietà non è rispettata, l'array non è ordinato, quindi setti a 0 la variabile booleana di cui sopra e nel for principale ci metti un controllo tipo if (variabile_booleana == 1) break.
La variabile booleana la inizializzi a 1 ad ogni iterazione del ciclo for esterno, quindi se viene modificata (cioè posta a 0) da quello interno significa che l'array non è ordinato e che le iterazioni devono continuare, altrimenti (cioè se rimane a 1) l'array è ordinato e quindi il ciclo può terminare.
Il controllo va fatto solo "in avanti", cioè da j in poi perché "all'indietro" l'array è già sicuramente ordinato, per come procede il selection sort per selezione di minimo.

Volendo si potrebbe anche riscrivere un po' il ciclo esterno per eliminare l'istruzione break.

Più dettagliato di così non riesco ad essere. Se proprio non riesci a farlo, posto una possibile soluzione.

[bigsqualo]

Se riesci a postarmi una possibile soluzione mi sarebbe di grande aiuto(se non ti rubo troppo tempo) grazie mille intanto.

[YuYevon]

Non mi rubi tempo, ma sarebbe stato meglio se l'avessi fatta da solo. Comunque questa dovrebbe andare, fai delle prove perché io ne ho fatte solo un paio:

void selection_sort(int a[], int n)
{
	int i, j, k, min, sorted;
	double t;

	for (i = 0; i < n; i++) {
		sorted = 1;

		min = i;
		for (j = i + 1; j < n; j++) {
			if (a[j] < a[min]) {
				min = j;
			}

			if (a[j-1] > a[j]) {
				sorted = 0;
			}
		}

		if (sorted == 1) {
			break;
		}

		t = a[min];
		a[min] = a[i];
		a[i] = t;
	}

	for (i = 0; i < n; i++) {
		printf("Il %d numero e' = %d\n", i + 1, a[i]);
	}
}

Presta attenzione al < invece di <= nel for esterno, va modificato anche nella precedente versione.

Come dicevo questa è solo una possibile soluzione, ci potrebbe essere qualcosa di meglio e in ogni caso anche questa potrebbe essere riscritta con un do-while in maniera tale da testare la condizione su sorted senza ricorrere a break.