største værdi i et array

iterer igennem og husker på det største tal du har mødt ?

lav en .sort på dit array, så har du den største værdi i sidste element.

//akj

Absolut kun 3 vædier?

int max=a[0];
if (a[1]>max) max=a[1];
if (a[2]>max) max=a[2];

Du sammenligner de tre tal! Start med at ligge de første tal over i en variabel X. Næste gang du sammenligner skal værdien kun ligges over i variavlen hvis den er større end den værdi osm allerede ligger i X! Tilsids har du så det højeste tal i arrayet!

dk_aki
At sortere et array med kun 3 elementer er totalt overkill:

rubberglove:
Brug erik's løsning.

Overkill måske men det kan løses på en kodelinie og virker selvom der pludseligt er 4  eller flere elementer i array'et.

//akj

Disky... Da sort benytter en quicksort rutine vil dette som regel altid være hurtigst!

En quicksort er meget langsommere end et lineært gennemløb, som
er tilstrækkeligt for at finde max. Altså: overkill.

Bare af nysgerrighed...
Hvor mange mili/micro/namo sekunder vil en .sort løsning være ift. alm sammenligning ??

//akj

Ps: Håber ikke jeg har startet en religionskrig :o)

Overhovedet ikke. Det handler ikke om tro, men om fakta.
Og hastigheden afhænger af størrelsen af det pågældende array.
Da lineær søgning altid er hurtigst, er det omsonst at begynde
at sætte tal på.

Quicksort = n*log(n) performance
Gennemløb = n performance

Det er rigtig nok, men stadig væk skal der også tænkes på at man sommetider vil have mindste værdien af et array!

Denne godt findes i et smæk, men det kræver at du koder en del for at finde begge del. Hvis du ligger mindste og største værdi i to seperate funktioner vil du have 2 gennemløb på n performance, hvilket vil være dårligere end n*log(n) performance hvor du vil kunne finde begge elementer.

Efter du har sortere vil oxo kunne benytte en binær søgning til at finde en værdi i arrayet.

Sorry for mit dårlige dansk :-)

nu er der ingen der tvinger dig til at lade være med at finde både max og min i et gennemløb

Du har ikke ret, rj7971. At finde max og min er stadig markant
billigere end at sortere, uanset sorteringsmetode.

rj7971:
Korrekt ved større talmængder, men startop tiden er stor for quicksort, den er også rekursiv (oftest) hvilket resulterer i stort forbrug af stack.

Forresten er quicksorts tidskomplextitet kun n*log(n) normalt, i værste tilfælde er den n^2 (når data ligger i perfekt omvendt rækkefølge)

En gennemløb med en komplexitet på O(n) er ALTID hurtigere end quicksort !

dk_aji:
Man skal ikke bruge en smart sorteringsalgoritme når man kun har 3 data, en dygtig programmør vælger værktøj efter problemstilling.
Hvis man senere skal finde max værdi i 100000 elementer er gennemløb stadigvæk det hurtigste :)

Oki, så har jeg da også lært noget idag :o)

dvs at jeg skal bruge erikjakobsens model :

int max=a[0];
if (a[1]>max) max=a[1];
if (a[2]>max) max=a[2];

cool nok med lidt diskussion... poster du et svar

Mig - nej. Jeg samler ikke på ligegyldige point.

disky:
Taget fra JDK dokumentationen:
The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

Det vil dog sige at den også kan rygge ned i n^2 men dette sker sjældent!

Men, rj, uagtet dette er denne sortering langt dårligere end et
enkelt lineært gennemløb - eller 2.

"vil du have 2 gennemløb på n performance, hvilket vil
være dårligere end n*log(n)" er noget sludder.

To O(n) algoritmer giver stadig en O(n) algoritme.

Arne:
to O(n) algoritner = O(2n) algoritme

" i værste tilfælde er den n^2 (når data ligger i perfekt
omvendt rækkefølge)" gælder ikke quicksort generelt men
kun quicksort med første eller sidste element som pivot
element.

(hvorfor de fleste vel tager midterste element som pivot element)

rj7971:
Der er ikke noget der hedder en O(2n) algoritme.
O(n) betyder at tid er proportilnal med n (og det "er"
2n også).

Sorry Arne, jeg har lige skrevet noget pjat..... Sorry.... Det er min fejl...

Men jeg vil stadig sige at hvis man har to gennemløb af n performance
altså n + n, vil en n*log(n) være teoretisk hurtigere

Nej, rj, log(n) er større end 2 for alle interessante n. For små n gælder
n*log(n) jo alligevel ikke.

Nej.

n              2*n        n*log10(n)
1                2                0
10              20            10
100          200            200
1000        2000          3000
1000000 2000000    6000000

lukket