Sortieralgorithmen?

Codovan

Welche Sortieralgorithmen auser Bubble- und Quicksort gibt es noch?

Und vorallem wie funktionieren sie?

volkard

Original erstellt von Codovan:
Welche Sortieralgorithmen auser Bubble- und Quicksort gibt es noch?
Und vorallem wie funktionieren sie?

http://volkard.de/vcppkold/inhalt.html
da gibts ne einführung in selection- insertion und shellsort.

außedem sind noch heapsort und mergesort recht wichtig, da muß ich aber auf google verweisen.

HumeSikkins

Hallo,
und was ist mit Introsort? Ist zwar nur ne Kombination, dennoch aber recht interessant.

Griffin

Hier nochma ein paar andere Sortieralgorithmen mit kleiner Beschreibung.
Hoffe es hilft n wenig weiter:)

Selectsort

wenn noch qsort dabei ist, kann man es doch in die FAQ packen.

volkard

Original erstellt von HumeSikkins:
Hallo,
und was ist mit Introsort? Ist zwar nur ne Kombination, dennoch aber recht interessant.

ist für mich nur ne variante von quicksort.
hab nichtmal GamaSort http://www.geocities.com/josephgama/GamaSort.htm aufgeführt.

wichtiger als ne dicke liste wäre ne liste, wo vor- und nachteile aufgeführt werden.

sowas wie
bubblesort:
+einer der einfachten zum üben
+schnell auf vorsortierten arrays
-lahm

selectionsort:
+minimale anzahl von vertauschungen
-lahm
ist manchmal ernsthaft anwendbar, und zwar, wenn die vergleichskosten minimal sind, aber die kopierkosten enorm

insertionsort:
+der bisher schnellste
+schnell auf vorsortierten arrays
-imernoch lahm
hat wie bubble und selection kaum overhead und ist für kleine arrays daher schneller als die folgenden klugen algos
wird gerne als endstufe in kombination mit quicksort etc genommen

shellsort:
+der erste, den man anwenden kann
+gutes beispiel, wie man nen bereits bekannten algo tunen kann

qicksort:
+für zufällige daten der schnellste
-kackt bei vorsortierten daten ab und wird lahmer als bubblesort
-kann viel speicher auf dem stack fressen

mergesort:
-braucht viel speicher
+hat man den, isses schneller als quicksort
+gut für externes sortieren

heapsort:
-leicht lahmer als quicksort

und dann noch ein paar beispiele, wie man so algos kombinieren und abwandeln kann.
quicksort mit insertion, selection oder bubble als endstufe und deutliche beschleunigung sehen. quicksort mit logarithmisch beschränkter rekursionstiefe. mergesort mit durch heapsort vorsortierten blöcken. und irgendwann auch introsort.

Erhard Henkes

nur zur Vollständigkeit, siehe auch:
Robert Sedgewick, Algorithmen in C++, Addison-Wesley

--> FAQ

Helium

Interessant ist vieleicht auch noch Radix

http://www.cubic.org/~submissive/sourcerer/radix.htm

Wenn es darum geht Felder von Zahlen zu sortieren unschlagbar.

volkard

Original erstellt von Helium:
Interessant ist vieleicht auch noch Radix
Wenn es darum geht Felder von Zahlen zu sortieren unschlagbar.

hab ich für wpc37 implementiert! zuerst introsort. dann dacht ich, mit radix werd ich noch schneller. pustekuchen! der zusätlich gebrauchte speicher hats für 100000 elemente abgebremst, daß es nur noch halb so schnell wie introsort war.

tja volkard, dazu kann ich nur sagen: schlecht implementiert von dir

donay

hi.
selbst gemacht ist immer schöner:(ist noch ausbaubar):

int sortarray(int array[6])
{
 int temp;
 for(int where=0;where<=6;where+=1){
  int counter=where;
  for(;counter<=6;counter+=1){
   if(array[where]>array[counter]){
    temp=array[where];
    array[where]=array[counter];
    array[counter]=temp;
   }
   }
  }

schön , nich naja ein kleines durcheinander
bye
donay

[ Dieser Beitrag wurde am 01.12.2002 um 16:00 Uhr von donay editiert. ]

volkard

Original erstellt von donay:
**hi.
selbst gemacht ist immer schöner:(ist noch ausbaubar):
**

Klauen ist auch ganz schön:

int sortarray(int array[6])
{//geklaut von donay und umgefummelt
 for(int where=0;where<=6;++where){
  for(int counter=where;counter<=6;++counter){
   if(array[where]>array[counter]){
    swap(array[where],array[counter]);
  }
 }
}

Jester

@Donay:

Hast Du gesehen? Über Deinem Posting ist ein ganzer Thread!

Nitromaus

Könnte vielleicht auch noch helfen: http://lightning-rpgs.game-dev.de/Site/include.php?path=content/content.php&contentid=7

Dieser Link ist leider nur noch bis zum 31.12.02 unter dieser Adresse zu erreichen.

[ Dieser Beitrag wurde am 01.12.2002 um 16:41 Uhr von Nitromaus editiert. ]

wann kommt das endlich in die faq? volkard oder marc++us oder humesikkins, schreibt noch was schlaues rein und dann ab damit!

donay

@jester:
was wolltest du mir damit sagen???

Mr. N

Original erstellt von volkard:
hab ich für wpc37 implementiert! zuerst introsort. dann dacht ich, mit radix werd ich noch schneller. pustekuchen! der zusätlich gebrauchte speicher hats für 100000 elemente abgebremst, daß es nur noch halb so schnell wie introsort war.

hehe

[ Dieser Beitrag wurde am 04.12.2002 um 16:36 Uhr von Mr. N editiert. ]

Hallo!

Kennt von euch jemand das Sortierungsverfahren Merge Sort? Das ganze Basiert auf "3 Bändern", wo das eingegebene Element (in dem Fall Buchstaben, bzw. Buchstaben eines Wortes), sortiert werden müssen. Die Sortierung an sich habe ich verstanden, nur leider ist mir nicht klar wie ich so das Programm gestalten könnte. Habe auch schon im Internet gesucht, doch leider nichts gefunden.
Habt ihr schon einmal was dazu gefunden? Oder schon so ein Programm bzw. Struktogramm gemacht? Wäre nett wenn ihr mir helfen könntet.

mit freundlichen Grüßen
waterproof

1ntrud0r

wenn du google frägst :

http://www.extreme.indiana.edu/sage/pcxx_ug/subsection3_6_2.html

danke, nur leider verstehe ich von diesem code noch nicht viel, weil ich erst vor ein paar Monaten mit C angefangen habe, und mir dieser Quelltext noch etwas zu komplex ist..außerdem habe ich schon bei google gesucht, nur leider nichts gefunden.