Ricorsione con InsertionSort

[Giova411]

Ciao a tutti,
sono MOLTO insicuro su una versione ricorsiva di InsertionSort:

// InsertionRicorsivo(A, i, f)
// dove A è l'array da ordinare
// i l'indice dell'inizio ed f l'indice della fine

InsertionRicorsivo(A, i, f)
if (i<f)
 temp = A[i+1]
 j = i
  while j>0 and A[j]>temp
     A[j+1] = A[j]
     j = j-1
 A[j+1] = temp
 i = i+1
 InsertionRicorsivo(A,i,f)

[apatriarca]

Che dubbi hai esattamente? Nonostante non veda alcun vantaggio nell'implementare una versione ricorsiva di un insertion sort, mi sembra corretta. Ovviamente c'è ancora una parte iterativa. Se il tuo obiettivo era averla completamente ricorsiva allora anche quella parte richiederebbe una trasformazione.

[Giova411]

Si era uno esercizio del Cormen e volevo scrivere il codice pur sapendo di ottenere sempre un tempo $\theta(n^2)$
Esattamente, come dici, la vorrei fare "totalmente ricorsiva"

[apatriarca]

Hai per prima cosa bisogno di un parametro aggiuntivo: l'indice dell'elemento da testare con quello preso attualmente in considerazione. Dovresti avere insomma qualcosa come il seguente (è codice Python):

def insertion_sort_rec(A, i, j, n):
	if i >= n:
		return A
	if j >= 0 and A[j] > A[j+1]:
		temp = A[j]
		A[j] = A[j+1]
		A[j+1] = temp
		return insertion_sort_rec(A, i, j-1, n)
	else:
		return insertion_sort_rec(A, i+1, i, n)

[Giova411]

Sei grande grande grande!!!
Figata Python!!!
Vado in OT se chiedo consigli per un buon libro di Python?!
Vengo dalla scuola C, C++, Java, JSP, Php... Mai visto il Python però ancora

[Giova411]

http://www.youtube.com/watch?v=ROalU379 ... re=related
=)