Newsgroup: it.comp.lang.c++
Titolo: quicksort

sto cercando di utilizzare qsort con un'array di stringhe ma non ne sono
capace, mi
dà sempre errore (penso di aver capito che accetta solo un'array di interi,
o mi sbaglio?)
se volessi scrivere la funzione da me come dovrei fare?
io pensavo: ho la lista A ordinata ed inserisco un elemento c.
prendo l'elemento in posizione A/2 e lo confronto con c, se c < A/2 prendo
A/4 altrimenti 3/4A.
e giusto fare così? e come mi comporto con numeri pari e dispari?

Rossi Andrea ha scritto:
hai provato cosě:
#include <string>
std::string array [3];
?
ciao
-- 
Luigi
--
bug windows [5] = {"95", "98", "NT", "Me", "2000"};

Utilizza questa versione del quick_sort vedrai che non avrai più problemi.
struct indirizzo{
 char cognome[MAX];
   char nome[MAX];
   char citta[MAX+MAX];
   char cap[6];
};
void qs_struct(indirizzo elem[], int inf, int sup){
 int s=inf, d=sup;
   indirizzo appoggio;
   char* perno;
   perno=elem[(s+d)/2].cap;
   do{
    while(strcmp(elem[s].cap, perno)<0 && s<sup) s++;
  while(strcmp(elem[s].cap, perno)>0 && d>inf) d--;
      if(s<=d){
       appoggio=elem[s];
         elem[s]=elem[d];
         elem[d]=appoggio;
         s++;
         d--;
      }
   }while(s<=d);
   if(d>inf){
    qs_struct(elem,inf,d);
   }
   if(s<sup){
    qs_struct(elem,s,sup);
   }

e come mi comporto con numeri pari e dispari?
????
Anto
--
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

 questo qua sopra non č il quicksort.
no, non lo e' credo che stesse spiegando (male) uno dei vari metodi per
scegliere il pivot. (qualcosa tipo median of three).
Alex


A proposito. Perche' non aggiorni l'articolo con le tre piu' famose "migliorie"
al QSort "classico"? Ovvero rimozione della ricorsione, algorithm switch verso
il selection sort per vettori brevi e median of three per la scelta del pivot?
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

il selection sort per vettori brevi e median of three per la scelta del pivot?
ci sono alcuni buoni motivi:
1) è un tip, non un articolo, quindi non può essere troppo lungo.
2) non ho tempo (maturità :-( )
3) non li conosco a fondo ;-)


 3) non li conosco a fondo ;-)
Questo mi sembra un motivo per farlo. Non ci vuole molta ricerca. E poi puoi
anche chiedere nel NG (non sarebbe neppure OT, se la domanda la poni a livello
di algoritmo e non a livello di codice pascal).


di algoritmo e non a livello di codice pascal).
si hai ragione, ma tanto appena ho finito gli esami ho il Sedgewick
appena comprato che mi aspetta... 



Quale? Io ho "Algoritmi in C++" del '92. Ci trovi tutte e tre le cose nel
capitolo sul qsort. Bel libro. Un pochino datato (soprattutto nell'uso del
linguaggio che e' poco piu' di un C). Ma il concetti relativi agli algoritmi non
muoiono mai.
Ma ci sono anche "Algoritms in C" del '90, "Algoritms in C: Fundamentals, Data
Structures, Sorting, Searching" del '97, e il fratello "Algoritms in C++:
Fundamentals, Data Structures, Sorting, Searching" del '98 nonche' "An
Introduction to The Analysis of Algorithms" del '96.


 Introduction to The Analysis of Algorithms" del '96.
Hai dimenticato "The return of the son of Algorithms in C++" :-)
Ciao,
Nicola

 wrote in message
news:3B208D3F...@divalsim.it...

