Newsgroup: it.comp.lang.c
Titolo: algoritmo di ordinamento per selezione

Poichè mi sono looppato la testa chidevo un piccolo aiutino per risolvere il
seguente problema:
Dato il seguente algoritmo di sort selection ( vedi selectionSort() sotto ),
mi viene richiesto di implementare un sort per selezione che mi elimini i
doppioni durante il processo.
int *selectionSort(int *a, int n)
{
int i, j, p, min;
 for (i=0; i<n; i++)
 {
  min = a[i];
  p=i;
  for (j=i+1; j<n; j++)
  {
   if (a[j]<min)
   {
    min = a[j];
    p = j;
   }
  }
  a[p] = a[i];
  a[i] = min;
 }
return a;
}

Il tuo algoritmo ordina un vettore di n interi, con un ordine di
complessita' di n^2.
Il modo in cui lo scrivi (il fatto di restituire il vettore ordinato)
suggerisce che  forse volevi usare un altro metodo di ordinamento
ricorsivo, quale il Quick Sort (con ordine di complessita' n*log(n) ).
Quale che sia il tuo algoritmo, magari anche ottimo e non ricorsivo
(Shell Sort), il problema di fondo e' come fare a "cancellare" i
doppioni.
In un array numerico, infatti, non esiste l'idea di "terminatore" di
default (come possono avere le stringhe), cosi' devi escogitare un
sistema per ricordare il numero di elementi presenti in ogni istante
dentro l'array.
E' logico che se vuoi cancellare "impunemente" qualche numero dal tuo
vettore, o usi un vettore/array dinamico, oppure gestisci
personalmente una sorta di terminatore finale, che non ti nascondo
potrebbe non essere riconosciuto qualora il tuo intervallo di valori
memorizzabili occupi tutte le configurazioni di bit che hai a
disposizione.
Altra soluzione, piu' semplice e diretta sarebbe quella di far
modificare dalla tua funzione la variabile contenente il numero di
elementi, e quindi passare tale dato per indirizzo. La soluzione di
sotto e' un Bubble Sort modificato.  Ho lasciato che la funzione
restituisse il puntatore ad intero, di modo che se vuoi puoi giocarci
un po' e sostituire il meccanismo con un altro ricorsivo piu' veloce.
int *selectionbubble(int *a, int *n)
{
int i , swap , ultimo ;
 ultimo = *n-1;
 for (i=0; i<*n-1; i++) {
  if (a[i]>=a[i+1]) {
   swap=a[i];
   a[i]=a[i+1];
   a[i+1]=swap;
   if (a[i]==a[i+1]) {
    /* sposto in fondo */
    swap = a[i+1];
    a[i+1]=a[ultimo];
    a[ultimo--]=swap;
    (*n)--;
   }
  i=-1;
  }
 }
 return a;
}

 }
Pensavo di averne viste tante... ma la tua implementazione
del bubble sort O(N^3) e' veramente una chicca.
--
----------------------------------------------------------------
 <\___/>  Andrea        email: agriff at tin dot it
 / . . \  "6502"          irc: _6502_@EFNET#italia
(  (")  ) Griffini   homepage: 
http://www.netservers.com/~agriff
Sent via Deja.com
http://www.deja.com/


"Evidentemente quando il buon Gesu' distribui' la pazienza, io ho
fatto due giri! "
Stimatissimo .... Andrea Griffini (?!?), credo che un conto sia la
conoscenza del mezzo e un altro il modo migliore per utilizzarlo in un
contesto adeguato.
E' fuori di dubbio che volendo essere pienamente utile a chi chiede
"le basi" tu dimentichi, dall'alto della tua incommensurabile
prosopopea, di usare un frasario alla portata del richiedente.
In questo caso, e' ovvio che la soluzione ottima si ottiene con
algoritmi di ordinamento ottimo su strutture dati dinamiche, o piu'
semplicemente, ordinando prima il vettore e poi eliminando i doppioni.
Si potrebbe, guarda un po', impostare un algoritmo parallelo .... ma
sarebbe veramente utile per chi domanda?
Appurato il tuo spirito critico che ti porta a contestare testi ed
emeriti autori che invece vai elogiando in altri newsgroup (inviero'
copie dei tuoi pregiatissimi e pubblici messaggi anche in
"it.comp.lang.c++"), ti esorterei cortesemente a chiedere piuttosto
che a criticare, questo se non altro per non rischiare di passare per
quello che il buon Toto' andava affermando aggiungendo la frase:
"...si informi!", e che io non ti auguro di certo.
Non te la prendere. Una svista puo' capitare a tutti; evidentemente
non condividi la mia premessa che esorta Graziano a modificare quanto
ho suggerito per trasformarlo in uno Shell Sort con uno sforzo
praticamente nullo, malgrado tu stesso vada elogiando lo sforzo
"guidato" da parte del richiedente .... attento perche'
contraddicendoti troppo spesso qualcuno potrebbe pensare che non ti si
possa prendere sul serio.
Ovviamente, parlando tra di noi, posso senz'altro abbassarmi per
risponderti che la tua analisi di costo computazionale e' inadeguata
per il via del fatto che questo e' un algoritmo "on-line" (...
suggerirti testi in passato non e' servito a granche' ...). Per questi
algoritmi ci sono funzioni di costo  di gran lunga piu' attinenti alla
realta' (per farti capire, e' lo stesso motivo per cui l'algoritmo del
simplesso, pur essendo di complessita' non polinomiale, va cosi'
bene).
Devi perdonarmi se non mi dilungo a parlare di Complessita'
Computazionale con te, ma ho gia' avuto prova delle tue capacita'
anche in questo campo.
Divertiti, se vuoi, non tanto a dimostrare formalmente il tuo calcolo,
quanto a produrre un esempio in cui l'algoritmo in questione, pur
inefficiente, raggiunge o supera il limite da te calcolato di O(n^3)
.... e poi in numero di iterazioni o di "swap"? (ti sara' giunto
all'orecchio che c'e' un bel po' di differenza tra il calcolo teorico
del costo computazionale di un algoritmo e quello pratico) Questo
assolutamente non per difendere il mio programma, che e' solo a scopo
didattico e di stimolo, ma per farti prendere coscienza della tua
condizione.
Mi scuserai di certo se non rispondendoti in futuro daro'
l'impressione -voluta - di snobbarti; la realta' e' che, come molti
che ti leggono, anch'io maturero' una rassegnata ilarita'.