Algoritmi - Nuovo algoritmo di ordinamento

Forum - Algoritmi - Nuovo algoritmo di ordinamento - Pagina 4

Pagine: [ 1 2 3 4 ]

Daf (Normal User)
Pro

Messaggi: 78
Iscritto: 27/06/2009

Postato alle 12:09
Lunedì, 29/06/2009

PASCAL

Codice sorgente - presumibilmente Delphi

unit OrdPascal;
 
interface
 
procedure ORDINA(vet: array of Integer, Inizio, Fine: Integer);
 
implementation
 
procedure SWAP(a, b: Pointer);
var
  aus: Pointer;
begin
  aus := a;
  a   := b;
  b   := aus;
end;
 
procedure ORDINA(vet: array of Integer, Inizio, Fine: Integer);
var
  I, max, min: Integer;
begin
  if(Inizio >= Fine)then
    Exit;
   min := Inizio;
   max := Fine;
   for I := Inizio to Fine do
   begin
     if(vet[I] > vet[max])then
       max := I
     else
       if(vet[I] < vet[min])then
         min := I;
   end;
   SWAP(@vet[min], @vet[Inizio]);
   if(max==Inizio)then
     max := min;
   SWAP(@vet[max], @vet[Fine]);
   ORDINA(vet, Inizio + 1, Fine - 1);
end;

C'è una cosa particolare: NON SERVONO LIBRERIE! :k:

Daf (Normal User)
Pro

Messaggi: 78
Iscritto: 27/06/2009

Postato alle 12:13
Lunedì, 29/06/2009

Funzia anke su Delphi

MrC (Member)
Newbie

Messaggi: 19
Iscritto: 28/11/2009

Postato alle 23:07
Martedì, 29/06/2010

Non per avvilire tutti coloro che in futuro tenteranno...

ma c'è una dimostrazione matematica (cioè certa)

che ogni algoritmo di ordinamento (a parte proprietà particolari dei dati)

non può avere una complessità asintotica migliore di O( n * log(n) )

:om:

eddiewrc (Member)
Expert

Messaggi: 560
Iscritto: 30/04/2006

Postato alle 19:02
Mercoledì, 30/06/2010

si, si chiama lower bound per comparison sort.
se un algoritmo di ordinamento basa il suo funzionamento sui confronti, per ordinare n elementi deve fare almeno n log n.

altri algoritmi ordinano in O(n) basandosi su altri stratagemmi

MrC (Member)
Newbie

Messaggi: 19
Iscritto: 28/11/2009

Postato alle 23:02
Venerdì, 16/07/2010

E io cos'ho detto?!

Pagine: [ 1 2 3 4 ]