LOL
Ma la tua ironia dimostra che non hai capito lo spirito del mio messaggio.
D'accordo che le FAQ non vengono aggiornate in base ai messaggi che passano e
che pochi seguono la netiquette e si leggono le ultime n settimane di messaggi
prima di postare. Ma e' anche vero che molte persone postano chiedendo
informazioni bibliografiche sul C++ (soprattutto per imparare il linguaggio) o
su argomenti di programmazione. I vari testi che parlano del linguaggio sono
citati spesso. Ma raramente si tratta di testi sugli algoritmi, sul design,
sulle strutture dati etc. Eccetto a volte l'opra di Knuth, il testo dlla GoF sui
pattern e (raramente) Numerical Recipes.
Quindi penso che possa essere utile a qualcuno avere, ogni tanto, una nota
bibliografica su questi temi correlati. A me piacerebbe che chi legge un nuovo
libro ne postasse un commentino beve breve (non una recensione completa) con
qualche info extra sull'autore e le sue altre opere. Non tutti hanno tempo o
possibilità di monitorare l'universo delle pubblicazioni tecniche nel suo
insieme.


Guarda che sono d'accordo con te! Se vuoi la mia ironia era piu' rivolta
al signor Sedgewick, che pare aver rimescolato argomenti molto simili
secondo tutte le combinazioni possibili.
Ciao,
Nicola
P.S. Anche se non ho letto niente di suo, so che e' un autore
apprezzato.

 wrote in message
news:3B20BB08...@divalsim.it...

Come detto io ho solo un libro. Quello in C++ del '92. Pero' se ci pensi non ha
rimescolato granche': ha semplicemente fatto edizioni aggiornate. Solo che
invece che chiamarle seconda edizione, terza edizione etc. ha modificato i
titoli.
In pratica ha scritto due testi. Il primo piu' pragmatico. Versione in C, poi
versione in C++ (nel '92, quindi un C++ vecchio). Poi estende il testo e cambia
titolo (chiamiamolo second edition, se vuoi), versione C prima versione C++
dopo.
Il secondo testo e' sull'analisi degli algoritmi, quindi una visione piu'
teorica.
Se pensi a Numerical Recipes (in tre o quattro linguaggi e varie revisioni) non
siamo molto lontani.
Comunque si, da quello che ho letto e' un autore apprezzabile.


 insieme.
Hai ragione, comincio subito in materia di algoritmi :
Data Structures & Algorithm Analysis in C++ second edition.
Mak Allen Weiss
ISBN 0-201-36122-1
Mark Allen Weiss ha preso il Ph.D. sotto Sedgewick ed ora insegna alla
universita' internazionale della Florida. Ha ricevuto moltissimi awards per
la ricerca e per l'insegnamento.
Il libro parte con un breve review della matematica necessaria, poi passa a
spiegare i concetti principali della OOP ed alcuni dettagli del C++(classi,
templates etc..)
Poi iniziano i veri capitoli:
2) Algorithm Analysis
3) Lists, Stacks, Queues
4) Trees
5) Hashing
6) Priority Queues(Heaps)
7) Sorting
8) The Disjoint Set ADT
9) Graph Algorithms
10) Algorithm Design Techniques
11) Amortized Analysis
12) Advanced Data Structures and Implementation
A) The standard Template Library
B) vector and string Classes (fatte dall'autore)
Il libro e' nuovo :  fine '99 e presenta tutti gli algoritmi in un C++ molto
moderno, con classi ben progettate e completamente templatizzate.
A me personalmente piace moltissimo ! (questa volta il giudizio era
personale ;-) )
Alex

insieme.
allora inizio io. Ho da poco finito di leggere "Programmazione nella
pratica" di Kernighan e Pike. Veramente ottimo, credo che non dovrebbe
mancare nella biblioteca di chi sta passando dalla fase in cui si
programmano programmi di qualche decina di righe a quella in cui le
linee diventano qualche migliaio.
L'unico appunto è che, in teoria, gli esempi dovrebbero essere in C,
C++ e Java. In pratica sono quasi solo C.
Anto
PS: piccola nota: gli autori hanno fornito anche i benchmark
comparativi dei programmi scritti in C, C++ e Java. E spesso il C++
(con STL, ad esempio) è risultato più veloce del C!!


