Diese Seite ist unverschlüsselt! Um sicherzustellen, das Ihr Passwort nicht ausgelesen werden kann, sollten Sie auf die verschlüsselte Seite wechseln!

    Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » größte zahl finden
Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 < [ 2 ]
000
04.11.2003, 15:39 Uhr
kronos
Quotenfisch
(Operator)


hi!
ich habe einen 1-dimensionalen array mit zahlen, was ist die effizienteste methode die nur größte zahl zu finden? und um die zweitgrößte, drittgrößte usw. zu finden?
qsort ist zu langsam außerdem soll die reihenfolge im array erhalten bleiben..
vielen dank für antworten!!
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
04.11.2003, 16:01 Uhr
Muffin



 würde sowas wie einen bubble sort schreiben und vielleicht in ein zweites array, wo dann die reihenfolge der grösse entsprechend ist... sonst müsstest ja variablen anlegen, oder willst immer wieder durchsuchen wenn die größte brauchst?

nur so ein gedanke
--
Gruß
Muffin
--- Ein Tag ohne ein Lächeln ist ein verlorener Tag, auch wenn Windows nicht so tut wie ich will ---
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
04.11.2003, 16:11 Uhr
0xdeadbeef
Gott
(Operator)


Es gibt keinen schnelleren Sortieralgorithmus als qsort, wenn das Array keine besonderen Eigenschaften hat, die sich dafür ausnutzen lassen.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
04.11.2003, 16:21 Uhr
(un)wissender
Niveauwart


doch sort() :-)
--
Wer früher stirbt ist länger tot.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
04.11.2003, 16:22 Uhr
(un)wissender
Niveauwart


Oh, stimmt, ohne vgl. ist qsort auch schnell, sorry.
Ja, ja erst lesen, dann posten!
--
Wer früher stirbt ist länger tot.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
04.11.2003, 16:23 Uhr
ao

(Operator)



Zitat:
kronos postete
ich habe einen 1-dimensionalen array mit zahlen, was ist die effizienteste methode die nur größte zahl zu finden? und um die zweitgrößte, drittgrößte usw. zu finden?

Um nur die größte Zahl zu finden, musst du überhaupt nicht sortieren, sondern nur linear suchen.

Und um die M größten Zahlen zu finden, reicht es, M-mal zu suchen. Wenn N (Länge des Arrays) viel größer ist als M (1000 gegenüber 3?), ist das schneller als das ganze Array zu sortieren.

ao
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
04.11.2003, 16:37 Uhr
void*
Generic Pointer
(Operator)


Hallo,

oder man kann 1-Mal suchen und sich währenddessen die M groessten merken...wobei man dabei natürlich die 3 Zahlen immer wieder vergleichen oder sortieren muss. Was ist dann schneller?

Gruß
void*
--
Gruß
void*
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
04.11.2003, 16:50 Uhr
0xdeadbeef
Gott
(Operator)


Das ist aber nur dann schneller als Quicksort, wenn das Array sehr lang ist und du relativ wenige der größten Zahlen rauskriegen willst. Wenn n die Länge des Arrays ist und du die m größten Zahlen wissen willst, skaliert dein Algo mit O(n * m^2), Quicksort skaliert mit O(n*log(n)).
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
04.11.2003, 17:16 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)


wobei man bei O(n*m^2) auf der sicheren seite ist n*log(n) ist nur im durchschnitt drin, kann auch gegen n^2 laufen
--
...fleißig wie zwei Weißbrote
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
04.11.2003, 17:23 Uhr
0xdeadbeef
Gott
(Operator)


Das ist allerdings sehr selten, du müsstest bei jeder Partitionierung extremes Pech mit dem Pivot-Element haben.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
Dieser Post wurde am 04.11.2003 um 17:23 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 < [ 2 ]     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: