Swapping elements in an array of strings

Question

I'm trying to create a program to generate random test cases. I have an array of strings (char **) that are ordered and I would like to randomize them. My approach is to randomly select two elements and swap them. However I keep getting a segfault and appear to missing some piece of knowledge.

Sample array(64 elements): {"1 2 3", "3 2 1", "4 5 6".....}

char ** randomizeOrder(char ** list, int size){

    char temp[6];
    temp[5] = '\0';

    srand(time(NULL));
    int count = 64;
    int x, y;
    while(count > 0){
        fprintf(stderr, "Starting...\n");
        x = rand() % 64;
        y = rand() % 64;

        strcpy(temp, list[x]);
        fprintf(stderr, "Copying %s from Y to X\n", list[y]);
        strcpy(list[x], list[y]);
        fprintf(stderr, "Copying %s from temp to Y\n", temp);
        strcpy(list[y], temp);
        count--;
    }

    return list;

}

It appears to work for the first few elements and then starts reading garbage. The elements are malloc'ed as is the array, all elements print just fine. Any ideas whats going wrong?

Answer 1

I believe their are some issues in your code:

• You pass size to randomize(), but you never use it. It would better to do:

  size_t x = rand() % size;
  size_t y = rand() % size;
  

  Instead of hard coding a size value of 64 into these lines.

• Since you are swapping pointers, their is no need to create a temporary buffer and strcpy() pointers into it. You can simply swap the pointers themselves. I recommend just using a function like this:

  void swap(char **s1, char **s2) {
      char *temp = *s1;
      *s1 = *s2;
      *s2 = temp;
  }
  

  then you can simply pass swap(&list[x], &list[y]); to swap your pointers.

• I don't believe your function randomize() needs to return char**. It would be easier if it was simply void.

Here is some testing code that shows this:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAYSIZE(x) (sizeof x / sizeof x[0])

void randomize(char **list, size_t size);
void print_list(char **list, size_t size);
void swap(char **s1, char **s2);

int main(void) {
    char *list[] = {"1 2 3", "3 2 1", "4 5 6", "6 5 4", "7 8 9", "9 8 7"};

    printf("Original list:\n");
    print_list(list, ARRAYSIZE(list));

    randomize(list, ARRAYSIZE(list));

    return 0;
}

void randomize(char **list, size_t size) {
    size_t x, y;

    srand(time(NULL));

    for (size_t i = 0; i < size; i++) {
        x = rand() % size;
        y = rand() % size;

        swap(&list[x], &list[y]);

        printf("Swapping list[%zu] and list[%zu]:\n", x, y);
        print_list(list, size);
    }
}

void print_list(char **list, size_t size) {

    printf("{");
    for (size_t i = 0; i < size-1; i++) {
        printf("%s, ", list[i]);
    }
    printf("%s}\n\n", list[size-1]);
}

void swap(char **s1, char **s2) {
    char *temp = *s1;
    *s1 = *s2;
    *s2 = temp;
}

Random output:

Original list:
{1 2 3, 3 2 1, 4 5 6, 6 5 4, 7 8 9, 9 8 7}

Swapping list[0] and list[4]:
{7 8 9, 3 2 1, 4 5 6, 6 5 4, 1 2 3, 9 8 7}

Swapping list[4] and list[1]:
{7 8 9, 1 2 3, 4 5 6, 6 5 4, 3 2 1, 9 8 7}

Swapping list[0] and list[1]:
{1 2 3, 7 8 9, 4 5 6, 6 5 4, 3 2 1, 9 8 7}

Swapping list[3] and list[3]:
{1 2 3, 7 8 9, 4 5 6, 6 5 4, 3 2 1, 9 8 7}

Swapping list[2] and list[1]:
{1 2 3, 4 5 6, 7 8 9, 6 5 4, 3 2 1, 9 8 7}

Swapping list[4] and list[1]:
{1 2 3, 3 2 1, 7 8 9, 6 5 4, 4 5 6, 9 8 7}

Answer 2

One problem of your code is that it is possible to have x and y to be same number, and you are strcpying to itself when strcpy(list[x], list[y]);. Afaik, this is not guaranteed to work.

(Though I believe your actual problem may have to do in how you populate the input char**. Cannot verify as it is lack of information now)

Answer 3

Think you should just swap the pointers, not the string content itself. A char** of course is just an array of pointers.

Would look like this:

while(count > 0){
    x = rand() % 64;
    y = rand() % 64;

    char* tmp = list[x];
    list[x] = list[y];
    list[y] = tmp;
    count--;
}

If you want to be very clever you can use this trick:

while(count > 0){
    x = rand() % 64;
    y = rand() % 64;

    list[x] |= list[y];
    list[y] |= list[x];
    list[x] |= list[y];

    count--;
}