Algoritmo Ordinamento

di il
5 risposte

Algoritmo Ordinamento

Salve a tutti, è da tanto che non scrivevo qui

Oggi mentre ero al lavoro avevo bisogno di un algoritmo di ordinamento e non avendo un codice già bello e pronto ho preso come riferimento il BubbleSort e ho scrito questo:
void ordinamento(int array[],int n)
{
 	int i,y;

 	for(i=1;i<n;i++) //scorro tutto l’array a partire dal secondo elemento
 	{
 		y=i; //assegno ad y il valore dell’indice
 		while(y>0 && array[y]<array[y-1]) //entro SOLO se la condizione è rispettata
 		{
 			scambia(&array[y],&array[y-1]);
 			y--;
 		}
 	}
}
Tornato a casa ho confrontato l'algoritmo che ci ha spiegato il nostro prof con questo.. Quello del prof, esegue tanti for quanti sono gli elementi ed ad ogni passo seleziona il massimo nell'ultima posizione dell'array per poi escuderlo nel passo successivo..

A me francamente questo sembra molto più efficiente..

La domanda e questa: io vorrei presentare questa versione al prof ma questo algoritmo esiste ed ha un nome oppure no? Ho paura di fare una bella figuraccia andando li con un algoritmo magari famosissimo xD

L'ho mostrato a diversi miei colleghi studenti e nessuno lo conosceva..

Può essere definito un BubbleSort più efficiente??

La complessità è nel caso peggiore O(n^2) come il bubblesort, ma per caso peggiore si ha solo con l'array ordinato al contrario.. Se non è ordinato al contrario ha complessità inferiore al Bubblesort..

5 Risposte

  • Re: Algoritmo Ordinamento

    Preso da wikipedia
    Le prestazioni del Bubble sort possono essere leggermente incrementate tenendo conto del fatto che, dopo ogni comparazione (ed eventuali scambi), l'elemento più grande incontrato nel passaggio corrente si troverà nell'ultima posizione esaminata. Quindi, dopo il primo passaggio, il più grande elemento della lista sarà posizionato nell'ultima posizione: alla luce di questo, data una lista di lunghezza n, l' n-simo elemento sarà spostato nella sua posizione finale dopo il primo passaggio, l' (n-1)-simo elemento sarà posizionato nel secondo passaggio, e così via. Perciò ogni passaggio può essere di 1 passo più corto rispetto al precedente, evitando di scorrere tutta la lista ogni volta fino alla fine, dato che gli ultimi elementi sono già nella loro posizione definitiva e non devono essere più spostati. Possiamo rappresentare quanto detto con il seguente pseudocodice:
    
    procedure BubbleSort( A : lista di elementi da ordinare)
      alto ? lenght(A) - 1
      while (alto > 0) do
        for i ? 0 to alto do
          if (A[i] > A[i + 1]) then       //scambiare il '>' con '<' per ottenere 
            swap ( A[i], A[i+1] )                  // un ordinamento decrescente
        alto ? alto - 1
    
    Non ti sembra come la tua versione?
  • Re: Algoritmo Ordinamento

    Io se devo ordinare non sto a cercare algoritmi perche so che C++ ne ha già uno molto performante
    
    #include <algorithm>
    std::sort(array,array + n);
    
    Complessità n*log(n) caso peggiore
  • Re: Algoritmo Ordinamento

    Non sto dicendo che questo sia il miglior algoritmo di ordinamento.. Mi sembra solo un BubbleSort più efficiente di quello classico
    procedure BubbleSort( A : lista di elementi da ordinare)
      alto ? lenght(A) - 1
      while (alto > 0) do
        for i ? 0 to alto do
          if (A[i] > A[i + 1]) then       //scambiare il '>' con '<' per ottenere 
            swap ( A[i], A[i+1] )                  // un ordinamento decrescente
        alto ? alto - 1
    Questo è il normale BubbleSort.. In questo io effettuo tutto il ciclo for ad ogni passo del while.. Se metti caso io ho un array già ordinato:

    1 2 3 4 5 6

    contronto 1-2 2-3 3-4 4-5 5-6 poi escludo il 6
    confronto 1-2 2-3 3-4 4-5 poi escludo il 5
    ............. e così via per ogni elemento dell'array..

    Quindi con il BubbleSort io se ho un array già ordinato oppure un array ordinato al contrario, faccio sempre lo stesso numero di confronti e ripeto confronti già effettuati.
    void ordinamento(int array[],int n)
    {
       int i,y;
    
       for(i=1;i<n;i++) //scorro tutto l’array a partire dal secondo elemento
       {
          y=i; //assegno ad y il valore dell’indice
          while(y>0 && array[y]<array[y-1]) //entro SOLO se la condizione è rispettata
          {
             scambia(&array[y],&array[y-1]);
             y--;
          }
       }
    }
    Nel BubbleSort che ho postato io invece se ho lo stesso array:

    1 2 3 4 5 6

    confronto 2-1
    confronto 3-2, 3>2 quindi non faccio altri confronti perchè so già che saranno inutili
    confronto 4-3, idem
    ........ e così vià per ogni elemento dell'array..

    Con lo stesso array io ho solo n-1 confronti..

    Una cosa del genere non risulta essere migliore?? Ti ripeto non sto dicendo che è l'algoritmo di ordinamento migliore, mi sembra solo un Bubble più efficiente di quello classico..
  • Re: Algoritmo Ordinamento

    A me sembra lo stesso algoritmo comunque. Se spezzetti il while e scambi il while col for di sopra torni all'algoritmo originale. Non sto dicendo che non é migliore o peggiore bisogna contare le iterazioni per tipo di vettore ma secondo me non risparmi neanche una iterazione. Magari mi sbaglio.
  • Re: Algoritmo Ordinamento

    Scusate se m'intrometto nel discorso,
    l'algoritmo proposto è una variazione al bubble sort e in fatto di modifiche ce ne sono una valanga. Tra le due più conosciute, citate anche da wiki esiste la tua.
    ...
    Una seconda linea di ottimizzazione (che può essere combinata con la prima) è basata sull'osservazione che (sempre assumendo una scansione dell'array, per esempio, in avanti, e ordinamento crescente) se una data iterazione non sposta nessun elemento di posizione maggiore di un dato valore i, allora si può facilmente dimostrare che nessuna iterazione successiva eseguirà alcuno scambio in posizioni successive a tale valore i. L'algoritmo può dunque essere ottimizzato memorizzando l'indice a cui avviene l'ultimo scambio durante una iterazione, e limitando le iterazioni successive alla scansione dell'array solo fino a tale posizione. Anche questa tecnica evidentemente introduce un piccolo overhead (gestione della variabile aggiuntiva che indica la posizione di ultima modifica).
    ...
    http://it.wikipedia.org/wiki/Bubble_sort#Varianti_e_ottimizzazioni

    @OP, è sicuramente apprezzabile la miglioria in un contesto didattico, perché l'algoritmo in questione viene usato quasi sempre in quel contesto e come ti ha suggerito skynet 'operativamente' non viene quasi mai usato (esiste già il quicksort molto più efficiente definito nello stdlib)
    Nel caso di ordinamento di liste dinamiche potremmo ricorrere ad un insertion sort ma nel caso di pochi elementi anche il bubble potrebbe essere idoneo.

    Facendo delle prove con bubble non perfezionato, usando un campione di 10.000 strutture casuali, io ottengo questi tempi:
    
    There are 10000 item(s) in list
    Sorting by 0=Name or 1=ID ?0
    Sorting...
    done in 2,153937 seconds
    ...
    There are 10000 item(s) in list
    Sorting by 0=Name or 1=ID ?1
    Sorting...
    done in 1,790466 seconds
    
    Ma se ho una lista ridotta di 500 elementi, ottengo:
    
    There are 500 item(s) in list
    Sorting by 0=Name or 1=ID ?0
    Sorting...
    done in 0,007974 seconds
    ...
    There are 500 item(s) in list
    Sorting by 0=Name or 1=ID ?1
    Sorting...
    done in 0,006087 seconds
    
    Ecco che 6/7 millesimi di secondo risulterebbe accettabile ed impercettibile
Devi accedere o registrarti per scrivere nel forum
5 risposte