Top-Themen

AppleEntwicklungHardwareInternetLinuxMicrosoftMultimediaNetzwerkeOff TopicSicherheitSonstige SystemeVirtualisierungWeiterbildungZusammenarbeit

Aktuelle Themen

Administrator.de FeedbackApache ServerAppleAssemblerAudioAusbildungAuslandBackupBasicBatch & ShellBenchmarksBibliotheken & ToolkitsBlogsCloud-DiensteClusterCMSCPU, RAM, MainboardsCSSC und C++DatenbankenDatenschutzDebianDigitiales FernsehenDNSDrucker und ScannerDSL, VDSLE-BooksE-BusinessE-MailEntwicklungErkennung und -AbwehrExchange ServerFestplatten, SSD, RaidFirewallFlatratesGoogle AndroidGrafikGrafikkarten & MonitoreGroupwareHardwareHosting & HousingHTMLHumor (lol)Hyper-VIconsIDE & EditorenInformationsdiensteInstallationInstant MessagingInternetInternet DomäneniOSISDN & AnaloganschlüsseiTunesJavaJavaScriptKiXtartKVMLAN, WAN, WirelessLinuxLinux DesktopLinux NetzwerkLinux ToolsLinux UserverwaltungLizenzierungMac OS XMicrosoftMicrosoft OfficeMikroTik RouterOSMonitoringMultimediaMultimedia & ZubehörNetzwerkeNetzwerkgrundlagenNetzwerkmanagementNetzwerkprotokolleNotebook & ZubehörNovell NetwareOff TopicOpenOffice, LibreOfficeOutlook & MailPapierkorbPascal und DelphiPeripheriegerätePerlPHPPythonRechtliche FragenRedHat, CentOS, FedoraRouter & RoutingSambaSAN, NAS, DASSchriftartenSchulung & TrainingSEOServerServer-HardwareSicherheitSicherheits-ToolsSicherheitsgrundlagenSolarisSonstige SystemeSoziale NetzwerkeSpeicherkartenStudentenjobs & PraktikumSuche ProjektpartnerSuseSwitche und HubsTipps & TricksTK-Netze & GeräteUbuntuUMTS, EDGE & GPRSUtilitiesVB for ApplicationsVerschlüsselung & ZertifikateVideo & StreamingViren und TrojanerVirtualisierungVisual StudioVmwareVoice over IPWebbrowserWebentwicklungWeiterbildungWindows 7Windows 8Windows 10Windows InstallationWindows MobileWindows NetzwerkWindows ServerWindows SystemdateienWindows ToolsWindows UpdateWindows UserverwaltungWindows VistaWindows XPXenserverXMLZusammenarbeit

Arrays in VBScript sehr schnell sortieren - Mischsort von 1985

Anleitung Entwicklung VB for Applications

Mitglied: Bitsqueezer

Bitsqueezer (Level 1) - Jetzt verbinden

29.11.2007, aktualisiert 10.05.2009, 17710 Aufrufe, 4 Kommentare

Wahrscheinlich schnellster Sortieralgorithmus, schneller als Quicksort, Umsetzung für VBS

Hallo zusammen,

oft steht man vor dem Problem, ein Array sortieren zu müssen. Leider hat Microsoft offenbar bei VBScript an einen schnellen Sortieralgorithmus in Form einer eingebauten Funktion vergessen, daher muß man sich hier selbst behelfen.

Allerdings geht es um eine Scriptsprache, also nicht gerade eine Turbosprache. Daher sollte man bei entsprechend großen Arrays schon genau überlegen, welche Sortierroutine man verwenden möchte. Klassiker sind Bubblesort und Quicksort oder der einfache Dreieckstausch.

Damals, als ich noch meinen C64 mit kleinen Programmen bearbeitete, gab es in der Zeitschrift "64er" mal eine Artikelserie über Sortieralgorithmen und deren Geschwindigkeit (was natürlich auf einem 64-Kilobyte-Computer mit 1 MHz ganz besonders wichtig war). Darin war unter anderem eine damals neue Sortierroutine namens "Mischsort" zu finden.

Meine Tests damals haben immer wieder gezeigt, daß dieser Algorithmus in der Tat turboschnell ist. Seit damals habe ich diese schon oft in andere Programmiersprachen portiert, um sie anderweitig zu verwenden. Leider ist das Original mit GOTOs vollgestopft und leider (oder zum Glück?) hat VBScript kein GOTO. Also habe ich den Algorithmus leicht modifiziert, und nun funktioniert er auch mit VBScript.

