Newsgroup: it.comp.lang.delphi
Titolo: Controllare l'ordinamento di una sequenza

Devo realizzare una funzione che, data una lista di valori, determini se e'
organizzata con consecutivita', cioe' se la lista e' ordinata o meno.
Per implementare questa funzione pensavo di applicare un algoritmo di sorting
alla lista, e nel qual caso ci fossero degli scambi di elementi, riconoscere
la mancata consecutivita' degli elementi nella lista.
Quale algoritmo potrei utilizzare: bubble sort, quick sort, shaker sort?
Oppure delphi fornisce gia' qualche funzione/classe/procedura per determinare
gli elementi che non sono ordinati ?
-- 
Morde. 
(
mo...@despammed.com
)

> Quale algoritmo potrei utilizzare: bubble sort, quick sort, shaker sort?
Circa un milione di anni fa ricordo di aver letto che l'algoritmo più veloce
è il quick sort ?
Non so se nel frattempo ne sono nati degli altri migliori, nè so indicarti
se c'è qualcosa di già fatto in delphi.
Donato Di Tullio

gli elementi che non sono ordinati ?
L'oggetto TList ha un metodo Sort che esegue l'algoritmo Quicksort,
potrebbe fare al caso tuo.
Ciao
Cecilia

è il quick sort ?
A parte questa digressione OT, l'affermazione e' incompleta perche' in realta'
i vari algoritmi "di scambio" che ho citato io, sono performanti *in
relazione* alla *disposizione* degli elementi nella lista.
Non c'e' un algoritmo in assoluto piu' veloce, ognuno ha le sue peculiarita'
in relazione alla lista da ordinare che hai e a come prevedi che sia
presentata (entrano in gioco le statistiche).
Nel mio caso specifico la lista *dovrebbe* presentarsi gia' ordinata, quindi
dovrei scegliere un algoritmo il piu' performante in condizioni simili.
Ciao Dona'!
-- 
Morde. 
(
mo...@despammed.com
)

potrebbe fare al caso tuo.
Si, infatti potrei fare : prendo la lista, la duplico, sorto il duplicato e
confronto le due liste. Gli elementi che differiscono sono quelli fuori posto.
Grazie per il suggerimento Cecilia :)
Ciao!
-- 
Morde. 
(
mo...@despammed.com
)

 ha scritto nel messaggio
news:bv1ovv0vd39aorar5...@4ax.com...

Se il tuo scopo e' solo quello di vedere se la lista e' ordinata lo fai con
un ciclo while, senza algoritmi di ordinamento e altre menate. Se poi vuoi
anche ordinarla e' un altro paio di maniche
lista da 0 a n-1 in ordine crescente
pos:=n-1;
while pos>0 do
begin
  if elemento[pos]<elemento[pos-1] then
    pos:=-1;
  dec(pos);
end;
if pos=-1 then
  (* disordinata *)
else
  (* ordinata*)
Ciao
 Max

 
Se cerchi di fare le cose ottimizzando (quello che sembra dalla tua 
risposta a donato), questa non e' certamente la soluzione piu' 
performante: per controllare se una lista di valori e' ordinata , la 
ordini ed in più la confronti con l'originale? Mah....mi sembra proprio 
una stupidata (scusa il termine)
Secondo me ti basta semplicemente fare al piu' (nel peggiore dei casi) 
una passata (non l'ordinamento totale, una sola passata!) con il 
semplice bubble sort sulla lista (anche senza scambiare realmente i 
valori, magari usa un flag boolean ).
Puoi avere 2 diversi risultati:
1- Non hai scambiato nessun elemento nella lista, quindi la lista è 
ordinata (questo è il caso peggiore, in cui fai una passata intera di 
bubble sort)
2- Hai scambiato un elemento (e qui fermi il la passata di bubble sort: 
nel migliore dei casi ti sei fermato al secondo valore della lista, nel 
peggiore all'ultimo): in questo caso la lista non è ordinata
Fammi sapere come ti sembra
Ciao,Ukkiosan

Ciao,Ukkiosan
Grazie per i suggerimenti, non ricordavo piu' le peculiarita' degli algoritmi
e il tuo aiuto mi ha rischiarito le idee. Anche se poi ieri sera in una
riunione e' stato deciso che non c'era piu' bisogno di questo espediente e i
dati verranno trattati in modo diverso, mi ha fatto bene questo veloce
excursus sugli algoritmi di ordinamento col metodo a scambio (ricordi di un
felice e spensierato periodo della mia vita da studente ribelle ;-))
Sicuramente il bubble sort e' il migliore in questo caso, proprio perche' la
lista si supponeva essere gia' ordinata.
ciao!
-- 
Morde. 
(
mo...@despammed.com
)

 confronto le due liste. Gli elementi che differiscono sono quelli fuori
posto.
scusa il suggerimento banale.. .e fare un semplice ciclo che controlla che
quello prima č minore di quello dopo?
Non so se come cicli CPU sia piů pesante di spostare la lista avanti e
indietro,ordinarla, riconfrontarla ancora...
ad esempio:
Nelementi:=lista.count;
FOR i:=0 to Nelementi-2 do
 IF lista[i]>lista[i+1] THEN
  BEGIN
   // la lista non č ordinata...
  END;
Ciao
Matteo