Advertisement
j3628800

C shuffle array

Apr 25th, 2024
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.16 KB | Source Code | 0 0
  1. /**
  2.  * Shuffle an array `arr` of length `len`.
  3.  *
  4.  * Having skipped the tutorials on the standard library, I invented this
  5.  * (time-inefficient and space-inefficient) method to solve this problem.
  6.  *
  7.  * Input code removed for the sake of simplicity.
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12.  
  13. void Swap(int *arr, int i, int j) {
  14.     int temp = arr[i];
  15.     arr[i] = arr[j];
  16.     arr[j] = temp;
  17. }
  18.  
  19. int *Zalloc(int len) {
  20.     int *j = (int *) malloc(len*sizeof(int) + 1);
  21.     if (j==NULL) {
  22.         perror("malloc failed\n");
  23.         exit(1);
  24.     }
  25.     return j;
  26. }
  27.  
  28. void PrintArray(int *arr, int len) {
  29.     for (int i=0; i<len; i++) {
  30.         printf("%d ", arr[i]);
  31.     }
  32.     printf("\n");
  33. }
  34.  
  35. float r, x;    /* static would be better */
  36.  
  37. int Rand(int *arr, int len) {    /* generate non-repeating PRNG 0<=x<len */
  38.     int rint, rintUnique;
  39.     rint = len * x;
  40.     rintUnique = arr[rint];
  41.     for (int i=rint+1; i<len; i++) {    /* remove already generated */
  42.         arr[i-1] = arr[i];
  43.     }
  44.     x = r * x * (1-x);
  45.     return rintUnique;
  46. }
  47.  
  48. void ShuffleArray(int *arrIn, int len) {
  49.     r = 3.75;    /* set to other values for different ordering */
  50.     x = 0.5;
  51.     int *arrTemp, *arrRand;
  52.     arrTemp = Zalloc(len);
  53.     arrRand = Zalloc(len);
  54.     for (int i=0; i<len; i++) {
  55.         arrTemp[i] = i;
  56.     }
  57.    
  58.     int rint;
  59.     int lenTemp = len;
  60.     for (int i=0; i<len; i++) {
  61.         rint = Rand(arrTemp, lenTemp);
  62.         arrRand[i] = rint;
  63.         //printf("rint is %d\n", rint);
  64.         lenTemp--;
  65.     }
  66.  
  67.     int lenHalf = len / 2;
  68.     for (int i=0; i<lenHalf; i++) {
  69.         Swap(arrIn, arrRand[i], arrRand[lenHalf+i]);
  70.         //printf("swapped elements %d and %d\n", arrRand[i], arrRand[lenHalf+i]);
  71.     }
  72.     free(arrTemp);
  73.     free(arrRand);
  74. }
  75.  
  76. int main() {
  77.     int array[] = {2,3,5,7,11,13,17,19,23,29,31};
  78.     int len = sizeof(array) / sizeof(int);
  79.    
  80.     printf("original: ");
  81.     PrintArray(array, len);
  82.     if (len<10) {
  83.         printf("\nArray is too short. Exiting\n");
  84.     } else {
  85.         ShuffleArray(array, len);
  86.         printf("shuffled: ");
  87.         PrintArray(array, len);
  88.     }
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement