How to Randomize / Shuffle (Generic) Collections and Lists – Implementing UnSort in Delphi

The second law of thermodynamics, in short version and when read by a programmer, states that “any collection of objects tends not to be sorted” 🙂

We developers, we have a tendency of organizing objects into lists, collections, queues, stacks …

Since you’ll be using the for loop to iterate over elements – why not sort the elements first. What’s more, a sorted list is easier (read: faster) to be searched upon.

For example, for a list of TDeveloper objects you would need developers (instances of TDeveloper) sorted, in the list, by their name, knowledge or salary – or any other property.

That’s boring! I want my lists randomized!

What if you need to randomize the position of elements in a list? Is there an “UnSort” method you can use? Is there a “Randomize” method in TStrings (or similar)? No.

Imagine a deck of cards. Yes, you see it now. How funny the game would be if you would always know what cards are on top of the deck.

Unsorting by sorting 🙂

So how do you unsort a list? Well, by sorting in random order. Here goes:

var
  //TMyObject = class(TObject)
  objects : TObjectList<TMyObject>;
begin
  objects := TObjectList<TMyObject>.Create(true); //uses System.Generics.Collections
  try
    //"missing" code!
    //add instances of TMyObjects to the "objects" list...

    //randomize / UNSORT / SHUFFLE positions
    objects.Sort(TComparer<TMyObject>.Construct(
      function(const L,R : TMyObject) : integer
      begin
        //returns -1, 0 or 1
        result := -1 + Random(3);
      end
    ));

    //"missing" code!
    //do something with randomized items
  finally
    objects.Free;
  end;
end;

That’s it. Call the Sort method by specifying a comparer that would randomly set if an element is less than or greater than the compared element.

This looks lovely, but if you have different lists of different objects that you want to have shuffled, you might want to have a more simple way to call the “unsort” code.

TGenericListHelper

Here’s a sample generic list helper class exposing class methods. There are actually 2 unsort/shuffle methods – so pick the one you prefer better 😉

  TGenericListHelper = class
    class procedure Shuffle<T>(const listOfT : TList<T>);
    class procedure UnSort<T>(const listOfT : TList<T>);
  end;

And the implementation part:

class procedure TGenericListHelper.Shuffle<T>(const listOfT: TList<T>);
//randomize positions by swapping the position of two elements randomly
var
  randomIndex: integer;
  cnt: integer;
begin
  Randomize;

  for cnt := 0 to -1 + listOfT.Count do
  begin
    randomIndex := Random(-cnt + listOfT.Count) ;
    listOfT.Exchange(cnt, cnt + randomIndex) ;
  end;
end;

class procedure TGenericListHelper.UnSort<T>(const listOfT: TList<T>);
//randomize positions by unsorting
begin
  Randomize;

  listOfT.Sort(TComparer<T>.Construct(
    function(const Left, Right : T) : integer
    begin
      result := -1 + Random(3);
    end
  ));
end;

You can, of course, use the above for any list (of any specific type), like:

//"pseudo" code ...
type
  TMyRecord = record
    b : boolean;
    i : integer;
    s : string;
  end;
var
  intList : TList<integer>;
  strList : TList<string>;
  recList : TList<TMyRecord>;
begin
  //add items to lists...
  //...

  //shuffle elements
  TGenericListHelper.Shuffle<integer>(intList);
  TGenericListHelper.Shuffle<string>(strList);
  TGenericListHelper.Shuffle<TMyRecord>(recList);
end;

Shuffle me gently by a sample …

Here’s a dummy example where a list of letters is displayed in a list box (“ListBox1”), then shuffled and displayed again.

Drop a TLIstBox on a form and have it filled in the OnCreate event of the form:

procedure TMainForm.FormCreate(Sender: TObject);
var
  c : Integer;
begin
  for c := 65 to 90 do
    ListBox1.Items.Add(CHR(c)+CHR(c)+CHR(c)) ;
end;

To make it more OOP (and therefore less clear to read, lol), have a class TMyObject defined as:

type
  TMyObject = class
    Value : string;
  end;

Now, have a TButton and handle its OnClick event to shuffle ListBox1’s elements:

procedure TMainForm.Button1Click(Sender: TObject);
var
  objects : TObjectList<TMyObject>;
  myO : TMyObject;
  s : string;
begin
  objects := TObjectList<TMyObject>.Create(true);
  try
    for s in ListBox1.Items do
    begin
      myO := TMyObject.Create;
      myO.Value := s;

      objects.Add(myO);
    end;

    //Option 1
    objects.Sort(TComparer<TMyObject>.Construct(
      function(const L,R : TMyObject) : integer
      begin
        //returns -1, 0 or 1
        result := -1 + Random(3);
      end
    ));

    //option 1 generalized
    TGenericListHelper.UnSort<TMyObject>(objects);

    //option 2
    TGenericListHelper.Shuffle<TMyObject>(objects);

    ListBox1.Clear;

    for myO in objects do
      ListBox1.Items.Add(myO.Value) ;
  finally
    objects.Free;
  end;
end;

If you have a simpler / shorter way to shuffle elements in lists – please do share as a comment…

12 thoughts on “How to Randomize / Shuffle (Generic) Collections and Lists – Implementing UnSort in Delphi

  1. Uwe Raabe

    As TObjectList.Sort internally uses QuickSort, I am not sure if that one will terminate when called with a random comparer. IIRC the QuickSort implementation used assumes that
    IF (A < B) AND (B < C) THEN <(A
    This is not guaranteed by that random comparer.

    Reply
  2. Uwe Raabe

    OK, that formula got scrambled by the formatting. In case this commenting system would allow me to either edit my comment or add a correction as a reply, I could write that this formula should read

    if (A < B) and (B < C) then (A < C) is true

    Reply
  3. zarkogajic Post author

    @Uwe, I’m not sure I understand what are you not sure of, but the presented UnSort method works as expected – it randomly rearranges the elements of a list.

    Reply
    1. Rudy Velthuis

      I think Uwe is right. Quicksort (probably any sort) depends on the fact that the results of a comparison are always the same and consistent. Using a random result certainly does something, but I doubt it shuffles properly.

      Reply
      1. zarkogajic Post author

        I’m not certain what would be “properly” in terms of shuffling, but if the (integer) list has items 1,2,3,4,5 and after calling UnSort the order is 4,2,5,3,1 and after calling again the order is 2,1,5,3,4 (and so on), that’s good enough for me.

        Reply
  4. Tony Frazier

    @zarko,

    The bigger strike against the Unsort method is going to be the performance characteristics. They’re going to be very uneven since the Comparer is returning random results — almost certainly worse on average than a normal quicksort. I’m still worried about the quicksort implementation getting into some very strange states with a random comparer as well.

    Also, your Fisher-Yates shuffle can stop at list.Count – 2. There’s not really any shuffling of the last element that can be done. 🙂

    Reply
  5. Tony Frazier

    I should have reviewed my other open tabs before commenting.

    Here’s a question asking about how various sort algorithms would perform given comparators that returned random results: https://cs.stackexchange.com/q/2336

    A properly implemented quicksort should be fine, other common sorting algorithms might perform slightly worse, but not degenerate significantly. Except bubble sort.

    Reply
  6. zarkogajic Post author

    @Tony,

    Yes, the (Fisher-Yates) Shuffle implementation can stop at -2, but -1 feels more natural even though the last step makes no sense.

    As for the UnSort, again, this is just “sorting” in random order, I do not see a problem here. I have it working without any issues (on small lists though). If performance would turn to be problematic I would go for the Shuffle method. Frankly, I’m always using the Shuffle method. The UnSort is a funny way to present how one can sort by unsorting 🙂

    Reply
  7. Thaddy de Koning

    Why not use the simple Satolo cycle to unsort?
    Example code (for an array, but you’ll get the point)
    uses math;
    var
    a:Array of cardinal;
    i,j:integer;
    t:cardinal;
    begin
    randomize;
    a:=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19];
    i := length(a);
    while i > 0 do
    begin
    dec(i);
    j :=randomrange(Low(a),i);
    t:=a[i];a[i]:=a[j];a[j]:=t;
    writeln(a[i]);
    end;
    end.

    It is a specialization of a fisher yates shuffle. https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Sattolo's_algorithm

    Reply
  8. Jasper Schellingerhout

    This method of sorting can end up in an endless loop, or take an enormous amount of time to finish. Its distribution is also not even (not quite sure why, but I did this test because I suspected as much). To test I did this

    Create a grid of vertices inside a 2×2 square (around 0,0). To test how good a random sample is I see if it is inside the unit radius circle inside the square. Random sampling that counts vertices inside the circle should approximate pi = 4 * InCircle/SampleSize.

    Your method has the largest deviation from pi and preforms the worst in terms of speed.

    Reply
    1. zarkogajic Post author

      Hi jasper,

      Thanks for the comments.

      I guess for every job the tool to be used is not always the same.

      For what I needed (shuffle a “deck of cards”) – the proposed “unsorting” works well.

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.