CS3343/3341
 Analysis of Algorithms 
  Randomize an Array   

Randomize an Array, the Hard Way

Here we want to randomize the order of elements in an array. For simplicity we use an array A of 26 letters, initialized to the 26 capital letters, in order. The first strategy is to create an array R of 26 random doubles. We will then sort R using a simple bubble sort algorithm. This algorithm just interchanges adjacent array elements that happen to be out of order, until the array is ordered. For every interchange performed on R, we perform the same interchange on A, so that as R is brought into order, A is brought into the disorder represented by the original disorder of R.

Because bubblesort is Θ(n2), so is this randomization algorithm. Could we do the same thing with quicksort? If so, we would have a Θ(n log(n)) algorithm.

Randomize an Array, the Hard Way
// ran.c: randomize array
#include <stdio.h>
#include <math.h>
#include "bubblesort.h"
#define ALPHA 26

double seed = 11111.0;
double rand();
void printr(double []);
void printa(int []);

int main() {
   int A[ALPHA];
   double R[ALPHA];
   int i;
   for (i = 0; i < 100; i++) rand();
   for (i = 0; i < ALPHA; i++) {
      A[i] = 'A' + i;
      R[i] = rand();
   }

   printa(A);
   printr(R);
   doublebubble(R, A, 0, ALPHA-1);
   printa(A);
   printr(R);
}

void printr(double R[]) {
   int i;
   for (i = 0; i < ALPHA; i++)
      printf("%20.16f\n", R[i]);
   printf("\n");
}

void printa(int A[]) {
   int i;
   for (i = 0; i < ALPHA; i++)
      printf("%c", A[i]);
   printf("\n");
}

double rand() {
   double a = 16807.0,
          m = 2147483647.0;
   double q;
   seed = a*seed;
   q = floor(seed/m);
   seed = seed - q*m;
   return(seed/m);
}
// bubblesort.h
void bubblesort(double [] , int , int );
void doublebubble(double [], int [], int, int);
int issorted(double [], int );

// bubblesort.c
#include <stdio.h>
#include "bubblesort.h"
 
static void exchange(double R[], int i, int j) {
   double temp = R[i];
   R[i] = R[j];
   R[j] = temp;
}
static void exchange2(int A[], int i, int j) {
   int itemp = A[i];
   A[i] = A[j];
   A[j] = itemp;
}

// bubblesort: sort array A
void bubblesort(double A[], int p, int r) {
   int dummy;
   int i;
   double temp;
   for (dummy = p; dummy < r; dummy++)
         for (i = 0; i < r; i++)
            if (A[i] > A[i+1]) {
               exchange(A, i, i+1);
            }
}

// doublebubble: sort R; rearrange A
void doublebubble(double R[], int A[],
      int p, int r) {
   int dummy;
   int i;
   double temp;
   for (dummy = p; dummy < r; dummy++)
         for (i = 0; i < r; i++)
            if (R[i] > R[i+1]) {
               exchange(R, i, i+1);
               exchange2(A, i, i+1);
            }
}
int issorted(double R[], int len) {
   int i;
   for (i = 0; i < len - 1; i++)
      if (R[i] >= R[i+1]) return 0;
   return 1;
}

cc -o ran -lm ran.c bubblesort.c
% ./ran
ABCDEFGHIJKLMNOPQRSTUVWXYZ
  0.2173017762681943
  0.1909537395420269
  0.3595004828458189
  0.1246151896773908
  0.4074929079075776
  0.7333032026576359
  0.6269270668862980
  0.7632131580092074
  0.3235466607490306
  0.8487272089574147
  0.5582009472689595
  0.6833207494035926
  0.5718352261799552
  0.8346464065064892
  0.9021541545643258
  0.5048757626232112
  0.4469424083116196
  0.7610564933908435
  0.0764844199067375
  0.4736453725367996
  0.5577762259905116
  0.5450302225281625
  0.3229500308274059
  0.8211681162105725
  0.3725291510915985
  0.0974423964961629



SZDBAWICYEQTPVUKMGLFRHXNJO
  0.0764844199067375
  0.0974423964961629
  0.1246151896773908
  0.1909537395420269
  0.2173017762681943
  0.3229500308274059
  0.3235466607490306
  0.3595004828458189
  0.3725291510915985
  0.4074929079075776
  0.4469424083116196
  0.4736453725367996
  0.5048757626232112
  0.5450302225281625
  0.5577762259905116
  0.5582009472689595
  0.5718352261799552
  0.6269270668862980
  0.6833207494035926
  0.7333032026576359
  0.7610564933908435
  0.7632131580092074
  0.8211681162105725
  0.8346464065064892
  0.8487272089574147
  0.9021541545643258

Randomize an Array, the Easy and Quick Way

There is a much better Θ(n) algorithm, one of the simplest and most elegant algorithms in the book (page 126):

Randomize-In-Place(A)

n = A.length
for i = 1 to n
   Exchange(A[i], A[Random(i, n)])

