Insertion sort

Messaggioda ZfreS » 18/07/2018, 09: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ì?
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]);
             }
}

ZfreS
Cannot live without
Cannot live without
 
Messaggio: 698 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Insertion sort

Messaggioda Super Squirrel » 18/07/2018, 11: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...
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 266 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Insertion sort

Messaggioda ZfreS » 18/07/2018, 12:28

Con quell'array non viene ordinato, anche cambiando l'ordine delle cifre.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 700 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Insertion sort

Messaggioda Super Squirrel » 18/07/2018, 14: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 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...
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 269 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Insertion sort

Messaggioda ZfreS » 18/07/2018, 14:19

Sono riuscito a risolvere, implementandolo diversamente, e funziona anche con l'array che mi hai proposto tu. Grazie comunque per l'aiuto.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 702 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Insertion sort

Messaggioda Super Squirrel » 18/07/2018, 15: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! :roll:
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 270 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Insertion sort

Messaggioda ZfreS » 18/07/2018, 15:32

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

ZfreS
Cannot live without
Cannot live without
 
Messaggio: 704 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Insertion sort

Messaggioda axpgn » 18/07/2018, 15:52

@Super Squirrel
Benvenuto nel club! :D
axpgn
Cannot live without
Cannot live without
 
Messaggio: 11559 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Insertion sort

Messaggioda Super Squirrel » 18/07/2018, 19:39

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

Finalmente è arrivata l'illuminazione! :D
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! :D

Uhm credo di aver intuito cosa intendi, in ogni caso onorato di farne parte! :-D
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 272 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Insertion sort

Messaggioda ZfreS » 18/07/2018, 19:52

Non so se tu mi stia prendendo sul serio o no, in ogni caso problema risolto,fino alla prossima.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 706 di 4589
Iscritto il: 22/10/2016, 17:52

Prossimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite