Skip to content

Instantly share code, notes, and snippets.

@mitnk
Created November 20, 2012 06:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mitnk/4116421 to your computer and use it in GitHub Desktop.
Save mitnk/4116421 to your computer and use it in GitHub Desktop.
Shuffle Array Algorithm
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10
void ShuffleArray_Fisher_Yates(char* arr, const int len)
{
int i = len, j;
char temp;
if ( i == 0 ) return;
while ( --i ) {
j = rand() % (i+1);
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
void ShuffleArray_General(char* arr, int len)
{
const int suff_time = len;
for(int idx=0; idx<suff_time; idx++) {
int i = rand() % len;
int j = rand() % len;
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
void printArray(char a[], const int len)
{
int i;
for (i = 0; i < len; ++i)
printf("%c ", a[i]);
printf("\n");
}
void log_array(char a[], int log[][SIZE], const int len)
{
int i, j;
for (i = 0; i < SIZE; ++i)
{
j = a[i] - 'A';
++log[j][i];
}
}
void print_logger(int log[][SIZE], const int len)
{
int i, j;
int min = 2100000000;
int max = 0;
printf("- | ");
for (i = 1; i <= len; ++i)
{
printf("%7d ", i);
}
printf("\n");
for (i = 0; i <= 88; ++i)
{
if (i == 2)
printf("+");
else
printf("-");
}
printf("\n");
for (i = 0; i < len; ++i)
{
printf("%c | ", 'A' + i);
for (j = 0; j < len; ++j)
{
printf("%7d ", log[i][j]);
if (max < log[i][j])
max = log[i][j];
if (min > log[i][j])
min = log[i][j];
}
printf("\n");
}
printf("\n");
printf("min: %d max: %d\n\n", min, max);
}
void test(void (*shuffle_array)(char *, const int))
{
srand(time(0));
int i, j;
int log[SIZE][SIZE];
char a[SIZE];
for (i = 0; i < SIZE; ++i)
a[i] = 'A' + i;
for (i = 0; i < SIZE; ++i)
{
for (j = 0; j < SIZE; ++j)
log[i][j] = 0;
}
for (i = 0; i < 1000000; ++i)
{
(*shuffle_array)(a, SIZE);
log_array(a, log, SIZE);
}
print_logger(log, SIZE);
}
int main()
{
int i;
for (i = 0; i < 20; ++i)
test(ShuffleArray_General);
for (i = 0; i < 20; ++i)
test(ShuffleArray_Fisher_Yates);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment