Matematicamente.it

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ì?

Codice:

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]);
             }
}



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...

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

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 ha scritto:... c'è qualcosa che non va tra le condizioni del primo for ...

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

Super Squirrel ha scritto: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...

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

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!

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

Codice:

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;
            
         }
}



@Super Squirrel
Benvenuto nel club!

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:

Codice:

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]);
        }
    }
}

@Super Squirrel
Benvenuto nel club!

Uhm credo di aver intuito cosa intendi, in ogni caso onorato di farne parte!

Non so se tu mi stia prendendo sul serio o no, in ogni caso problema risolto,fino alla prossima.