C/C++ - PROBLEMA CODICE INSERTION SORT

Se non hai mai sentito parlare di rosettacode.org, questa potrebbe essere una buona occasione per farci una visitina:

rosettacode.org/wiki/Sorting_algorithms/…

Anche questo può essere un bello spunto:

tutorialspoint.com/…

Non so se li hai postati per me, questi link, ti ringrazio.

Ho già postato un algoritmo in C, insertion sort ma Iprogrammer voleva correggere il suo e non voleva un codice nuovo.

Nel caso specifico, bubblesort, insertion sort, selection sort, li conosco e non ho nessun problema a scriverli in VB.NET o C#, anche se oggi non servono più con le potenti funzioni implementate in VB.NET e C#, compresi i sort che si possono fare con le Tuple.

Per me è stato un esercizio, il C somiglia con inganno al C#, e l'esempio è strutturato in blocchi divisi, così da pemettermi di saggiare proprio le differenze tra C e C#.
Ammetto che senza le info di nessuno e Ultimo non avrei potuto risolvere gli errori, visto che per correggerli tutti bisognava capire perfettamente la logica di funzionamento.

Prima di postare il codice corretto aspetto di sentire Iprogrammer, per sapere a che punto sta.

Carlo: "Non so se li hai postati per me, questi link, ti ringrazio."

In effetti, no. Li ho segnalati per chi ha avviato questo filone di discussione. E' ben vero che voleva correggere il codice che ci ha riportato, ma vedere come altri hanno risolto il problema è senz'altro un buon "cacciavite", un attrezzo utile per riuscire ad arrivare alle proprie soluzioni personali.

Ho trovato più volte spunti molto interessanti in rosettacode.org, anche se non ho mai fatto un vero e proprio "copia-e-incolla" delle soluzioni fornite (il copia-e-incolla è il più delle volte inadeguato per risolvere questioni specifiche). Vedere come gli altri affrontano e risolvono i problemi è una fonte preziosa di apprendimento. Amo i luoghi web nei quali volontari benintenzionati espongono il frutto dei propri sforzi, anche quando magari non danno luogo a soluzioni "da professionisti".

Senza polemica, questo e' un forum tecnico (come altri o almeno prima lo era) e chi chiede aiuto (esclusa la pappa pronta diseducativa) vorrebbe una indicazione o una spiegazione su cosa non va nel codice.

Fare una lunga discussione OT sulle basi del linguaggio (Carlo se hai dubbi apri un thread e fai domande ... se fossi stato il creatore del thread non avrei gradito i tuoi interventi OT) o suggerire spazi web (?) che soddisfano la sete di conoscenza di codici scritti da altri senza spiegarsi il perche' siano scritti in quel modo, e' altrettanto fuorviante ed inutile per l'op. E il fatto di non essere professionisti non significa che non si debbano utilizzare e studiare soluzioni da professionisti. Le soluzioni fai da te possono funzionare nel breve e limitato periodo o contesto ma si deve imparare bene come si fanno le cose. Molti studenti saranno i professionisti di domani non i pensionati hobbysti e bisogna dare loro una mano al massimo delle possibilita'.

Se questo forum si basera' su risposte da hobbysti e filosofia del fai da te avra' vita breve.

Fossi stato in lui sarei andato su altro forum.

La stessa domanda l'ha postata su altri 3 forum, e forse anche di più, ma non si è interessato alle risposte.

Per tutti i lettori del futuro, oltre alle spiegazioni già postate alle 13:02 di Mercoledì, 29/04/2020
il codice funzionante commentato:

/*
 * codice per insertion sort
 * descrizione: https://it.wikipedia.org/wiki/Insertion_sort
 */

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

#define MAX_INPUT 10

void estrai_dati(int ac, char **av, int *vett, int *lung)
{	// estrae dall'argomento
	*lung = ac - 1;
	
	for (int i = 0; i < *lung; ++i)
		vett[i] = atoi(av[i + 1]);
}

void fai_spazio(int posizione, int *vett, int lung)
{	// scorre di una posizione
	for (int j = lung; j > posizione; --j)
		vett[j] = vett[j - 1];
}