Kleiner Wermutstropfen dabei: Er funktioniert nur mit Stringarrays ab Index 1, aber das kann man verschmerzen. Sicher kann man ihn auch auf Arrays mit 0-Basis anpassen, aber er ist auch so schon kompliziert genug...

Funktionsprinzip des Algorithmus besteht darin, die Tabelle in kleinere Tabellenstücke aufzuteilen und jeweils die Teilbereiche für sich zu sortieren, um sie dann wieder ineinanderzumischen und erneut zu sortieren.

Ganz ehrlich habe ich bis heute nicht wirklich verstanden, wie das genau funktioniert, die 64er-Ausgabe beschreibt da zwar noch etwas mehr, aber nicht wirklich ausführlich genug. Für mich war in erster Linie wichtig, DASS sie funktioniert und daß sie SCHNELL funktioniert. Und das leistet sie auch heute noch (wieviele 64er-Programme kann man heute wohl noch einsetzen?... ...)

Nach einigem Herumtüfteln kam dann die unten angehängte VBScript-Version heraus, die sicher für den ein oder anderen brauchbar ist.

Viel Spaß damit und viel Vergnügen beim Herausfinden, wie sie funktioniert.

Christian

01.
Option Explicit 
02.
 
03.
' Mischsort-Algorithmus 
04.
' ===================== 
05.
06.
' Original: Zeitschrift "64er" Ausgabe 9/1985, Seite 126/127 
07.
' Originalautor: Horst Armin Kosog 
08.
09.
' C64-Originalprogramm (optisch aufgebessert): 
10.
'1000 DIM A$(6):A=6 
11.
'1010 A$(1)="TEST" 
12.
'1020 A$(2)="TEST2" 
13.
'1030 A$(3)="NOCHEINS" 
14.
'1040 A$(4)="EINELEMENT" 
15.
'1050 A$(5)="NOCHEINELEMENT" 
16.
'1060 A$(6)="LETZTES ELEMENT" 
17.
'10050 ZF=INT(A/2+.5) 
18.
'10052 DIM TV$(ZF) 
19.
'10059 REM 
20.
'10060 FOR X=2 TO A STEP 2 
21.
'10070    IF A$(X-1)>A$(X) THEN TV$(0)=A$(X-1):A$(X-1)=A$(X):A$(X)=TV$(0) 
22.
'10080 NEXT X 
23.
'10082 IF A<3 THEN 50000 
24.
'10090 LF=1 
25.
'10092 FOR MZ=1 TO INT(LOG(A-1)/LOG(2)) 
26.
'10100    ZF=INT(ZF/2+.5) 
27.
'10101    LF=2*LF 
28.
'10110    FOR FZ=1 TO ZF 
29.
'10112       A1=1+2*LF*(FZ-1) 
30.
'10114       A2=A1+LF 
31.
'10116       E1=A2-1 
32.
'10118       E2=E1+LF 
33.
'10120       IF E2<=A THEN ET=LF:GOTO 10150 
34.
'10130       IF A<A2 THEN 10230 
35.
'10140       E2=A 
36.
'10142       ET=A+1-A2 
37.
'10150       FOR X=1 TO ET:TV$(X)=A$(X+E1):NEXT 
38.
'10160       FOR X=E2 TO A1 STEP -1 
39.
'10170          IF A$(E1)<TV$(ET) THEN 10200 
40.
'10180          A$(X)=A$(E1) 
41.
'10182          E1=E1-1 
42.
'10184          IF E1>=A1 THEN 10220 
43.
'10190          FOR Y=X-1 TO A1 STEP -1 
44.
'10192             A$(Y)=TV$(ET) 
45.
'10194             ET=ET-1 
46.
'10196          NEXT Y 
47.
'10198          GOTO 10210 
48.
'10200          A$(X)=TV$(ET) 
49.
'10202          ET=ET-1 
50.
'10204          IF ET>=1 THEN 10220 
51.
'10210          X=A1 
52.
'10220       NEXT X 
53.
'10230    NEXT FZ 
54.
'10240 NEXT MZ 
55.
'50000 FOR I=1 TO 6:PRINT A$(I):NEXT I 
56.
57.
58.
' ------------------------------------ 
59.
' VBS-Variante 
60.
' ------------------------------------ 
61.
' Autor: Christian Coppes 
62.
' Version: 1.0 
63.
' Letzte Änderung: 29.11.2007 
64.
65.
' Die Sortierroutine sortiert extrem schnell auch große Stringmengen. 
66.
' Kleiner Wermutstropfen: Das Stringarray muß mit Index 1 beginnen. 
67.
 
