Kleine Sortierfunktion für Zahlen Arrays

Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Neue Antwort erstellen

Trust

Betreff: Kleine Sortierfunktion für Zahlen Arrays

BeitragSo, Mai 20, 2012 18:16
Antworten mit Zitat
Benutzer-Profile anzeigen
Die Funktion:
BlitzMax: [AUSKLAPPEN]

Function sort(array:Int[] Var)
Local tmp:Int = 0
Local swap:Int = 0
Local depth:Int = 0
Repeat
swap = 0
For Local i:Int = 0 To array.length - 2 - depth
If array[i] > array[i + 1]
tmp = array[i]
array[i] = array[i + 1]
array[i + 1] = tmp
swap = 1
End If
Next
depth = depth + 1
Until swap = 0
End Function



Anwendungsbeispiel:

BlitzMax: [AUSKLAPPEN]
SuperStrict

Local arrayLength:Int = 1000

Local value:Int[arrayLength]

Print "Unsortiert:"
For Local i:Int = 0 To arrayLength - 1
value[i] = Rand(20)
Print value[i]
Next

Local ms:Int = MilliSecs()
sort(value)
Local ms2:Int = MilliSecs()


Print "Sortiert:"
For Local i:Int = 0 To arrayLength - 1
Print value[i]
Next
Print ""
Print "Sortierdauer: " + (ms2 - ms) + " ms"


Will man andere Datentypen sortieren als "Int"

einfach den Funktionskopf der Sortierfuntion abändern:
zB. anstatt "int"
BlitzMax: [AUSKLAPPEN]
sort(array:Int[] Var

"float"
BlitzMax: [AUSKLAPPEN]
sort(array:Float[] Var)
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.
  • Zuletzt bearbeitet von Trust am So, Mai 20, 2012 19:42, insgesamt 9-mal bearbeitet

ZEVS

BeitragSo, Mai 20, 2012 18:19
Antworten mit Zitat
Benutzer-Profile anzeigen
BlitzMax unterstützt auch die einfache Funktion array.Sort für jedes Array.

BladeRunner

Moderator

BeitragSo, Mai 20, 2012 18:19
Antworten mit Zitat
Benutzer-Profile anzeigen
mach ienfach mal array.sort() bei einem Array deiner Wahl, trust Wink
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI

Stolzer Gewinner des BAC#48, #52 & #92

Xeres

Moderator

BeitragSo, Mai 20, 2012 18:28
Antworten mit Zitat
Benutzer-Profile anzeigen
Für das Codearchiv sollte der Code mindestens Strict sein.
Ob rekursiv viele Arrays zu bearbeiten auf lange Sicht in Ordnung geht...?
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Trust

BeitragSo, Mai 20, 2012 18:29
Antworten mit Zitat
Benutzer-Profile anzeigen
Ok, hab erst garnicht geschaut ob es sowas schon gibt.
Danke für den Hinweiß Razz


[Edit]

@Xeres: habs angepasst.

@Xeres: Hab den Code abgeändert, aber glaube du hast recht, 1000 Einträge zu sortieren dauert bei mir immernoch ca. 3 sek.
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.
  • Zuletzt bearbeitet von Trust am So, Mai 20, 2012 19:02, insgesamt einmal bearbeitet

ChaosCoder

BeitragSo, Mai 20, 2012 18:52
Antworten mit Zitat
Benutzer-Profile anzeigen
Ist aber auch nur ein schlecht optimierter Bubblesort-Algorithmus.

Beispiel: Größte Zahl steht am Anfang, Rest ist sortiert.

Dein Algorithmus:
Tauscht die ersten beiden -> Rekursion
Tauscht das 2. und 3. Element -> Rekursion
Tauscht das 3. und 4. Element -> Rekursion
...
Und am Ende läuft noch jede Rekursionstiefe einmal über das komplette Array, wobei es n Rekursionstiefen gibt -> Anzahl Vergleiche: n^2

Normaler Bubble-Sort würde hier n+(n-1) Vergleiche benötigen, also < 2n
Projekte: Geolaria | aNemy
Webseite: chaosspace.de

Trust

BeitragSo, Mai 20, 2012 19:07
Antworten mit Zitat
Benutzer-Profile anzeigen
Ok, der Code ist miserabel!

[Edit]
Damit der Beitrag einen Sinn hat, habe ich nun ein Bubblesort draus gemacht.
( Siehe ersten post )
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

ChaosCoder

BeitragSo, Mai 20, 2012 19:30
Antworten mit Zitat
Benutzer-Profile anzeigen
Noch Optimierungsvorschlag (nur falls du Lust hast, ich brauch den Code nicht^^):

Im Worstcase (absteigend sortiertes Array) brauchst du nun n*n Vergleiche, weil du immer wieder bis zum letzten Element durchgehst.

Nach einem Durchgang steht die größte Zahl aber bereits an letzter Stelle, beim zweiten Durchgang die zweitgrößte an vorletzter, usw.

Somit würdest du (nur) n+(n-1)+(n-2)+...+(n-n)=n*(n+1)/2 Vergleiche benötigen. Ist zwar asymptotisch das gleiche, aber optimiert ist optimiert. Smile
Projekte: Geolaria | aNemy
Webseite: chaosspace.de

Trust

BeitragSo, Mai 20, 2012 19:40
Antworten mit Zitat
Benutzer-Profile anzeigen
@ChaosCoder:
Soviel wollte ich mich garnicht damit beschäftigen ^^
Habs angepasst ( siehe ersten post )
Danke Smile
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group