muoiono mai.
no. Me lo hanno regalato quelli delle olimpiadi e mi hanno dato
"Algoritmi in C". Cmq sono convinto che per imparare gli algoritmi non
è certo necessario il C++ ma vada molto bene anche il C. D'altronde
che bisogno ci sarebbe di insegnare il quicksort in C++ quando si può
usare std::sort?


sto cercando di utilizzare qsort con un'array di stringhe ma non ne sono

Scritto cosi' l'algoritmo mi sembra un po' confuso... :-)
L'algoritmo consiste nelle seguenti operazioni:
- 1 - scelgo un elemento arbitrario del vettore (tu hai scelto quello
di mezzo, io preferisco usare il primo, perché ti permette di
riadattare più facilmente il codice all'ordinamento di una lista);
- 2 - confronti questo elemento con tutti gli altri, e metti quelli
minori da una parte e quelli maggiori dall'altra, dividendo in due
l'insieme;
-3- poni l'elemento di confronto in mezzo ai due insiemi;
- 4 - riapplichi ricorsivamente il quicksort all'insieme dei numeri
maggiori, e all'insieme dei numeri minori;
- 5 - quando l'insieme da ordinare contiene meno di due elementi
finisci il sort;
Sul kernighan (4.10 e 5.6) è spiegato a puntino!

riadattare piů facilmente il codice all'ordinamento di una lista);
Attenzione. Se fai cosi' e la sequenza e' gia' "quasi ordinata"
allora l'algoritmo degenera: al momento della divisione nelle
due meta' tutti gli elementi staranno da una parte e l'altra
risultera' vuota e l'algoritmo diventa O(N^2) (una passata
lunga N + una passata lunga N-1 + ... + una passata lunga 1 =
N+(N-1)+...+1 = N*(N+1)/2; inoltre ti trovi con N chiamate
ricorsive invece di log2(N) del caso ottimale).
Nota anche che un elenco "quasi ordinato" non e' affatto un
caso poco comune.
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 >riadattare più facilmente il codice all'ordinamento di una lista);


 quel punto lo inserisco.
Non sono sicuro di quello che hai fatto ma ho l'impressione che se tu "scandissi
tutta la lista per sapere dove metterlo" (a parte che ti fermeresti nel punto in
cui lo devi mettere) il tuo codice sarebbe un sacco di volte piu' veloce.
Le liste non sono oggetti ad accesso random. Pertanto una operazione "semplice
semplice" come "contronto con l'elemento che sta in mezzo" richiede la scansione
di mezza lista. Peggio: se l'elemento e' maggiore di quello in mezzo tu al passo
successivo lo paragoni con quello in mezzo alla metà superore della lista
(ovvero l'elemento a 3/4 della lista). Dipende da come hai scritto il codice ma
facile facile che questo semplice paragone richieda la scansione di 3/4 della
lista. In questo caso se la lista "in uscita" e' già lunga, per esempio, 15
elementi, e il prossimo da inserire dovesse finire nella 14^ posizione,
scandendo la lista dovresti "scorrere" 14 elementi per scoprirlo. Con il tuo
metodo rischi di doverne scorrere 47!


vabbè, scusa ancora, ma in realtà io parlo di liste perchè mi viene bene, ma
sono array!
cioè oltretutto avevo anche scritto di usare una CList, porc...
uso CArray
d'altra parte dover fare un ordinamento con le liste, e farlo velocemente,
mi fa rizzare
i capelli a solo pensarci

Allora che ho fatto?
...
Il tuo algoritmo e' terribile... o almeno lo e' se con "lista"
intendi quella struttura dati in cui l'accesso all'elemento
n-esimo richiede una scansione di n elementi. Per ordinare una
lista puoi chiedere aiuto all'algoritmo di sort per liste che
e' presente nella libreria standard.


 i capelli a solo pensarci
Se pensi alla velocità che puoi ottenere con un array, certamente. Ma potresti
stupirti delle performance ottenibili nel sort di liste da un buon algoritmo
rispetto a quello che probabilmente otterresti se dovessi "inventarlo" tu sul
momento.



programamzione.it
 in un 'tip' di Cuni.
oppure, ancora meglio, std::vector + std::sort
