Newsgroup: it.comp.lang.c
Titolo: Algoritmo di sorting

Ciao!
 Ho come "compito" di fare un algoritmo che dati in ingresso n valori
(n dato dall'utente) li ordini dal + piccolo al + grande.
Immagino sia trito e ritrito come problema, ma vorrei sapere le vostre
opinioni. Io avevo realizzato un programma che solo dopo ho saputo da
un amico che si chiama Bubble Sorting. In pratica la mia idea era
quella di fare confronti a coppie (incrociando, ovvero 1 con 2, 2 con
3, 3 con 4...) e invertire la coppia se ad es. 1<2... 
Pero' mi e' stato detto che non e' il piu' veloce... ma allora quale
e'?
Grazie!


Il piu' veloce mi sembra che sia il quicksort che ha un'ordine di
complessita' di 
O(n*log(n)) (Bubble-sort O(n^2)).
Ciao.
-- 
     (ZZZ)       Filippo Salotti, Bagni di Lucca, Lucca, Italy.
    //   \\  _                 E-mail : 
fil...@humnet.unipi.it
   /Y\    ZD<_o===============================================o
 .oZZZZZo.     | Studente Ingegneria Informatica Automatica  |
<OXXXXXXXO>    | Dip. Sistemi Elettrici Universita' di Pisa. |

e'?
Per un numero relativamente grande di dati e' sempre meglio usare il
quick sort.
Ma ne esistono diversi, tra cui lo shell sort e l'insertion sort che
funzionano meglio su un numero di dati piccolo.
Il seguente codice implementa il quick sort per numeri in virgola
mobile :
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void scambia ( float * p1, float * p2 )
{
     float temp = *p1 ;
     *p1 = *p2, *p2 = temp ;
}
float *partizione ( float  *ptr_basso, float * ptr_alto )
{
       float indice = * ( ptr_basso + (ptr_alto - ptr_basso) / 2 ) ;
       while ( ptr_basso <= ptr_alto )
       {
             while ( *ptr_basso < indice )
                   ptr_basso++ ;
             while ( *ptr_alto > indice )
                   ptr_alto-- ;
             if ( ptr_basso <= ptr_alto )
                 scambia ( ptr_basso++, ptr_alto-- ) ;
       }
       return ptr_basso ;
}
void quick_sort ( float *ptr_basso, float *ptr_alto )
{
     float *ptr_indice ;
     if ( ptr_basso < ptr_alto )
     {
        ptr_indice = partizione ( ptr_basso, ptr_alto ) ;
        quick_sort ( ptr_basso, ptr_indice - 1 ) ;
        quick_sort ( ptr_indice, ptr_alto ) ;
     }
}
void scrivi_dati ( float * dati, unsigned dimensione )
{
     unsigned i ;
     for (i = 0 ; i < dimensione ; i++ )
         printf("%5.3f, ", dati[i] ) ;
     printf("\n") ;
}
int main()
{
    float *dati ;
    unsigned i, dimensione = 0 ;
    printf("numero di elementi da generare : ");
    scanf("%u", &dimensione) ;
    dati = calloc ( dimensione, sizeof( float ) ) ;
    if ( dati )
    {
       /* genera i dati in modo pseudo-casuale */
       for (i = 0 ; i < dimensione ; i++ )
           dati [i] = sin ( i ) / ( 2.4 + sqrt ( i ) ) ;
       printf("prima dell\'ordinamento : \n");
       scrivi_dati ( dati, dimensione ) ;
       quick_sort ( &dati[0], &dati [dimensione-1] ) ;
       printf("dopo l\'ordinamento : \n");
       scrivi_dati ( dati, dimensione ) ;
    }
    return 0 ;
}
Andrea Laforgia

O(n*log(n)) (Bubble-sort O(n^2)).
Il quick sort ha un "worst-case" di O(n^2).
Andrea Laforgia

 Grazie!
Il bubble sort e' un algoritmo che non si usa mai perche' fa proprio
schifo! Il quick sort e il merge sort sono algoritmi di ordinamento
asintoticamente ottimi (theta di n*log(n) ) tra quelli che operano per
confronti. Puoi avere anche una complessita' lineare, ma devi
abbandonare la filosofia dei confronti: con il counting sort puoi
ordinare n elementi in O(n), con la limitazione che gli n valori stiano
nell'intervallo 1 - k, se k=O(n). Altri algoritmi di ordinamento lineare
sono radix sort e bucket sort. Se vuoi qualcosa di piu' preciso, chiedi
pure (ha da poco fatto l'esame di Algoritmi e Strutture Dati, si vede?
;-) ).
Ciao, Luca.
-- 
*******************************************************
  "C'e' un vecchio detto a riguardo delle reti che    
  recita: i problemi di banda possono essere risolti  
  con il denaro. I problemi di latenza sono piu' dif- 
  ficili poiche' la velocita' della luce e' una cos-  
  tante e non e' possibile corrompere Dio."           
 
                                     David Clark, MIT 
  Reply to 
