Frage deutsch
~~~~~~~~~~~~~~
Wie kann ich ein paar Texte sortieren, die auch Umlaute enthalten können?
 

Question English
~~~~~~~~~~~~~~
How to sort some pieces of text which may contain "umlauted" characters?
 

Antwort 1
~~~~~~~~
[ von Peter Vollenweider ( peter.vollenweider*gmx.ch ) im QB-Forum, 13.5.02 ]
.
Die Online-Hilfe von QuickBasic 4.5 enthält für den SWAP-Befehl unter <Beispiele> ein einfaches Beispiel für die Sortierung von Texten. Dieser Programmvorschlag versagt jedoch, wenn Umlaute in den Texten vorkommem oder wenn Groß- un d Kleinbuchstaben gemischt vorkommen.
 
Das folgende kleine Programm fordert den Anwender zunächst zur Eingabe einiger Wörter auf, die auch Umlaute und "ß" enthalten können und trägt diese in ein Feld "woerter" und gleichzeitig in ein Hilfsfeld "hilfsarray1" ein.
 
Das Hilfsfeld wird benötigt, um die Umlaute und das "ß" zu beherrschen. Dort werden die Umlaute durch die entsprechenden "umlautlosen" Buchstaben ersetzt, z.B. "ä" durch "a".
 
Das Hilfsfeld wird jetzt mit Hilfe des normalen "Bubble Sort" Algorithmus sortiert. Mehr Informationen zu Bubble Sort findest Du in den Beiträgen "Wie kann ich ein paar Zahlen sortieren" und "was gibt es für Sortieralgorithmen".
 
Die Indices der sortierten Feldelemente werden in einem zweiten Hilfsfeld "hilfsarray2" mitgeführt, anhand derer sich dann die Textstücke im ursprünglichen Feld "woerter" in sortierter Reihenfolge angezeigen lassen.
Hinweis: Die in dem Beispielprogramm verwendeten Umlaute werden natürlich erst dann richtig dargestellt, wenn man sie in eine DOS-Anwendung einfügt, z.B. in die QBasic-Entwicklungsumgebung. Die Ursache liegt in dem unter Windows verwendeten ANSI-Zeichensatz, der bei den Sonderzeichen vom DOS-ASCII-Zeichensatz abweicht.
 
'******************************************************************************
' Sort_TXT.bas = Sortieren von Texten mit korrekter Behandlung der Umlaute
' ============
' Die ASCII-odes der Textzeichen sind von Haus aus schon in der richtigen
' alfabetischen Reihenfolge angeordnet. Dadurch ist das Sortieren von
' englischen Texten fast ein Kinderspiel. Bei deutschen Umlauten und "Eszet"
' liegen die Zeichencodes jedoch ganz ausserhalb der Reihenfolge. Das
' vorliegende QBasic-Programm wandelt sie daher vor dem Sortieren zunaechst
' in die entsprechenden Nicht-Umlaut-Buchstaben um; aus a-Umlaut wird z.B. a.
'
' Wird dieses Programm mit einer Windows-Anwendung betrachtet, so ist zu
' beachten, dass die Umlaute im Windows-ANSI-Code anders als im DOS-ASCII-
' Code angezeigt werden.
'
' (c) Peter Vollenweider (peter.vollenweider*gmx.ch), 13.5.02
' Kommentare von Thomas Antoni, 13.5.02 - 26.2.04
'******************************************************************************
'$DYNAMIC
DEFINT A-Z
CLS
max = 1000
DIM woerter(max) AS STRING
DIM hilfsarray1(max) AS STRING
DIM hilfsarray2(max) AS INTEGER
'
DO
wort = wort + 1
INPUT "Gib das naechste Wort ein, leere Eingabe zum Beenden: ", woerter(wort)
LOOP UNTIL woerter(wort) = ""
max = wort - 1
FOR ersetzen = 1 TO max
hilfsarray1(ersetzen) = woerter(ersetzen)
WHILE INSTR(hilfsarray1(ersetzen), "„") 'Kleines A-Umlaut
MID$(hilfsarray1(ersetzen), INSTR(hilfsarray1(ersetzen), "„"), 1) = "a"
WEND
WHILE INSTR(hilfsarray1(ersetzen), """) 'Kleines O-Umlaut
MID$(hilfsarray1(ersetzen), INSTR(hilfsarray1(ersetzen), """), 1) = "o"
WEND
WHILE INSTR(hilfsarray1(ersetzen), "�") 'Kleines U-Umlaut
MID$(hilfsarray1(ersetzen), INSTR(hilfsarray1(ersetzen), "�"), 1) = "u"
WEND
WHILE INSTR(hilfsarray1(ersetzen), "á") 'EsZet
MID$(hilfsarray1(ersetzen), INSTR(hilfsarray1(ersetzen), "á"), 1) = "s"
WEND
WHILE INSTR(hilfsarray1(ersetzen), "Ž") 'Grosses A-Umlaut
MID$(hilfsarray1(ersetzen), INSTR(hilfsarray1(ersetzen), "Ž"), 1) = "A"
WEND
WHILE INSTR(hilfsarray1(ersetzen), "™") 'Grosses O-Umlaut
MID$(hilfsarray1(ersetzen), INSTR(hilfsarray1(ersetzen), "™"), 1) = "O"
WEND
WHILE INSTR(hilfsarray1(ersetzen), "š") 'Grosses U-Umlaut
MID$(hilfsarray1(ersetzen), INSTR(hilfsarray1(ersetzen), "š"), 1) = "U"
WEND
hilfsarray1(ersetzen) = UCASE$(hilfsarray1(ersetzen))
'Gross fuer keine Unterscheidung
hilfsarray2(ersetzen) = ersetzen
NEXT
'Sortieren, nur Hilfsarrays vertauschen!
FOR sort1 = 1 TO max
FOR sort2 = sort1 TO max
IF hilfsarray1(sort1) > hilfsarray1(sort2) THEN
SWAP hilfsarray1(sort1), hilfsarray1(sort2)
SWAP hilfsarray2(sort1), hilfsarray2(sort2)
END IF
NEXT sort2, sort1 'Trick f�r schnellere FOR-Schleife
'
PRINT
PRINT "Die sortierten W"rter lauten:"
FOR anzeigen = 1 TO max
PRINT woerter(hilfsarray2(anzeigen))
NEXT
SLEEP
END
 
Das obige Programm steht im Verzeichnis Progs\ zur Verfügung sowie online unter www.antonis.de/faq/progs/sort_txt.bas .
 
 
Answer 2
~~~~~~~~~~~~~
 
*** Recursive QuickSort mehod
The following program demonstrates the recursive QuickSort method by sorting 6 text words:
 
'*************************************************************************
' SORTQUIK.BAS = Recursive QuickSort example
' ============ Demonstration des rekursiven Sortierverfahrens QuickSort
'
' English-language Description
' -----------------------------
' This (Q(uick)Basic programm sorts somw text words using the
' recursive QuickSort method. It can be easily modified for sorting
' numerical values.
'
' Deutsche Beschreibung
' -----------------------------
' Dieses Q(uick)Basic-Programm sortiert ein paar von Anwender
' eingegebene Worte mit Hilfe des rekursiven QuickSort-Verfahrens
' Das Programm kann leicht so abgewandelt werden, dass es
' Zahlenwerte statt Texte sortiert.
'**************************************************************************
'
DECLARE SUB QuickSortSTR (Array() AS STRING, Low%, High%)
DIM word$(5)
CLS
PRINT "You will be pompted to type in 6 text words"
PRINT
FOR i% = 0 TO 5
INPUT "Type a Word"; word$(i%)
NEXT
CALL QuickSortSTR(word$(), 0, 5)
PRINT
PRINT "The words in sorted order:"
FOR i% = 0 TO 5
PRINT word$(i%)
NEXT
SLEEP
DEFINT A-Z
'
SUB QuickSortSTR (Array() AS STRING, Low, High)
' /^\ /^\
' | |
' Change these to any BASIC data type for this routine to
' handle other types of data arrays other than strings.
'
'============================== QuickSortXXX ================================
' QuickSortXXX works by picking a random "pivot" element in Array(), then
' moving every element that is bigger to one side of the pivot, and every
' element that is smaller to the other side. QuickSortXXX is then called
' recursively with the two subdivisions created by the pivot. Once the
' number of elements in a subdivision reaches two, the recursive calls end
' and the array is sorted.
'===========================================================================
'
' Microsoft's source code modified as needed
'
STATIC BeenHere
IF NOT BeenHere THEN
Low = LBOUND(Array)
High = UBOUND(Array)
BeenHere = -1
END IF
DIM Partition AS STRING ' Change STRING to any BASIC data type
' for this QuickSort routine to work with
' things other than strings.
IF Low < High THEN
' Only two elements in this subdivision; swap them if they are out
' of order, then end recursive calls:
IF High - Low = 1 THEN ' we have reached the terminating condition!
IF Array(Low) > Array(High) THEN
SWAP Low, High
BeenHere = 0
END IF
ELSE
' Pick a pivot element at random, then move it to the end:
RandIndex = INT(RND * (High - Low + 1)) + Low
SWAP Array(High), Array(RandIndex)
Partition = Array(High)
DO
' Move in from both sides towards the pivot element:
i = Low: J = High
DO WHILE (i < J) AND (Array(i) <= Partition)
i = i + 1
LOOP
DO WHILE (J > i) AND (Array(J) >= Partition)
J = J - 1
LOOP
' If we haven't reached the pivot element, it means that two
' elements on either side are out of order, so swap them:
IF i < J THEN
SWAP Array(i), Array(J)
END IF
LOOP WHILE i < J
' Move the pivot element back to its proper place in the array:
SWAP Array(i), Array(High)
' Recursively call the QuickSortSTR procedure (pass the smaller
' subdivision first to use less stack space):
IF (i - Low) < (High - i) THEN
QuickSortSTR Array(), Low, i - 1
QuickSortSTR Array(), i + 1, High
ELSE
QuickSortSTR Array(), i + 1, High
QuickSortSTR Array(), Low, i - 1
END IF
END IF
END IF
END SUB
 
Das obige Programm steht im Verzeichnis Progs\ zur Verfügung sowie online unter www.antonis.de/faq/progs/sortquik.bas .
 
 
*** Non-recursive (iterative) QuickSort method
 

Question:
Is there a way to implement a QuickSort SUB without using recursion?
 

Answer:
Yes, indeed there is. Cornel Huth implemented an iterative quicksort algorithm, which I then tweaked a bit. It is actually a bit faster than the other, and doesn't use too much of the stack. It accomplishes this by using an array to simulate a stack. The modified version follows:
 
 
'****************************************************************
' SORTQIK2.BAS = Iterative QuickSort example
' ============ Demonstration des Sortierverfahrens QuickSort
' (nicht-rekursive Variante)
'
' English-language Description
' ------------------------------
' This (Q(uick)Basic programm sorts some text words using the
' iterative (non-recursive) QuickSort method. It can be easily
' modified for sorting numerical values instaed of strings.
'
' Deutsche Beschreibung
' -----------------------
' Dieses Q(uick)Basic-Programm sortiert ein paar von Anwender
' eingegebene Worte mit Hilfe des iterativen (nicht-rekursiven)
' QuickSort-Verfahrens Das Programm kann leicht so abgewandelt
' werden, dass es Zahlenwerte statt Texte sortiert.
'
' (c) Cornel Huth
'*****************************************************************
'
DECLARE SUB subHuthSortSTR (Array() AS STRING)
'
TYPE StackType
low AS INTEGER
hi AS INTEGER
END TYPE
'
DIM word$(5)
CLS
PRINT "You will be pompted to type in 6 text words"
PRINT
FOR i% = 0 TO 5
INPUT "Type a Word"; word$(i%)
NEXT
CALL subHuthSortSTR(word$())
PRINT
PRINT "The words in sorted order:"
FOR i% = 0 TO 5
PRINT word$(i%)
NEXT
SLEEP
'
SUB subHuthSortSTR (Array() AS STRING)
' ^ TWEAK THESE ^
' | FOR OTHER TYPES |
' `--+--------------'
' V
'
'
DIM aStack(1 TO 128) AS StackType
DIM compare AS STRING
StackPtr = 1
aStack(StackPtr).low = LBOUND(Array)
aStack(StackPtr).hi = UBOUND(Array)
StackPtr = StackPtr + 1
DO
StackPtr = StackPtr - 1
low = aStack(StackPtr).low
hi = aStack(StackPtr).hi
DO
i = low
j = hi
mid = (low + hi) \ 2
compare = Array(mid)
DO
DO WHILE Array(i) < compare
i = i + 1
LOOP
DO WHILE Array(j) > compare
j = j - 1
LOOP
IF i <= j THEN
SWAP Array(i), Array(j)
i = i + 1
j = j - 1
END IF
LOOP WHILE i <= j
IF j - low < hi - i THEN
IF i < hi THEN
aStack(StackPtr).low = i
aStack(StackPtr).hi = hi
StackPtr = StackPtr + 1
END IF
hi = j
ELSE
IF low < j THEN
aStack(StackPtr).low = low
aStack(StackPtr).hi = j
StackPtr = StackPtr + 1
END IF
low = i
END IF
LOOP WHILE low < hi
'IF StackPtr > maxsp THEN maxsp = StackPtr
LOOP WHILE StackPtr <> 1
END SUB
 
Das obige Programm steht im Verzeichnis Progs\ zur Verfügung sowie online unter www.antonis.de/faq/progs/sortqik2.bas .
 
 
*** ShellSort method
Another well-known sort algorithm is ShellSort. The following programm demonstrates how it works:
 
'*************************************************************************
' SORTSHEL.BAS = ShellSort example
' ============ Demonstration des Sortierverfahrens ShellSort
'
' English-language Description
' -----------------------------
' This (Q(uick)Basic programm sorts some text words using the
' ShellSort method. It can be easily modified for sorting
' numerical values.
'
' Deutsche Beschreibung
' -----------------------------
' Dieses Q(uick)Basic-Programm sortiert ein paar von Anwender
' eingegebene Worte mit Hilfe des ShellSort-Verfahrens
' Das Programm kann leicht so abgewandelt werden, dass es
' Zahlenwerte statt Texte sortiert.
'
' (c) Released to Public Domain, 1993, by R.A. Coates
'**************************************************************************
'
DECLARE SUB ShellSort (col0%, array$())
'
DIM word$(5) 'Text array to be sorted
col10% = 5 'Number of array elements - 1
CLS
PRINT "You will be pompted to type in 6 text words"
PRINT
FOR i% = 0 TO 5
INPUT "Type a Word"; word$(i%)
NEXT
CALL ShellSort(col10%, word$())
PRINT
PRINT "The words in sorted order:"
FOR i% = 0 TO 5
PRINT word$(i%)
NEXT
SLEEP
'
'
'---------------------------------------------------------------------------
' Procedure uses the Shell-Metzger algorithm for sorting an array of string
' variables. Adapted from an article by Donald Shell and disassembled IBM
' 360 machine language. This sorting algorithm is extremely efficient for
' sorting small and medium sized arrays.
'
' PARAMETERS: col0% = number of elements - 1 in the string array array$()
' array$() = string variable array to be sorted.
' RETURNS: array$() = sorted string variable array
'----------------------------------------------------------------------------
'
SUB ShellSort (col0%, array$())
col1% = col0%
'
WHILE col1% <> 0
col1% = col1% \ 2
col2% = col0% - col1%
'
FOR count% = 1 TO col2%
col3% = count%
sort1:
col4% = col3% + col1%
IF array$(col3%) <= array$(col4%) THEN
GOTO sort2
ELSE
SWAP array$(col3%), array$(col4%)
col3% = col3% - col1%
END IF
'
IF col3% > 0 THEN
GOTO sort1
END IF
sort2:
NEXT count%
WEND
END SUB 'ShellSort()
 
Das obige Programm steht im Verzeichnis Progs\ zur Verfügung sowie online unter www.antonis.de/faq/progs/sortshel.bas .

[ The QBasic-MonsterFAQ --- Start Page: www.antonis.de/faq ]