Thanks to rFree's post I wanted to look a little closer at this Sorry if all this seems a bit long for such a simple thing.
That won't shuffle very well at all.
I'd say it shuffles well enough, unless you are into scientific random probability statistics stuff. Or some such thing OK it had a minor flaw in swapping when not needed, and scanning the array to the end (again swapping with itself). But this is almost not worth mentioning for a first draft. I changed it in the versions below. "Bubble unsort" might be a misnomer too, i just though I remembered a very similar sorting method, but I see now that a bubble sort is different. At any rate I'd say both shufflers use the same principle, and now I know it has an impressive-sounding name: The Fisher[ch8211]Yates shuffle http://en.wikipedia.org/wiki/Fisher[ch8211]Yates_shuffle
So I'd say you posted an almost identical algorithm, with the addition of the rand_range() function, which alters the random output somehow. This is why it is different. Which is better I don't know. Also note; when I changed the "bubble unsort" to scan the array in the same direction as your fisher-yates (ie backwards), the outputs where exactly identical when I tested them on my PC (code::blocks in ubuntu). However on the Arduino I got different results. Not sure why that is. I had to change the arduino version a bit, but I don't think that's the reason (no guarantee that I didn't make any errors though).
But anyway thanks for some interesting code!
The difference (on the arduino version at least) is all due to the rand_range() function, which doesn't have anything to do with Fisher-Yates as far as I can see. Otherwise the two shuffling methods are really the same. I get the same result when implementing rand_range() (and scanning the array the same way) on the arduino too. Not surprising since they are basically the same.
void bubbleUnsort(int *list, int elem)
{
for (int a=elem-1; a>0; a--)
{
//int r = random(a+1);
int r = rand_range(a+1);
if (r != a)
{
int temp = list[a];
list[a] = list[r];
list[r] = temp;
}
}
}
// generate a value between 0 <= x < n, thus there are n possible outputs
int rand_range(int n)
{
int r, ul;
ul = RAND_MAX - RAND_MAX % n;
while ((r = random(RAND_MAX+1)) >= ul);
return r % n;
}
Btw, in case someone is interested, these are the test programs I made for the arduino and code::blocks
On the arduino, functions with arguments like this:
void shuffle_swap(size_t index_a, size_t index_b, void *array, size_t size)
became
void shuffle_swap(int index_a, int index_b, int *array, int size)
Since I don't know how else to do it. But anyway this doesn't matter for testing shuffling routines.
Also had to add a cast to a char pointer in both versions in the shuffle_swap() function. But I don't belive that matters, as the shuffle_swap() takes care of the array's data type size. (Except possibly in the modified arduino version).
This is the arduino code:
// Arduino comparative shuffle test
// Fisher-yates vs "bubble unsort"
// 2010.03.13 raron
int anArray[] = {0,1,2,3,4,5,6,7,8};
int elements = sizeof(anArray) / sizeof(int);
int anotherArray[] = {0,1,2,3,4,5,6,7,8};
int arraySize = sizeof(anotherArray) / sizeof(int);
void setup()
{
Serial.begin(9600);
delay(2000);
int noise = analogRead(2);
randomSeed(noise);
/*
Serial.print("RAND_MAX is ");
Serial.println(RAND_MAX,DEC);
Serial.println("---- Original ----: ");
printArray(anotherArray, arraySize);
Serial.println("");
*/
// bubble unsort shuffle
bubbleUnsort(anotherArray, arraySize);
Serial.println("---- bubble unsorted ---- ");
printArray(anotherArray, arraySize);
Serial.println("");
Serial.println("");
randomSeed(noise); // seeding with same nr. again
// Fisher-yates
shuffle(anArray, elements, sizeof(int));
Serial.println("---- fisher-yates shuffled ---- ");
printArray(anArray, elements);
}
void loop()
{
}
void printArray(int *array, int elem)
{
for (int i=0; i<elem; i++)
{
Serial.print("array[ ");
Serial.print(i); Serial.print(" ] = ");
Serial.println(array[i]);
}
}
void bubbleUnsort(int *list, int elem)
{
for (int a=elem-1; a>0; a--)
{
int r = random(a+1);
//int r = rand_range(a+1);
if (r != a)
{
int temp = list[a];
list[a] = list[r];
list[r] = temp;
}
}
}
// generate a value between 0 <= x < n, thus there are n possible outputs
int rand_range(int n)
{
int r, ul;
ul = RAND_MAX - RAND_MAX % n;
while ((r = random(RAND_MAX+1)) >= ul);
//r = random(ul);
return r % n;
}
void shuffle_swap(int index_a, int index_b, int *array, int size)
{
char *x, *y, tmp[size];
if (index_a == index_b) return;
x = (char*)array + index_a * size;
y = (char*)array + index_b * size;
memcpy(tmp, x, size);
memcpy(x, y, size);
memcpy(y, tmp, size);
}
// shuffle an array using fisher-yates method, O(n)
void shuffle(int *array, int nmemb, int size)
{
int r;
while (nmemb > 1) {
r = rand_range(nmemb--);
shuffle_swap(nmemb, r, array, size);
}
}
And this is the code::blocks version:
// PC comparative shuffle test
// Fisher-yates vs "bubble unsort"
// 2010.03.13 raron
#include <iostream> // cout
#include <cstdlib> // rand()
#include <ctime> // time()
#include <string.h> // memcpy
using namespace std;
int anArray[] = {0,1,2,3,4,5,6,7,8};
int elements = sizeof(anArray) / sizeof(int);
int anotherArray[] = {0,1,2,3,4,5,6,7,8};
int arraySize = sizeof(anotherArray) / sizeof(int);
void printArray(int *array, int elem);
void bubbleUnsort(int *list, int elem);
int rand_range(int n);
void shuffle_swap(size_t index_a, size_t index_b, void *array, size_t size);
void shuffle(void *array, size_t nmemb, size_t size);
int main()
{
int timesec = time(0);
srand((unsigned)timesec); // random seed based on seconds since midnight
/*
cout << "RAND_MAX is " << RAND_MAX << " with size: " << sizeof(RAND_MAX) << "bytes" << endl;
cout << "---- Original array ----: " << endl;
printArray(anotherArray, arraySize);
cout << endl;
*/
// bubble unsort
bubbleUnsort(anotherArray, arraySize);
cout << "---- Bubble unsorted ---- " << endl;
printArray(anotherArray, arraySize);
cout << endl;
srand((unsigned)timesec); // seeding with the same nr again
// fisher-yates
shuffle(anArray, elements, sizeof(int));
cout << "---- Fisher-yates shuffled ---- " << endl;
printArray(anArray, elements);
return 0;
}
void printArray(int *array, int elem)
{
for (int i=0; i<elem; i++) cout << "array[ " << i << " ] = " << array[i] << endl;
}
void bubbleUnsort(int *list, int elem)
{
for (int a=elem-1; a>0; a--)
{
int r = rand()%(a+1);
//int r = rand_range(a+1); // seemingly doesn't matter which one is used on the PC
if (r != a)
{
int temp = list[a];
list[a] = list[r];
list[r] = temp;
}
}
}
// generate a value between 0 <= x < n, thus there are n possible outputs
int rand_range(int n)
{
int r, ul;
ul = RAND_MAX - RAND_MAX % n;
while ((r = rand()) >= ul); // r = rand()%ul;
//r = rand()%ul;
return r % n;
}
void shuffle_swap(size_t index_a, size_t index_b, void *array, size_t size)
{
char *x, *y, tmp[size];
if (index_a == index_b) return;
x = (char*)array + index_a * size; // had to cast array to a char pointer
y = (char*)array + index_b * size;
memcpy(tmp, x, size);
memcpy(x, y, size);
memcpy(y, tmp, size);
}
// shuffle an array using fisher-yates method, O(n)
void shuffle(void *array, size_t nmemb, size_t size)
{
int r;
while (nmemb > 1) {
r = rand_range(nmemb--);
shuffle_swap(nmemb, r, array, size);
}
}
EDIT: Hey, 100th post