Mega Code Archive
Shuffling data using a parallel algorithm
<![CDATA[
Title: Shuffling data using a parallel algorithm
Question: There are many solutions for sorting your data (Bubblesort, QuickSort, Merge and Divide, ...), however if you ever want to shuffle your data, often you'll be left alone.
Answer:
This article I have first published in German at the Delphi-PRAXiS on February, 20th 2004.
A common way to merge your data
Most algorithms shuffling your data are based upon a simple Random based algorithm that swaps different positions in an array with each other over and over again. Long enough that you may say that the data are in a unordered position. A single thread (usually your main application) access the data in different positions multiple times and does it often enough to provide a solution you will accept as "merged".
// ShuffleArray
// aData: pointer to an array of integer numbers
// (probably sorted)
// aMin: lowest member of array to be shuffeled
// aMax: highest member of array to be shuffeled
// aIterations: number of iterations each thread
// has to do on array
procedure ShuffleArray(aData: PIntegerArray;
aMin, aMax: Integer; aIterations: Integer);
var
Source, Dest, Temp: Integer;
begin
// for each shuffle to be done
while aIterations 0 do
begin
// get source an destination for shuffling
Source := RandomRange(aMin, aMax);
Dest := RandomRange(aMin, aMax);
// swap data
Temp := aData^[Source];
aData^[Source] := aData^[Dest];
aData^[Dest] := Temp;
// one shuffle done
Dec(aIterations);
end;
end;
]]>