68.
 
69.
Const Anz=10 
70.
 
71.
Dim I,strSort(), strAnzeige, strElement 
72.
ReDim strSort(Anz) 
73.
 
74.
strSort(1)="Test" 
75.
strSort(2)="Test2" 
76.
strSort(3)="Nocheins" 
77.
strSort(4)="EinElement" 
78.
strSort(5)="Noch ein Element" 
79.
strSort(6)="Letztes Element" 
80.
strSort(7)="Doch nicht1" 
81.
strSort(8)="2Doch nicht" 
82.
strSort(9)="3Nicht doch" 
83.
strSort(10)="Mal sehen, was geht" 
84.
 
85.
'strSort(1)="6" 
86.
'strSort(2)="4" 
87.
'strSort(3)="1" 
88.
'strSort(4)="3" 
89.
'strSort(5)="9" 
90.
'strSort(6)="5" 
91.
'strSort(7)="8" 
92.
'strSort(8)="7" 
93.
'strSort(9)="0" 
94.
'strSort(10)="2" 
95.
 
96.
For I = 1 To Anz 
97.
	strAnzeige=strAnzeige+strSort(I)+vbCr 
98.
Next 
99.
MsgBox strAnzeige 
100.
 
101.
Mischsort strSort 
102.
 
103.
strAnzeige="" 
104.
For I = 1 To Anz 
105.
	strAnzeige=strAnzeige+strSort(I)+vbCr 
106.
Next 
107.
MsgBox strAnzeige 
108.
 
109.
WScript.Quit 
110.
 
111.
Function Mischsort(strArr) 
112.
	Dim A,intTeilfeldAnzahl,X, intLaufendeFeldlaenge, intMischzaehler, intTeilfeldZaehler 
113.
	Dim A1, A2, E1, E2, ET, Y 
114.
	Dim ZF, LF, MZ, FZ, NextX 
115.
	Dim strTempArr() 
116.
 
117.
	A=UBound(strArr) 
118.
 
119.
	ZF=Int(A/2+0.5) 
120.
	ReDim strTempArr(ZF) 
121.
 
122.
	For X=2 To A Step 2 
123.
		If strArr(X-1)>strArr(X) Then 
124.
			strTempArr(0)=strArr(X-1) 
125.
			strArr(X-1)=strArr(X) 
126.
			strArr(X)=strTempArr(0) 
127.
		End If 
128.
	Next 'X 
129.
	If A<3 Then WScript.Quit 
130.
	LF=1 
131.
	For MZ=1 To Int(Log(A-1)/Log(2)) 
132.
		ZF=Int(ZF/2+0.5) 
133.
		LF=2*LF 
134.
		For FZ=1 To ZF 
135.
			A1=1+2*LF*(FZ-1) 
136.
			A2=A1+LF 
137.
			E1=A2-1 
138.
			E2=E1+LF 
139.
			If E2<=A Then 
140.
				ET=LF 
141.
			Else 
142.
				If Not(A<A2) Then 
143.
					E2=A 
144.
					ET=A+1-A2 
145.
				End If 
146.
			End If 
147.
 
148.
			If (E2<=A) Or (Not(A<A2)) Then 
149.
				For X=1 To ET 
150.
					strTempArr(X)=strArr(X+E1) 
151.
				Next 
152.
				For X=E2 To A1 Step -1 
153.
					NextX=0 
154.
					If strArr(E1)<strTempArr(ET) Then 
155.
						NextX=1 ' Flag setzen, um "GOTO 10220" zu emulieren 
156.
						strArr(X)=strTempArr(ET) 
157.
						ET=ET-1 
158.
						If Not(ET>=1) Then 
159.
							X=A1 
160.
						End If 
161.
					End If 
162.
 
163.
					If NextX=0 Then 
164.
						strArr(X)=strArr(E1) 
165.
						E1=E1-1 
166.
						If Not(E1>=A1) Then 
167.
							For Y=X-1 To A1 Step -1 
168.
								strArr(Y)=strTempArr(ET) 
169.
								ET=ET-1 
170.
							Next 'Y 
171.
							X=A1 
172.
						End If 
173.
					End If 
174.
				Next 'X 
175.
			End If '(E2<=A) Or (Not(A<A2)) 
176.
		Next 'FZ 
177.
	Next 'MZ 
178.
End Function
Mitglied: melisa88
14.08.2008 um 18:26 Uhr
Also kannst du vielleicht nur in kleinen code schreiben?
z.B schreibe ich in einem textdatei "bsapuync" und er soll es jetzt schritt für schritt sotieren (also von a bis z).
Wie kann ich das in c++ schreiben?
Bitte warten ..
Mitglied: Bitsqueezer
15.08.2008 um 20:46 Uhr
Hallo Melisa,

bei C++ kann ich Dir nicht helfen, da ich mit C noch nicht programmiert habe.

Vielleicht ist das hier ja das richtige für Dich:

http://www.c-plusplus.de/forum/viewtopic-var-t-is-39154.html

Du mußt lediglich vorher Deine Textzeile in einzelne Buchstaben als einzelne Strings eines Stringarrays aufteilen.

Oder, in diesem speziellen Fall, bei dem es nur um einzelne Buchstaben geht: Den String als ganzes nehmen und dann mit einer Schleife immer den ersten gelesenen Buchstaben mit dem darauffolgenden vergleichen und dann austauschen, wenn der nächste Buchstabe kleiner ist als der vorhergehende. Wenn ein Tausch stattgefunden hat, das ganze von vorn beginnen, so lange, bis kein Tausch mehr stattgefunden hat (kann man z.B. über eine Flag-Variable abfragen, die man auf true setzt, wenn ein Tausch stattgefunden hat).
Das ist ein sehr primitiver Sortieralgorithmus, da es aber nur um eine Buchstabenreihe geht, sollte das wohl sehr schnell gehen.

Wenn man eine SQL-Datenbank zur Verfügung hat, kann man auch anders sortieren: Für jeden String einen Eintrag in einer Temporärtabelle machen und dann per SELECT mit ORDER die Sortierung den SQL-Server erledigen lassen und das Ergebnis gemütlich auslesen.

Gruß

Christian
Bitte warten ..
Mitglied: melisa88
15.08.2008 um 21:44 Uhr
Also in SQL habe ich schon bisschen Ahnung. Und der Link ist eigentlich die richtige den ich gesucht habe
Ich programmiere nämlich acuh ungefähr so;)

Danke für dein Hilfe

schöne Grüße

Melisa
Bitte warten ..
Mitglied: Bitsqueezer
17.02.2013 um 18:28 Uhr
Für alle Interessierte:

Leider war mir die Verbindung zum Erläuterungsartikel des Originalautors damals verlorengegangen, später nicht mehr daran gedacht, hier ist der Link, auf dem der Autor seinen Algorithmus erläutert und sogar eine verbesserte, noch schnellere Version vorstellt:

http://www.administrator.de/forum/sortieralgorithmus-mischsort-105141.h ...
Bitte warten ..
Neuester Wissensbeitrag
Windows 10

Powershell 5 BSOD

(1)

Tipp von agowa338 zum Thema Windows 10 ...

Ähnliche Inhalte
Entwicklung
gelöst Get ip from external txt file and use in vbscript (5)

Frage von thankusomuch zum Thema Entwicklung ...

Batch & Shell
gelöst Powershell - Dateien aus verschiedenen Arrays - Attribute vergleichen (5)

Frage von Giffas zum Thema Batch & Shell ...

Webbrowser
Mozilla: Firefox 50 startet schnell und bringt Emoji (3)

Link von Frank zum Thema Webbrowser ...

Heiß diskutierte Inhalte
LAN, WAN, Wireless
gelöst Server erkennt Client nicht wenn er ausserhalb des DHCP Pools liegt (28)

Frage von Mar-west zum Thema LAN, WAN, Wireless ...

Outlook & Mail
Outlook 2010 findet ost datei nicht (18)

Frage von Floh21 zum Thema Outlook & Mail ...

Windows Server
Server 2008R2 startet nicht mehr (Bad Patch 0xa) (18)

Frage von Haures zum Thema Windows Server ...