void inserisci(int nuovo_dato, int num_dati_ord, int *vett)
{      // riempimento dati_ordinati passato come puntatore
	if (num_dati_ord == 0) { // il vettore è vuoto, facile
		vett[0] = nuovo_dato;
		return;
	}
	// se nuovodato è più piccolo va in testa
	for (int i = 0; i < num_dati_ord; ++i) {
		if (nuovo_dato < vett[i]) {
			// sposta da vett[i] in poi di un posto sulla destra
			// prima di inserire il nuovo_dato
			fai_spazio(i, vett, num_dati_ord);
			vett[i] = nuovo_dato;
			return;
		}
		else {// altrimenti va nella stessa posizione che occupava in dati_non_ordinati
			vett[num_dati_ord] = nuovo_dato;
		}
	}
}

void ordina_dati(const int *dati_non_ordinati, int *dati_ordinati, int num_dati)
{	// ciclo principale
	for (int i = 0; i < num_dati; ++i)
		inserisci(dati_non_ordinati[i], i, dati_ordinati);
}

void stampa_vettore(const int *vett, int lung)
{	// visualizza
	for (int i = 0; i < lung; ++i)
		printf("%d ", vett[i]);
	printf("\n");
}

int main(int argc, char **argv)
{	// i valori vanno inseriti da riga comando dopo compilazione
	
	if (argc > MAX_INPUT + 1) {
		printf("Numero massimo di input %d\n", MAX_INPUT);
		return -1;
	}
	int dati_input[MAX_INPUT] = { 0 }; // matrice di 10 elementi
	int dati_ordinati[MAX_INPUT] = { 0 }; // matrice di 10 elementi
	int num_dati = 0; // passato come puntatore verrà calcolato in estrai_dati

	estrai_dati(argc, argv, dati_input, &num_dati);
	ordina_dati(dati_input, dati_ordinati, num_dati);
	stampa_vettore(dati_ordinati, num_dati);
	return 0;
}

Carlo, i dati che già esistono si utilizzano, non si ricavano nuovamente. E vale per tutti i linguaggu

void estrai_dati(char **av, int *vett, int lung)
{       
	for (int i = 0; i < lung; ++i)
                vett[i] = atoi(av[i + 1]);
}

int main(int argc, char **argv)
{       
        int dati_input[MAX_INPUT] = { 0 }; // vettore di 10 elementi
        int dati_ordinati[MAX_INPUT] = { 0 }; // vettore di 10 elementi
        int num_dati = argc-1;

        if (num_dati > MAX_INPUT) {
                printf("Numero massimo di input %d\n", MAX_INPUT);
                return -1;
        }
 
        estrai_dati(argv, dati_input, num_dati);
        ordina_dati(dati_input, dati_ordinati, num_dati);
        stampa_vettore(dati_ordinati, num_dati);
        return 0;
}

Una considerazione ... l'algoritmo di ordinamento in genere si utilizza sullo STESSO vettore disordinato, non si utilizza un altro vettore. Per la didattica va bene ma in realtà se hai un milione di dati da ordinare non puoi usare un altro vettore parallelo di un altro milione di elementi ... (anche se in quel caso si userebbero altri algoritmi, ma è un'altra storia).

Quindi questo codice andrebbe riscritto usando solamente il primo vettore derivante da argv

Concordo, mi sono concentrato nel lasciare il codice uguale come richiesto, che è palesemente didattico e sparpagliato.
Per il mio archivio l'ho riscritto, uso lo stesso vettore con un algoritmo che proviene da un mio vecchio C#, che poi ho visto simile in molti siti, e dimensiono la matrice in accordo con il numero di interi immessi (se ho fatto qualcosa non C compatibile, graditi suggerimenti).
Le tue info sono essenziali, ma sempre circostanziate, e questa volta piacevolmente esaurienti.

/*
 * codice per insertion sort
 * descrizione: https://it.wikipedia.org/wiki/Insertion_sort
 */

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

void stampa_vettore(const int *vett, int lung)
{	// visualizza
	for (int i = 0; i < lung; ++i)
		printf("%d ", vett[i]);
	printf("\n");
}

void insertion_sort(int *vett, int lung)
{	// ordina modificando la matrice di ingresso
	int provv, c1, c2 = 0;

	for (c1 = 1; c1 < lung; c1++)
	{
		provv = vett[c1];
		c2 = c1 - 1;
		while ((vett[c2] > provv) && (c2 >= 0))
		{
			// scorrimento
			vett[c2 + 1] = vett[c2];
			c2--;
		}
		// progresso
		vett[c2 + 1] = provv;
		printf("Ciclo %d = ", c1);
		stampa_vettore(vett, lung);
	}
}