bia...@maganet.net
*******************************************************

 wrote in message
371a51a5...@diesel.cu.mi.it...


dati sono in numero pari e non ordinati.
Mergesort ha una complessita' del tempo di esecuzione O(n)= n*logn
indipendentemente dalla disposizione e dal tipo dei dati, QuickSort non puo'
vantare lo stesso primato, tant'e' che oscilla tra n*n (caso peggiore
ordinati al rovescio) e n*logn. MergeSort e piu' facile da applicare a liste
e QuickSort ad array. Per valutare quanto piccola deve essere la quantita'
di dati basta che sostituisci la cardinalita' del tuo campione in O(n) e ti
accorgi che deve essere veramente piccola per non usare  MergeSort o
QuickSort:-).
Ciao, Marco.

Ciao, Marco.
Forse questi dati possono essere utili alla discussione, sono delle
prove che ho fatto poco tempo fa, la macchina e' un p2 350 con 64 mb
e Linux.
		Merge-Sort	Quicksort	Selection-sort
n			
100		0,000205	0,000073	0,000204
1000		0,002201	0,000845	0,017389
5000		0,012006	0,004688	0,433114
10000		0,02506		0,009727	1,777986
20000		0,051178	0,020487	7,157139
50000		0,139744	0,054871	45,322114
100000		0,286864	0,116842	179,026059
500000		1,645464	0,649461	6369,601833
1000000		3,461371	1,403434	n.d.
10000000	66,855292	16,76779	n.d.
20000000	206,622463	113,2551	n.d.
I tempi sono in secondi.
Bonf

Bonf
Mi sembra troppa la differenza tra MergeSort e QuickSort hai i sorgenti, dei
due algoritmi non vorrei che l'implementazione di uno rispetto all'altra sia
stata penalizzata in qualcosa. Poi non mi tornano i valori dei tempi,
MergeSort e QuickSort dovrebbero avere un trend di crescita simile e a prima
vista dai valori che leggo non sembra essere cosi', boh.
Ciao, Marco.



Mi aspettavo commenti di questo tipo, infatti a prima vista i tempi
mettono un po' paura, pero' i conti tornano. La differenza tra quick e
merge e' dovuta al fatto che quick lavora in loco, mentre merge no,
infatti mi sono fermato a 20M perche' oltre quel valore merge
cominciava ad usare troppa memoria (ho 64 mb) ed i 
tempi sarebbero stati falsati (gia' gli ultimi che ho messo lo sono),
comunque facendo un grafico si nota che l'andamento e' quello che ci
si aspetta.
Per quanto riguarda il selection, mentre lavorava avevo fatto una
previsione e devo dire che e' (piu' o meno)stata rispettata :
180                x
____________  = _______________
100.000 ^ 2     500.000 ^ 2
x = 4500
Bonf
---------------------------------------------------------------------------------
-  Bonf : Per scrivermi bonf at penguinpowered com                              - 
---------------------------------------------------------------------------------
-  Hint : Buttate  KDE nel cesso e installate Gnome 1.0                         - 
---------------------------------------------------------------------------------

merge e' dovuta al fatto che quick lavora in loco, mentre merge no,
Ok, allora e' solo un problema di implementazione dei due algoritmi, uno e'
molto piu' efficiente dell'altro solo perche' e' piu' ottimizzato,
lavorandoci un po' su si dovrebbe migliorare anche l'altro :-))
Ciao, Marco