Insertion sort

Fai una domanda Tutte le categorie

18 lug 2018, 10:15

Ho implementato una mia versione dell'insertion sort in c++ funzionante, ma confrontandola con altre trovate in rete, ho paura che la mia contenga qualche bug. Potreste aiuatarmi a capire se è possibile ciò, oppure se va bene così?

void insertionSort(int arr[], int l)
{
	int i = 0;
	for(i; i<l && arr[0]<l; i++)
		
			for(int j = 0; j<l-1;j++)
				if (arr[j] > arr[j + 1])
				{
					swap(arr[j], arr[j + 1]);
			    }
}

Risposte

Super Squirrel

18 lug 2018, 10:39

Innanzitutto c'è qualcosa che non va tra le condizioni del primo for, prova ad applicare l'algoritmo sul seguente array:

v = 7, 3, 1

cosa succede?

Premesso che i miei studi sull'argomento si limitano ad una lettura su wikipedia appena fatta, quello mi sembra più un bubble sort mal congegnato che un insertion sort...

oleg.fresi

18 lug 2018, 11:28

Con quell'array non viene ordinato, anche cambiando l'ordine delle cifre.

Super Squirrel

18 lug 2018, 13:12

Con quell'array non viene ordinato, anche cambiando l'ordine delle cifre.

Quindi? Tutto qui? Nessuna ipotesi circa questo malfunzionamento?
Eppure considerando quanto detto in precedenza

"Super Squirrel":
... c'è qualcosa che non va tra le condizioni del primo for ...

mi sembra che il campo sia stato ristretto già abbastanza...

"Super Squirrel":
Premesso che i miei studi sull'argomento si limitano ad una lettura su wikipedia appena fatta, quello mi sembra più un bubble sort mal congegnato che un insertion sort...

Nessun commento al riguardo?

Sarò sincero, al di là del metodo di studio quanto meno discutibile, non vedo molta buona volontà da parte tua...

oleg.fresi

18 lug 2018, 13:19

Sono riuscito a risolvere, implementandolo diversamente, e funziona anche con l'array che mi hai proposto tu. Grazie comunque per l'aiuto.

Super Squirrel

18 lug 2018, 14:08

Sono riuscito a risolvere, implementandolo diversamente, e funziona anche con l'array che mi hai proposto tu.

Implementando cosa? Un insertion sort come era nelle tue intenzioni iniziali o solo un bubble sort funzionante?
Sarei curioso di vederlo questo algoritmo.

Grazie comunque per l'aiuto.

Di niente!

P.S.
Complimenti cmq per la tua capacità di dribblare le domande!

oleg.fresi

18 lug 2018, 14:32

Non volevo dribblare proprio nulla, è che riflettendoci di più ho trovato una soluzione diversa ed efficiente. Te la mostro:

void insertionSort(int arr[], int lunghezza)
{
	for (int i = 0; i < lunghezza - 1; i++)
		for (int j = i + 1; j > 0; j--)
			if (arr[j] < arr[j - 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = tmp;
				
			}
}

axpgn

18 lug 2018, 14:52

@Super Squirrel
Benvenuto nel club!

Super Squirrel

18 lug 2018, 18:39

Non volevo dribblare proprio nulla, è che riflettendoci di più ho trovato una soluzione diversa ed efficiente. Te la mostro: ...

Finalmente è arrivata l'illuminazione!

Scherzi a parte credo che questo possa essere considerato un insertion sort. Magari un'ottimizzazione potrebbe essere quella di aggiungere un else{break;} dopo l'if, oppure semplicemente:

void insertion_sort(int *v, const unsigned int dim)
{
    for(unsigned int i = 1; i < dim; ++i)
    {
        for(unsigned int j = i; j > 0 && v[j] < v[j - 1]; --j)
        {
            swap(v[j], v[j - 1]);
        }
    }
}