int main(int argc, char **argv)
{	// i valori vanno inseriti da riga comando dopo compilazione release
	// es \Release\InsertionSort4 12 23 62 7 4 5 2

	int num_dati = argc - 1; // numero di interi passati da riga comando
	int* dati_inout = (int*)malloc(num_dati *  sizeof(int)); // dimensiono il vettore in out
	
	for (int i = 0; i < num_dati; ++i)
		dati_inout[i] = atoi(argv[i + 1]); // copio i dati dell'argomento nella matrice in out
	printf("\n- Sono stati inseriti N. %d interi: \n\n", num_dati);
	
	// ordinamento
	insertion_sort(dati_inout, num_dati);
	

	printf("\n- Risultato = ");
	stampa_vettore(dati_inout, num_dati);

	return 0;
}

Ok ... solo qualche precisazione.

E' buona norma restituire sempre un valore di stato in uscita ed è meglio che il punto di uscita sia unico (niente return in mezzo al codice). I valori in uscita devono essere chiaramente stabiliti e documentati.

Inoltre, considera che la mancanza di argomenti può essere trattato come un caso particolare.

Infine, controlla SEMPRE che l'allocazione di memoria vada a buon fine e che ad una allocazione corrisponda SEMPRE una free che libera la memoria allocata quando non serve più; anche se sembrano operazioni poco utili, sono buone abitudini che fanno risparmiare mal di testa in codici molto lunghi e complessi e differenziano il codice scritto da PROFESSIONISTI (chi vuole intendere mi intenda...).

#define ALL_OK		0
#define OUT_OF_MEM -1
#define NO_ARGS    -2

int main(int argc, char **argv)
{       // i valori vanno inseriti da riga comando dopo compilazione release
		// es \Release\InsertionSort4 12 23 62 7 4 5 2

	int res = ALL_OK;
	int num_dati = argc - 1; // numero di interi passati da riga comando

	if (num_dati)
	{
		int* dati_inout = (int*)malloc(num_dati * sizeof(int)); // dimensiono il vettore in out

		if (!dati_inout)
		{
			printf("Out of memory\n");
			res = OUT_OF_MEM;
		}
		else
		{
			for (int i = 0; i < num_dati; ++i)
				dati_inout[i] = atoi(argv[i + 1]); // copio i dati dell'argomento nel VETTORE in out

			printf("\n- Sono stati inseriti N. %d interi: \n\n", num_dati);

			// ordinamento
			insertion_sort(dati_inout, num_dati);

			printf("\n- Risultato = ");
			stampa_vettore(dati_inout, num_dati);

			free(dati_inout);
		}
	}
	else
	{
		printf("No args\n");
		res = NO_ARGS;
	}

	return res;
}

Ciao e buono studio.

P.S. La questione dell'operatore sizeof è semplice ... questo riporta la grandezza in byte del TIPO di dato che si pasa.
Se scrivi

char a[10];
printf("%d\n", sizeof(a));

vedrai che otterrai 10 perché il tipo di dato passato è char[10] e un carattere è in genere equivalente ad un byte.

Ma se passi il vettore ad una funzione, ad esempio (e questo vale sempre perché viene sempre passato per puntatore)

void test(char *v)
{
    printf("%d\n", sizeof(v));
}

otterrai SEMPRE 4 perché adesso il tipo di dato passato è un char * ovvero un puntatore che ha sempre grandezza 4 (nei sistemi a 32 bit) anche se il vettore è di 1000 elementi. Nei sistemi (e programmi) a 64 bit otterrai sempre 8 dato che il puntatore è a 8 byte. Quindi, in questo caso non potrai utilizzare questo operatore per determinare la grandezza del vettore. In realtà in C NON E' POSSIBILE sapere quanto sia grande il vettore passato per puntatore (ovvero non si può sapere quanti byte sono allocati e validi per un determinato puntatore e in questo forum c'è stata una lunga e controversa discussione sulla questione).

Questi sono errori comuni di chi inizia a programmare o chi rimane nello stato di "dilettante" come il fatto di non controllare la validità di una allocazione, di non liberare la memoria allocata o altro ...