Algoritmi - Combo_11 Sort

   // Algoritmo di ordinamento numerico di un Vettore di numeri.
  // Scritto in linguaggio c/c++ con MS Visual C++ express 2008.

  int swaps = 0;    // swaps = controllo degli scambi.
  int gap = max2;   //Inizializza la dimensione del passo (gap = passo)
                    //(max2 è la quantità di elementi del Vettore memoria2).
    
  for ( ran = 0; ran < (MAX-1); ran++ )   // MAX = totale elementi del Vettore
  {  
		 if ((swaps == 0) && (gap == 1) && (ran > 0))
		{
			break;   //Fine del ciclo, ordinamento completato.
		}
        if (gap > 1)   //Aggiorna il valore del passo per il prossimo passaggio.
	{   	 
                if ((gap == 10) || (gap == 9))
			{   
			gap = 11;   //passo ottimale per i passaggi finali.
	                   }

                gap = (int)(gap / 1.3);    //1.3 = fattore di riduzione.

			if (gap < 1)    //non si sa mai, controllo.
			{
			gap = 1;
			}
	}
        
         if (swaps == 1)
         {
           swaps = 0;     // ripristina il controllore
         }

         for ( i = 0; i < (MAX-1); i++ ) 
		  {   
			if ((i+ gap) > (MAX-1))
			{
				break;
			}
                       if (memoria2[i] < memoria2[i + gap])    //fase di scambio.
			{ 
		          int k = memoria2[i + gap];    //k mi serve per gli scambi.
                              memoria2[i + gap] = memoria2[i];
                              memoria2[i] = k;
			  if (gap == 1 && swaps == 0)      //passo finale
			  {
                              swaps = 1;        //se c'è stato scambio segnala 1
			  }
		         }
              
		  }    // Fine secondo for.

                 if (gap == 2)
		 {
	           gap = 1;    //perchè 2/1.3, arrotondato ad integer da sempre 2 ;)
                    swaps = 1;
		 }

  }	// Fine primo for, fine algoritmo di ordinamento.

Carini i colori del Pyton, comunque il codice è il C/C++.

Il Combo11 sort è stato inventato da un qruppo di matematici per migliorare
le prestazioni dell'algoritmo di ordinamento a scambio tipo il Bubble sort.


Il Combo11 sort è molto veloce, da 85 a 190 volte più veloce del Selected sort.
Se siete interessati inserisco anche la versione in Vbasic.net .
Come giudicate il Combo11 sort ?

Quì di seguito inserisco anche una Funzione che esegue il Combo11_Sort
in Vbasic.Net.

 Public Sub Comb11_Sort(ByVal Vet() As Int32, ByVal ElemV As Int32)

                Dim swaps As Integer = 0    ' Scambi.
                Dim Passo As Integer = ElemV
                Dim Kc As Int32
         
                For r = 0 To (ElemV - 2) Step +1

                    If ((swaps = 0) And (Passo = 1)) Then
                        Exit For
                    End If
                    ' Aggiorna il valore del passo per il prossimo passaggio
                    If (Passo > 1) Then

                        If ((Passo = 10) Or (Passo = 9)) Then
                            ' Passo ottimale per i passaggi finali.
                            Passo = 11
                        End If

                        Passo = CInt(Passo / 1.3)
                    End If

                    If swaps = 1 Then
                        swaps = 0
                    End If

                    For y As Int32 = 0 To (ElemV - 2) Step +1

                        If ((y + Passo) > (ElemV-1)) Then
                            Exit For
                        End If

                        If (Vet(y) > Vet(y + Passo)) Then

                            Kc = Vet(y + Passo)
                            Vet(y + Passo) = Vet(y)
                            Vet(y) = Kc

                            If (Passo = 1 And swaps = 0) Then
                                swaps = 1
                            End If

                        End If
                    Next y

                    If Passo = 2 Then
                        Passo = 1
                        swaps = 1
                    End If

                Next r

        End Sub

        ' In questo modo chiamo la funzione e gli passo il nome del Vettore
        ' e il numero dei suoi elementi.
        Comb11_Sort(NomeVettore, Nelementi)

          ' In questo modo chiamo la funzione e gli passo il nome della Lista
        ' e il numero dei suoi elementi.
        Comb11_Sort(NomeLista, NomeLista.Count)

sarebbe carino se scrivessi anche un briciolo di spiegazione teorica, per capire come funziona e qual è il suo costo computazionale.

L'argomento è interessante, aspetto ulteriori aggiustamenti (ah, rimetti bene il tag code, che è saltato per qualche motivo)...

Il costo computazionale è essere O(n) = n^2?

Questa parte di codice cosa dovrebbe fare? (volevi fare un'assegnazione?)

Hai ragione volevo assegnare e non confrontare, tnx

Se gap == 2 allora gap = 1, swaps = 1, perchè quando il passo arriva a 2, avrà già
fatto un passaggio a 2, e senza questo controllo rimarrebbe sempre 2, per via del
gap / 1.3, che viene convertito in integer, qundi farà gli ultimi passaggi con
il passo 1 e se non ci saranno scambi (swaps==0) && (gap==1) il ciclo termina.