Visual Basic - Technik, FAQ, Tricks, Beispiele

Home / Daten / Array / Mix

Arrayinhalte schnell mischen

Historie
15.05.2004Unsortierung verbessert (nach Hinweis von Donald Lessau)
13.11.2001Erste Version

Einleitung

Manchmal ist es notwendig, eine gegebene Menge von Daten zufällig zu sortieren. Mögliche Anwendungen dafür sind z.B. "Ziehung von Losen", "Turnierplanung", Kartenspiele, etc. pp.

Im Allgemeinen soll eine gegebene Wertemenge A in eine Wertemenge B überführt werden, die zwar die gleichen Elemente enthält, aber in einer zufälligen Reihenfolge. Oft sind diese Daten in Arrays abgelegt.

Für die Realisierung sind verschiedene Verfahren denkbar, welche man auch immer wieder veröffentlicht sieht:

Da diese bekannten Verfahren die beschriebenen Performance-Nachteile haben, werde ich im Folgenden Schritt für Schritt einen Algorithmus vorstellen, welcher weder Probleme mit dem Freien-Platz-finden hat, noch einen Objekt-Overhead erzeugt.

Ergänzend zu diesem Artikel empfehle ich übrigens auch die Lektüre von "König Zufall" und "Oft gestellte Fragen über Arrays / Wie kann eine Funktion ein Array zurückgeben?".

Beispiele

Ziehung der Lottozahlen (6 aus 49):

Dim Kugeln As Variant 'As Long() 'VB6

Kugeln = RandomLongArray(49, , 6)
For i = 1 To 6
  MsgBox Kugeln(i)
Next i

Ein Array voller Zitate zufällig durchlaufen:

Dim Zitate() As String
Dim Index As Variant 'As Long() 'VB6
Dim i As Long

LadeAlleZitate Zitate
Index = RandomIndex(Zitate)
For i = LBound(Index) To UBound(Index)
  MsgBox Zitat(Index(i))
Next i

Ein gegebenes String-Array klonen und durcheinander-wirbeln:

Dim sGeordnet() As String
Dim sGemischt() As String

FülleStringArray sGeordnet
MixArrayStr sGeordnet, sGemischt
BenutzeStringArray sGemischt

Code / Quelltext

RandomLongArray

Die Grundlage des Array-Mischens wird eine Folge von Ganzzahlen sein, welche mit der folgenden Funktion erzeugt werden können. Man beachte, dass in VB6 statt As Variant besser As Long() zu benutzen ist (s.a. "Wie kann eine Funktion ein Array zurückgeben?"):

' ©2004 by Jost Schwider, http://vb-tec.de/
Public Function RandomLongArray( _
    ByVal Max As Long, _
    Optional ByVal Min As Long = 1, _
    Optional ByVal Count As Long = 0 _
  ) As Variant 'As Long() 'VB6

  Dim Range As Long
  Dim Longs() As Long
  Dim i As Long
  Dim j As Long
  Dim Item As Long
  
  'Array initialisieren:
  ReDim Longs(Min To Max)
  For i = Min To Max
    Longs(i) = i
  Next i
  
  'Array mischen:
  Range = Max - Min + 1
  For i = Min To Max - 1
    j = Int(Rnd * Range) + i
    Item = Longs(j)
    Longs(j) = Longs(i)
    Longs(i) = Item
    Range = Range - 1
  Next i
  
  'Ergebnis zurückgeben:
  If Count > 0 Then
    ReDim Preserve Longs(Min To Min + Count - 1)
  End If
  RandomLongArray = Longs

End Function

Wie arbeitet nun der Algorithmus? Man kann es sich wie ein Kartenstapel vorstellen, wo man zuerst die erste Karte mit einer zufälligen anderen tauscht, dann die zweite, dritte, usw.! Da nur "Karten" (hier: Datentyp Long) getauscht werden, muss niemals ein freier Platz gesucht werden. Da jede Karte mindestens einmal bewegt wird, ist die Qualität der "Un-Sortierung"/Mischung bei diesem Verfahren sehr gut.

RandomIndex

Mit Hilfe der gerade vorgestellten RandomLongArray-Funktion kann sehr einfach eine zufällige Reihenfolge aller möglichen Indexe eines Arrays generiert werden. Es müssen dafür nur alle Zahlen zwischen LBound und UBound berücksichtigt werden:

Public Function RandomIndex( _
    ByRef anArray As Variant _
  ) As Variant 'As Long() 'VB6

  RandomIndex = RandomLongArray( _
      UBound(anArray), _
      LBound(anArray))

End Function
MixArrayStr

Möchte man nun ein vorhandenes String-Array un-sortieren, kann man dies mit Hilfe der zufälligen Indexe folgendermaßen realisieren:

Public Sub MixArrayStr( _
    ByRef sInput() As String, _
    ByRef sOutput() As String)

  Dim Index As Variant 'As Long() 'VB6
  Dim i As Long

  Index = RandomIndex(sInput)
  ReDim sOutput(LBound(sInput) To UBound(sInput))
  For i = LBound(sInput) To UBound(sInput)
    sOutput(i) = sInput(Index(i))
  Next i

End Sub

Man beachte, dass bei diesem Verfahren jeder String nur genau einmal bewegt wird. Es muss niemals geprüft werden, welcher Platz überhaupt frei ist, und eine bremsende Objekt-Struktur wird auch nicht aufgebaut.
Daher ist dieses Verfahren allen anderen deutlich überlegen (bis zu Faktor 100)!

© Jost Schwider, 13.11.2001-15.05.2004 - http://vb-tec.de/arrmix.htm