Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Shuffle an array `arr` of length `len`.
- *
- * Having skipped the tutorials on the standard library, I invented this
- * (time-inefficient and space-inefficient) method to solve this problem.
- *
- * Input code removed for the sake of simplicity.
- */
- #include <stdio.h>
- #include <stdlib.h>
- void Swap(int *arr, int i, int j) {
- int temp = arr[i];
- arr[i] = arr[j];
- arr[j] = temp;
- }
- int *Zalloc(int len) {
- int *j = (int *) malloc(len*sizeof(int) + 1);
- if (j==NULL) {
- perror("malloc failed\n");
- exit(1);
- }
- return j;
- }
- void PrintArray(int *arr, int len) {
- for (int i=0; i<len; i++) {
- printf("%d ", arr[i]);
- }
- printf("\n");
- }
- float r, x; /* static would be better */
- int Rand(int *arr, int len) { /* generate non-repeating PRNG 0<=x<len */
- int rint, rintUnique;
- rint = len * x;
- rintUnique = arr[rint];
- for (int i=rint+1; i<len; i++) { /* remove already generated */
- arr[i-1] = arr[i];
- }
- x = r * x * (1-x);
- return rintUnique;
- }
- void ShuffleArray(int *arrIn, int len) {
- r = 3.75; /* set to other values for different ordering */
- x = 0.5;
- int *arrTemp, *arrRand;
- arrTemp = Zalloc(len);
- arrRand = Zalloc(len);
- for (int i=0; i<len; i++) {
- arrTemp[i] = i;
- }
- int rint;
- int lenTemp = len;
- for (int i=0; i<len; i++) {
- rint = Rand(arrTemp, lenTemp);
- arrRand[i] = rint;
- //printf("rint is %d\n", rint);
- lenTemp--;
- }
- int lenHalf = len / 2;
- for (int i=0; i<lenHalf; i++) {
- Swap(arrIn, arrRand[i], arrRand[lenHalf+i]);
- //printf("swapped elements %d and %d\n", arrRand[i], arrRand[lenHalf+i]);
- }
- free(arrTemp);
- free(arrRand);
- }
- int main() {
- int array[] = {2,3,5,7,11,13,17,19,23,29,31};
- int len = sizeof(array) / sizeof(int);
- printf("original: ");
- PrintArray(array, len);
- if (len<10) {
- printf("\nArray is too short. Exiting\n");
- } else {
- ShuffleArray(array, len);
- printf("shuffled: ");
- PrintArray(array, len);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement