Sortieralgorithmus
lima-city → Forum → Programmiersprachen → C/C++ und D
anzahl
array
bedenken
code
datum
doppelte zahl
durchgang
feld
funktion
laufzeit
maximum
mus
nachdenken
objekt
richtung
schleifen
sortieren
system
vorstellen
zahl
-
Hi,
also in unserem Fach Algorithmen und Datenstrukturen sollten wir einen Sortieralgorithmus f?r Zahlen in einem Array entwerfen, ich hatte mir da folgendes gedacht (hab ich noch nicht probiert, also auf syntaktische Fehler usw)
int InputArray[500],TempArray[500],OutputArray[500],Max,c;
for(i=0;i<500;i++)
{
TempArray[InputArray] = i;
if(InputArray > Max)
Max = InputArray;
}
for(i=0;i<Max;i++)
{
if(TempArray <> 0)
{
c++
OutputArray[c] = i;
}
}
Request for Comments!
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Sry aber nach 10 Stunden Blockvorlesung heute ist mein Hirn schon im Bett, deshalb Quick & Dirty :
http://www.sortieralgorithmen.de/ -
Es ging mir um eine Schulaufgabe und keine Doktorarbeit ^^
-
Also ich hab jetzt 5 Minuten ?berlegt ob und unter welchen umst?nden das funktionieren k?nnte, m?glicherweise f?r den Fall das die Nummern schon sortiert sind ...
-> int InputArray[500],TempArray[500],OutputArray[500],Max,c;
Ok, Klar, das sind 3 Arrays
-> for(i=0;i<500;i++)
-> {
-> TempArray[InputArray] = i;
-> if(InputArray > Max)
-> Max = InputArray;
-> }
Hm, als erstes ist mir die 3 Zeile ins Auge gesprungen, wozu ist die gut? Wenn ein Wert doppelt vorkommt (ist ja nicht ausgeschlossen diese M?glichkeit) dann w?rde zweimal das selbe Feld mit I beschrieben ... Der Rest sieht mir so aus als wenn das Maximum gesucht wird ...
-> for(i=0;i<Max;i++)
Aha, die Zahlen sind also alle gr??er 0 ??? (und kleiner als 500)
-> {
-> if(TempArray <> 0)
-> {
-> c++
C ist nicht mit 0 initialisiert
-> OutputArray[c] = i;
Das funktioniert sicher nur wenn jede Zahl nur einmal vorkommt ...
-> }
-> }
Also gut ist, das Du Dir selbst einen Kopf gemacht haste, der gew?hnliche Informatikstudent im fortgeschrittenen Semester benutzt gern entsprechende Bibliotheksfunktionen bzw. Iteratorobjekte und steht dann erstmal dumm da wenn er die selbst implementieren mu?. Wichtig ist, alle Nebenbedingungen als solche zu notieren. Ansonsten w?rde ich behaupten das mindestens zwei verschachtelte Schleifen notwendig sind. -
Hallo
P.S. Habe nicht gesegen das schon jemand geantwortet hat.
Also es geht bestimmt nicht darum das du den Besten algo findest.
Den du da aufgeschrieben hast ist aber mit sehr bedenklich.
Erst dachte ich du wolltest den einfachsten Sortirungsalgorithmus implementieren. Aber den hast du nicht.
Was ist an deinen Bedenklich?
Also dein Algo arbeitet nur auf ganzen Zahlen.
Dein TempArray ist gegebenfals zu klein (wenn es nicht zahlen zwischen 0 und 500 sind).
Sollte eine Zahl zweimal auftachen wird eine Zahl nicht gespeicher.
Und wenn die Zahlen, welche ihr Sortiren sollt gross werden hast du ein Problem mit der Laufzeit.
Also der einfachste (soviel kann ich dir wohl verraten) benutzt zwar auch zwei Schleifen, aber nicht ein TempArray sondern nur einen Temp Variable.
Und die Schleifen sind ineinander Geschachtelt.
Laufzeit ist ungef?hr 500*500/2 aber das n?tzt dir wohl wenig.
@tom-nachdenk gew?hnliche Informatikstudent h?rt und analysiert sowas in der Vorlesung.
Jens -
Also es geht nur darum ganze integer-Zahlen zu sortieren. Das TempArray hat 500 nicht als Maximum sondern als Anzahl der Felder. An die doppelte Zahl hab ich ehrlich gesagt nicht gedacht.
-
Hallo
-> Also es geht nur darum ganze integer-Zahlen zu sortieren.
-> Das TempArray hat 500 nicht als Maximum sondern als Anzahl
-> der Felder.
Dein Algo braucht trozem ein TempArray der gr?sse max und nicht der gr?sse 500.
Denn du greifst auch auf Daten des Feldes TempArray[max] zu.
Es ist egal wieviele werte den wert 0 haben.
->An die doppelte Zahl hab ich ehrlich gesagt
-> nicht gedacht.
Solltest du aber. Kannst ja nochmal ?berlegen.
So schwer ist er nicht.
@des-sys las ihn doch selber nachdenken. Denn damit hilft man ihn mehr.
Jens -
hi lord!
um ein integerarray zu sortieren gibt es das sogenannte bubblesort-verfahren.
dabei wird das array von vorn nach hinten durchlaufen und der aktuelle wert mit dem nachfolgenden verglichen.
falls es gr??er ist, werden die werte getauscht.
####################
# // Deklaration der Variablen
# int temp, max=500;
# int array[max];
#
# // F?llen des Arrays
# .
# .
# .
#
# // Sortieren nach BubbleSort
# for(int i=max-1;i>=0;i--) {
# ?for(int j=0;j<=i;j++) {
# if(array[j] > array[j+1]) {
# temp = array[j];
# array[j] = array[j+1];
# array[j+1] = temp;
# }
# }
# }
#
# // Ausgabe
# .
# .
# .
####################
hoffe ich konnte dir helfen!
biba! system -
Hallo!
Ja Bubblesort kenn ich auch aber folgende Funkion sortiert noch schneller, da sie nicht so oft tauscht.
void sortiere(int feld[], int l)
int j, i, min, help;
for (j=0; j<l-1; j++)
{
min = j;
for (i=j+1; i<l; i++)
{
if (feld < feld[min]
min = i;
}
help = feld[j];
feld[j] = feld[min];
feld[min] = help;
}
Bei dieser Funktion wird immer der kleinste Wert gesucht und nach vorne getauscht.
Hoffe geholfen zu haben.
mfg
Lukas
-
ob nun die h?chsten werte nach hinten oder die niedrigsten werte nach vorne sortiert werden, ist doch imho das selbe in gr?n und dementsprechend gleich schnell...
(ergo beides bubblesort nur in unterschiedlichen richtungen)
oder nicht?!
-
Hallo
-> ob nun die h?chsten werte nach hinten oder die niedrigsten
-> werte nach vorne sortiert werden, ist doch imho das selbe
-> in gr?n und dementsprechend gleich schnell...
-> (ergo beides bubblesort nur in unterschiedlichen
-> richtungen)
-> oder nicht?!
Na ja. Es ist die gleiche Gr??enordnung.
Allerdings mus man bedenken das eine "Kopiervorgang" mehr Kosten verursacht als einen Zahl zu ?ndern.
Aber es wird erst gravierent, wenn die Objekte, welche Sortiert werden sollen, sehr gro?e Daten sind.
Denn man k?nnte sich vorstellen, dass das was man Sortirt nicht Zahlen sind sondern andere Sortierbare Objekte.
Jens -
-> Hallo
->
-> Na ja. Es ist die gleiche Gr??enordnung.
-> Allerdings mus man bedenken das eine "Kopiervorgang" mehr
-> Kosten verursacht als einen Zahl zu ?ndern.
-> Aber es wird erst gravierent, wenn die Objekte, welche
-> Sortiert werden sollen, sehr gro?e Daten sind.
-> Denn man k?nnte sich vorstellen, dass das was man Sortirt
-> nicht Zahlen sind sondern andere Sortierbare Objekte.
->
-> Jens
da geb ich dir auch recht mit. bisher war aber nur ein algo gefragt, der zahlen sortiert...
f?r mich stellte sich nur die frage, in wie weit der code nach meinem schneller sein sollte... denn es ist der selbe nur in ne andere richtung!
erm... das mit dem "lass ihn mal selber nachdenken"-edit war wohl im falschen post, oder?!
aber gut... wollte ja nur a bisserl helfen. ^^ *nix-mehr-sag*
biba! system -
-> da geb ich dir auch recht mit. bisher war aber nur ein algo
-> gefragt, der zahlen sortiert...
-> f?r mich stellte sich nur die frage, in wie weit der code
-> nach meinem schneller sein sollte... denn es ist der selbe
-> nur in ne andere richtung!
->
-> biba! system
tut mir leid dir wiedersprechen zu m?ssen, aber das ist nicht der selbe Code nur in die andere Richtung!
Bubblesort tauscht immer, wenn n?tig zwei NEBENEINANDER liegende Zahlen. Also wird meistens mehrmals pro Durchgang getauscht. Meine Funktion tauscht nur sooft wie lang das Array ist.
Bei normal Zahlen ist das sicher ziemlich egal, aber wie gesagt bei gro?en Daten macht das schon einen Unterschied.
mfg
Lukas -
-> Bubblesort tauscht immer, wenn n?tig zwei NEBENEINANDER liegende
-> Zahlen. Also wird meistens mehrmals pro Durchgang getauscht. Meine
-> Funktion tauscht nur sooft wie lang das Array ist.
Soweit stimmt das, aber Du hast dann ein Problem die Zahl richtig einzusortieren, wenn Du ein Array hast, weil Du ja an der richtigen Stelle keinen Platz frei hast!
--> es funktioniert nur mit verketteten Listen, in welchen Du einen Pointer verbiegst, bei arrays wirds eher schwierig!
Gucci -
Hab gerad mal in meinen Unterlagen geschaut und ne schicke erkl?rung zu Quicksort gefunden, ist auch bedeutend schneller wenn das zu sortierende Zahlenfeld gr?sser wird:
funktion feld_aufteilen(links, rechts) {
pivotelement=feld[beliebiger_index_innerhalb_des_bereichs]; (z. B. (links+rechts)/2)
solange (links<rechts) {
solange (feld[links]<pivotelement und links<rechts)
links:=links+1;
solange (feld[rechts]>pivotelement und links<rechts)
rechts:=rechts-1;
vertausche feld[links] mit feld[rechts];
}
ergebniswert links; (oder rechts)
}
Als drittes Verfahren f?llt mir da dann ncoh Bubblesort ein. Gibt aber noch mehr, so als kleinen Trost. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