Random(a, b)
// assumes a <= b
// return x, a <= x <= b
// all integers equally likely
   return
      floor((b - a + 1)*Uniform() + a)

Here is an imlementation using the simplifying conventions of the earlier program:

Randomize an Array, the Easy and Quick Way
// ran2.c: randomize an array
#include <stdio.h>
#include <math.h> // needed for floor
#define ALPHA 26

double seed1 = 1.0;
double seed2 = 1.0;
double seed;

void inita(int []);
void randomize(int []);
void exchange(int [], int , int );
void printa(int []);
double rand();

int main() {
   int A[ALPHA];
   int i;
   // exercise the RNG a little
   for (i = 0; i < 100; i++) rand();
   inita(A);
   printa(A);
   
   for (i = 0; i < 20; i++) {
      inita(A);
      randomize(A);
      printa(A);
   }
}

void inita(int A[]) {
   int i;
   for (i = 0; i < ALPHA; i++)
      A[i] = 'A' + i;
}

void printa(int A[]) {
   int i;
   for (i = 0; i < ALPHA; i++)
      printf("%c", A[i]);
   printf("\n");
}

// randomize: this does the work
void randomize(int A[]) {
   int i;
   for (i = 0; i < ALPHA; i++)
      exchange(A, i, random(i,ALPHA-1));
}

void exchange(int A[], int i, int j) {
   int itemp = A[i];
   A[i] = A[j];
   A[j] = itemp;
}

// random: returns random x, a<=x<=b
int random(int a, int b) {
   return floor((b - a + 1)*rand() + a);
}

// rand: returns random uniform double x, 0 < x < 1
double rand() {
   double a1 = 48271.0,      a2 = 40692.0,
          m = 2147483647.0,  m2 = 2147483399;
   double q1,                q2;
   double q, diff;
   seed1 = a1*seed1;         seed2 = a2*seed2;
   q1 = floor(seed1/m);      q2 = floor(seed2/m2);
   seed1 = seed1 - q1*m;     seed2 = seed2 - q2*m2;
   // now combine results
   if ((diff = seed1 - seed2) < 0.0)
      diff = diff + m;
   q = floor(diff/m);
   seed = diff - q*m;
   return(seed/m);
}

ABCDEFGHIJKLMNOPQRSTUVWXYZ
CKPYNGDHZEAMXJTUSRIWLQVBFO
BYNZQWHXODVSLKCUERGTPMAJFI
HMRIPVNCJYWGSULKBQDZOXTAEF
YZAGKEVCJTRLQONSWFXIHUBDPM
KSHPBVCEDYNXIWRQOTFJULZAMG
NOCFHJUAEYDTVIRQSZWKPXBLMG
ECRBZQYHOLMFANKWUTDPISXJGV
ORTNFSXKEQLJMBUVCIHPGWDAZY
QGFAIKRMHTJLUDVZCYSWXEONBP
HEUKVLDBRGMNQFSOXCAIJPTYZW
OCXQALUDBKMETHGIVWFNZJYSPR
RESYHOWZFGUVICPQJLNDKTMXBA
VICDKLGFTQAXYZORSPWEUMBNHJ
XRHGYJLVZUCEWIPDONTMKQASFB
LTSZWUGRHVXIDPBQENYMKJFCAO
OFWHDCLNEQKMJRVTSIUAZGPYXB
PEXRNGQKBLTIFJWVCYZDHMUSAO
THLNGCBDKSYORUFQPZWEMIAJXV
MOFBARTWEYKGCIXLDSUVZQHNJP
VUDSLIMFAOJZPQXWNGHBREYTCK

ABCDEFGHIJKLMNOPQRSTUVWXYZ
CVAYSFKBMHQITERGUPXZLNJWOD
VOSBIWKDPFUQAYRHMCXNELTJGZ
BETROYKJSZXLQVAPMUNHGDCIFW
EIJUPMTQWOKGBAYLZHVXCFRDSN
KAFCBNSVLDMYTZWGQRPJEOIHXU
WTSLKDPZUAYXQMOJFCGVHBENIR
CIMBRPKDWFGYXANSLOQVHZUETJ
HGYJATVSWFCDIMPUNZQBELORKX
WAMQYNHPTKLVSRODFBIGZUCEJX
CBGSILXZOAWDENMTUPYJKHQVFR
TZFICEJSDNRAQYGKOLMWBXHUVP
FTBMYXUZPCHEWGNIRLVOKJDSQA
PRHTDIAKSQUOLYXZJNFWBMGECV
XHYKFEZTBWAJLGMROICDNQUVPS
XVGFZBOYDSTJQNKLMHAUCIWRPE
IPVXJDYBKALOURGSHMENZTQWFC
RIMPFSJTOBLUKXEDNQYVWHGZCA
DCXUWKRBYSVFZEHOGPQATMNJIL
CBMUFLJIAKGRSPODHTVEXQZNWY
ZBDRLGMSPVOKTYQWICJFNXEAUH

Revision date: 2012-09-13. (Please use ISO 8601, the International Standard Date and Time Notation.)