Comparazione dell'algoritmo di ordinamento di inserzione

2

Recentemente mi sono imbattuto in tecniche di ordinamento e, in particolare, in 'insertion sorting.

Sebbene la logica e il metodo siano abbastanza comprensibili, la funzione effettiva sembrava un po 'complessa (fornita di seguito).

void InSort(int AR[], int size)
{
    int tmp,j; 
    AR[0]=INT_MIN;  //defined in limits.h , basically the smallest possible value 

     for(int i=1;i<size;i++)
     {  
       tmp=AR[i];
       j=i-1;

        while(tmp<AR[j])
         {
           AR[j+1]=AR[j];
           j--;
          }

       AR[j+1]=tmp;
     }

}

Si noti che gli elementi per la funzione sopra sono inseriti da AR [1].

Ho quindi provato il mio tentativo di eseguire l'ordinamento in un modo più semplice, come illustrato di seguito. (Ascendente)

void iSort(int Arr[] , int size)
{
  Int temp;
  for(int i=1 ; i<size ; i++)
  {

    for(int j=0 ; j<i ; j++)
    {
       if(Arr[i]<Arr[j])
       {
        temp=Arr[i];
        Arr[i]=Arr[j];
        Arr[j]=temp;
        }
    }
  }
}

Con mio sgomento, qualcuno mi ha detto che sebbene questo metodo eseguirà l'ordinamento, non si qualifica come "Inserisci ordinamento", ma credo ancora che segua lo stesso principio.

È così? Allora, cosa c'è di particolarmente sbagliato nel mio tentativo? Ancora più importante, la seconda funzione si qualifica come ordinamento per inserimento?

-

Vorrei menzionare che sono relativamente nuovo alla programmazione in generale, quindi perdona il mio tentativo apparentemente primitivo, tutto quello che voglio fare è imparare! Inoltre, questa non è la versione recente del C ++, è in realtà vecchiaia, quindi scuse in anticipo!

Sarei felice per ogni input ricevuto, grazie in anticipo!

    
posta Vignesh Balchand 19.01.2015 - 16:22
fonte

1 risposta

1

Il secondo algoritmo si chiama Bubble Sort, non Insertion Sort.

L'idea è che in Insertion Sort, prendi un elemento nell'array, cerchi dove dovrebbe trovarsi in l'intero array , quindi "inserisci" in quel punto, spostando tutti gli elementi una volta. Fai questo inserimento una sola volta per elemento.

Con Bubble Sort, guardi sempre due elementi adiacenti e li scambia se necessario. Il nome deriva dall'idea che gli elementi più alti si "gonfiano" lentamente fino alla cima dell'array, poiché si muovono solo di un passo alla volta.

Then, what is particularly wrong with my attempt?

Niente. Ti è appena capitato di scrivere un algoritmo diverso per sbaglio. Entrambi questi algoritmi hanno una complessità temporale O (n ^ 2) nel caso peggiore e nel caso medio (poiché eseguono più o meno gli stessi confronti e assegnazioni in ordini diversi), quindi non è come se avessi peggiorato la situazione.

Sono d'accordo sul fatto che Bubble Sort è solitamente un algoritmo più semplice da leggere e scrivere in codice, quindi se le prestazioni non sono un problema (e la tua lingua non ha una funzione sort () per qualche motivo) allora sentiti libero di usare quello. Tuttavia, Insertion Sort ha spesso prestazioni migliori sugli array in cui la maggior parte degli elementi è già nel posto giusto.

Naturalmente, heapsort e mergesort sono O (n log n) worst-case, e quicksort è O (n log n) nel caso medio, quindi se ti preoccupi delle prestazioni di ordinamento dovresti probabilmente guardare uno di quelli .

    
risposta data 19.01.2015 - 23:39
fonte

Leggi altre domande sui tag