Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » Top100 Sortieren mittels Quicksort

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
15.12.2003, 17:02 Uhr
~Jupp82
Gast


Tach zusammen !

Ich hab ein "kleines" Problem.
Ich habe ein Array mit 10.000 Zahlen und möchte nun das ganze so sortieren, dass die 100 höchsten Eintrage auf die 100 ersten Indices des Array verteilt werden => also z.B. so:


C++:
nArray[0] = 100000;
nArray[1] = 85947;
nArray[2] = 85865;
// usw. => Top 100 des Array absteigend sortiert



Ich möchte diese Sortierung gerne mit dem Quicksort-Algorithmus machen.
Eine Einschränkung ist, dass die Sortierung so erfolgen soll, dass möglichst nicht immer das ganze Array durchlaufen wird, weil ich später vorhabe, eine größere Anzahl von Elementen hinzuzufügen.

Hoffe auf Eure Hilfe - Pseudocode oder eine Erklärung, wie ich an das Problem rangehen könnte, reichen auch aus ... aber wenn einer ne Code-Lösung hat - da wäre ich auch nicht abgeneigt

Gruß

Jupp82
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
15.12.2003, 17:21 Uhr
0xdeadbeef
Gott
(Operator)


Ich denke, das sinnvollste dürfte sein, direkt einen Baum zu benutzen. In C++ bietet sich std::multiset an. Das ist dann zwar aufsteigend sortiert, so dass du statt eines normalen Iterators einen reverse_iterator benutzen musst, aber das hat keine wirklich negativen Auswirkungen. Was genau möchtest du denn nachher damit machen?
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
17.12.2003, 01:12 Uhr
lubU



jmd en tipp wie sowas in C funktioniert ?
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
17.12.2003, 06:59 Uhr
derphilipder



Was? Sortieralgorithmus? Baum? Präzisiere er!
--
Konfuzius says: "A man who goes to bed with an itchy asshole is a man who wakes up with stinky finger!"
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
17.12.2003, 15:34 Uhr
lubU



ich denke ein sortieralgorithmus wäre am sinvollsten.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
17.12.2003, 16:34 Uhr
derphilipder



Da gibts unterschiedliche Möglichkeiten

z.B:

-Bubble-Sort: Eine Liste wir immer wieder durchlaufen und zwei nebeneinanderliegende Elemente, je nach dem ob das eine größer/kleiner ist als das andere, getauscht. Wenn irgendwann das in einem Durchlauf nichts mehr getauscht wird, ist die Liste sortiert.

-Selection-Sort: Eine Liste wird durchlaufen und sich dabei das größte/kleinste Element gemerkt und am Ende des Durchlaufs z.B an den Anfang gepackt.
Im nächsten Durchlauf beginnt man dann mit den Durchlauf bei der zweiten Komponente usw...

-Quicksort:
1.Wenn die Liste leer ist, ist sie bereits sortiert und wir sind fertig.
2.Andernfalls wird x (das erste Element) aus der Liste herausgenommen.
3.Die Restliste wird in zwei neue aufgeteilt - eine enthält alle Elemente, die kleiner als x sind, die andere alle Elemente, die größer oder gleich x sind.
4.Diese zwei neuen Listen werden rekursiv nach der gleichen Strategie (1.-3.) sortiert.
5.Die beiden (jetzt sortierten) Listen werden aneinandergehängt, wobei x wieder zwischen ihnen eingefügt wird.
--
Konfuzius says: "A man who goes to bed with an itchy asshole is a man who wakes up with stinky finger!"
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
17.12.2003, 16:35 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)


qsort gibt es schon als fertige funktion in c für beispiele einfach mal das forum nach qsort durchsuchen....
--
...fleißig wie zwei Weißbrote
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
17.12.2003, 16:43 Uhr
0xdeadbeef
Gott
(Operator)



Code:
QSORT(3)                     Bibliotheksfunktionen                    QSORT(3)



[b]BEZEICHNUNG[/b]
       qsort - sortiert ein Array

[b]ÜBERSICHT
       #include <stdlib.h>

       void qsort(void *base, size_t nmemb, size_t size,
              int (*compar)(const void *, const void *))

BESCHREIBUNG[/b]
       Die  Funktion  [b]qsort()[/b] sortiert ein Array mit [u]nmemb[/u] Elementen der Größe
       [u]size[/u].  Das Argument [u]base[/u] zeigt auf den Anfang des Arrays.

       Die Inhalte des Arrays werden  in  aufsteigender  Reihenfolge  sortiert
       bezogen  auf  eine Vergleichsfunktion, auf die [u]compar[/u] zeigt, welche mit
       zwei Argumenten aufgerufen wird, die auf die zu vergleichenden  Objekte
       zeigen.

       Die Vergleichsfunktion muß eine Ganzzahl zurückgeben, die kleiner Null,
       gleich Null oder größer Null ist, je nachdem,  ob  das  erste  Argument
       kleiner,  gleich  oder größer als das zweite ist.  Wenn zwei Felder des
       Array gleich sind ist ihre Reihenfolge unbestimmt.

[b]RÜCKGABEWERT[/b]
       Die Funktion [b]qsort()[/b] gibt keinen Wert zurück.

[b]KONFORM ZU[/b]
       SVID 3, POSIX, BSD 4.3, ISO 9899

[b]SIEHE AUCH[/b]
       [b]sort[/b](1)




GNU                              6. Juni 1996                         QSORT(3)


--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 17.12.2003 um 16:47 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
17.12.2003, 16:51 Uhr
lubU



wird dann die niedrigste Zahl in array[0]
und die höchst zahl im letzten arrayfeld bspw. array[100] gespeichert ?
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
17.12.2003, 16:53 Uhr
0xdeadbeef
Gott
(Operator)


Je nachdem, wierum deine compar-Funktion das macht.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
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: