Algoritmi di sort

[Habdul]

Qualcuno saprebbe dirmi/darmi l'algoritmo di insertion sort ricorsivo (funzionante)???

[LeleFT]

L'algoritmo Insertion-Sort non è ricorsivo: è iterativo!! (Certo, si potrebbe disquisire sull'iteazione vista come ricorsione di coda, ma non mi sembra il caso).

Comunque, questo è l'algoritmo Insertion-Sort: (funzionante implica un linguaggio di programmazione, che tu non hai specificato!)

Pseudo-codice:

A: array di elementi
Length: funzione che restituisce la lunghezza dell'array passato come argomento

Insertion-Sort(A) {
   for j=2 TO Length(A) {
      key = A[j]
      i = j - 1
      while ((i > 0) AND (A[i] > key)) {
         A[i + 1] = A[i]
         i = i - 1
      }
      A[i + 1] = key
   }
}

Ciao.

[Habdul]

Originariamente inviato da LeleFT
L'algoritmo Insertion-Sort non è ricorsivo: è iterativo!! (Certo, si potrebbe disquisire sull'iteazione vista come ricorsione di coda, ma non mi sembra il caso).

Comunque, questo è l'algoritmo Insertion-Sort: (funzionante implica un linguaggio di programmazione, che tu non hai specificato!)

Pseudo-codice:

A: array di elementi
Length: funzione che restituisce la lunghezza dell'array passato come argomento

Insertion-Sort(A) {
   for j=2 TO Length(A) {
      key = A[j]
      i = j - 1
      while ((i > 0) AND (A[i] > key)) {
         A[i + 1] = A[i]
         i = i - 1
      }
      A[i + 1] = key
   }
}

Ciao.

Grazie, ma l'iterativo gia lo conosco benissimo!!!!

Devo creare una versione con le liste e con questa struttura la versione ricorsiva c va a nozze!!! Cmq il linguaggio è il C!!!

[cipo_mad]

Versione Ricorsiva
// Programma Insertion Sort ricorsiva
#Include <Stdio.h>
int n=5;
array= ( int*) calloc ( n, size of ( int ) ) ;
Main()

{
.
.
.
Insertion Sort ( & array , n ); /* Chiamata alla procedura Insertion sort con passaggio di valori per indirizzo e per valore */

Void Insertion Sort ( int * a, int n )
{
int j, pos min ;
If (n = =1)
Return;
pos=0;
min= *a;
for ( j=0 ; j> n-1 ; j++ ) /* primo ciclo for che ricerca il piu piccolo elemento e lo mette in cima all’array*/

{
if *(a+j)< Min
{
Min= *(a+j);
pos=j;
}
}
*(a+pos)=*a;
*a= min;
j=2;
do /* ciclo che confronta il terzo elemento dell array con il secondo e ove ci sia uno scambio da fare lo effettua */
{

if *( a+j) < *(a+(j-1))
{
Min= *( a+j);
*(a+j) = *(a+(j-1));
*(a+(j-1))=min;
}

j++;
}
while( j = =n)

insertion sort ( & (a+1), n-1 ); /* chiamata ricorsiva alla stessa funzione con passaggio di un nuovo array piu piccolo di un elemento quello iniziale che gia è assoldato essere il piu piccolo*/
return;
}



eheh sento l'aria di un esame eh?

[Habdul]

Originariamente inviato da cipo_mad
Versione Ricorsiva
// Programma Insertion Sort ricorsiva
#Include <Stdio.h>
int n=5;
array= ( int*) calloc ( n, size of ( int ) ) ;
Main()

{
.
.
.

eheh sento l'aria di un esame eh?

Si!!! Grazie...