Newsgroup: it.comp.lang.c
Titolo: Segmentation Fault durante la ricorsione

Perche' questo programma termina con il messaggio "segmentation fault"
durante l'esecuzione?
Se elimino la riga commentata con //RICORSIONE invece funziona.
--
Enos
// Programma per l'ordinamento di una lista di numeri
#include <stdio.h>
#define LISTA 10
int contatore;
int Lista[LISTA];
void Ordina(int FinoA);
main() {
  for (contatore=0; contatore<LISTA; contatore++)
    scanf("%d",&Lista[contatore]);
  Ordina(LISTA-1);
  for (contatore=0; contatore<LISTA; contatore++)
    printf("%d ",Lista[contatore]);
}
void Ordina(int FinoA) {
  int maggiore=0;
  for (contatore=0; contatore<FinoA; contatore++)
    if (Lista[contatore]>Lista[maggiore]) maggiore=contatore;
  contatore=Lista[FinoA];
  Lista[FinoA]=Lista[maggiore];
  Lista[maggiore]=contatore;
  Ordina(FinoA-1);  //RICORSIONE
}

 
ciao
Giacomo

 lo porta a -1 e Lista[-1] genera il segfault.
Grazie!
-- 
Enos


--
Giorgio Silvestri
DSP/Embedded/Real Time OS   Software Engineer

 durante l'esecuzione?
Segue la versione giusta (aggiunti un if e un "=" ).
Quale e' in C l'algoritmo piu' efficente per l'ordinamento di liste?
--
Enos
// Programma per l'ordinamento di una lista di numeri
#include <stdio.h>
#define LISTA 10
int contatore;
int Lista[LISTA];
void Ordina(int FinoA);
main() {
  for (contatore=0; contatore<LISTA; contatore++)
    scanf("%d",&Lista[contatore]);
  Ordina(LISTA-1);
  for (contatore=0; contatore<LISTA; contatore++)
    printf("%d ",Lista[contatore]);
}
void Ordina(int FinoA) {
  int maggiore=0;
  for (contatore=0; contatore<=FinoA; contatore++)
    if (Lista[contatore]>Lista[maggiore]) maggiore=contatore;
  contatore=Lista[FinoA];
  Lista[FinoA]=Lista[maggiore];
  Lista[maggiore]=contatore;
  if (FinoA) Ordina(FinoA-1);
}


Ulteriormente migliorabile con:
...
   if (FinoA > 1) Ordina(FinoA-1);
...
e forse anche in altro modo.
A parte queste inezie, di algoritmi efficienti ne esistono
infiniti. In generale intendo, non solo in C.
Alcuni di quelli ottimi in tempo sono:
(a) MergeSort,
(b) HeapSort.
tutti di complessità O(nlogn)-TIME
Mentre esiste un algoritmo eccellente nel caso medio
ma peggiore in casi sfortunati": QuickSort.
All'atto pratico è reputato il migliore, anche se non
lo è dal punto di vista puramente teorico della
complessità computazionale.
Non ti resta che studiarteli un pò.
Dovresti trovare parecchio materiale in giro, sono famosissimi.
Un consiglio: non conviene usare la ricorsione in questo caso.
Hai un significativo overhead dovuto alle chiamate di
funzione.
Senza contare lo stack che se ne và allegramente in crash
per dei valori di LISTA più grandi.


 Quale e' in C l'algoritmo piu' efficente per l'ordinamento di liste?
Nel tuo esempio stai usando un array, se vuoi sapere se c'e' una 
funzione che ordina gli array nella libreria C, dai un'occhiata alla 
funzione qsort()
Se invece ti riferivi a vere e proprie liste con puntatori e tutto, il 
merge sort e' uno dei piu' efficienti con complessita N*log(N) pari al 
quicksort.
ciao
Giacomo

 ha scritto nel
messaggio news:tD%Cg.69307$zy5.1...@twister1.libero.it...

No.
Il mergesort non si applica alle liste ma agli array.
Almeno nella forma classica, quella più conosciuta.
Inoltre:
(a)  MergeSort è N * log(N)
(b) QuickSort è N*N.
E'  N*log(N) nei casi pratici
ma teoricamente quadratico.


 ma teoricamente quadratico.
In effetti hai ragione, e' quadratico nel caso peggiore, ed e' n*log(n) 
nel caso medio (dove "caso medio" e' un termine tecnico con un 
seignificato ben preciso e non significa "in pratica".)
ciao
Giacomo

 sequenziali, quindi per le liste va benone.
In effetti l'origine dovrebbe essere quella.
Probabilmente l'uso sugli array è la forma più conosciuta da me.
Non ordino praticamente mai file sequenziali o liste ma sempre array. :-)


 ma peggiore in casi sfortunati": QuickSort. [...]
Grazie per le risposte.
-- 
Enos