Shuffling array elements in C

Question

This is an answer to this problem.

Basically, given an array, swap the given number of elements in the array.

The solution that came to my mind: since we always swap at least two elements, pick two random indices and swap array[first_random] with array[second_random]. Then, if there's more to swap, find index that was not swapped yet and swap it with one of previously swapped.

This might be confusing a little, but it works. I am curious whether there are some other, better approaches.

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

void print_arr(int a[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ",a[i]);
    }
        printf("\n");
}

void swap(int a[], int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

int next_idx(int swapped[], int s_count, int size) {
    int n, i;
    char in_arr;
    while (1) {
        in_arr = 0;
        n = rand() % size;
        for (i = 0; i < s_count; i++) {
            if (swapped[i] == n) {
                in_arr = 1;
                break;
            }
        }
        if (!in_arr) {
            break;
        }
    }
    return n;
}

void swap2_or_more(int a[], int size,int count) {
    srand(time(NULL));
    int i, j, s_count = 0;
    int swapped[size];
    i = rand() % size;
    swapped[s_count] = i;
    s_count++;
    do {
        j = rand() % size;
    } while (i == j);  // make sure indexes are different
    swapped[s_count] = j;
    s_count++;

    swap(a, i, j);
    count -= 2;
    while (count) {
        i = next_idx(swapped, s_count, size);
        j = rand() % s_count;
        swap(a, i, swapped[j]);
        swapped[s_count] = i;
        s_count++;
        count--;
    }
    printf("swapped indexes:\n");
    print_arr(swapped, s_count);
}

int main(void)
{
    int a[] = {1,2,3,4,5,6,7,8,9,10};
    swap2_or_more(a, 10, 5);
    printf("array after swap:\n");
    print_arr(a, 10);
    return 0;
}

Answer 1

There is a huge amount of guessing in your program, code like:

int next_idx(int swapped[], int s_count, int size) {
    int n, i;
    char in_arr;
    while (1) {
        in_arr = 0;
        n = rand() % size;
        for (i = 0; i < s_count; i++) {
            if (swapped[i] == n) {
                in_arr = 1;
                break;
            }
        }
        if (!in_arr) {
            break;
        }
    }
    return n;
}

Let's say the input data has 1000000 members, and we need to swap 10 of them... swapped[] array contains.... {1, 100, 500, 800, 1000, 10000} do we really just keep guessing until we hit a random value that is in the data? This is... a problem.

One solution which will produce a suitably random distribution of the swapped items relies on a 'simple' algorithm which does just one rand() per item, and there's no guess-work. This is done using a fisher-yates shuffle. But, for this problem, we don't shuffle the items, we shuffle the indexes... so:

void swap2_or_more(int a[], int size,int count) {
    int i, tmp;
    int swapped[size];

    // initialize the swapped array with all the data indices.
    for (i = 0; i < size; i++) {
        swapped[i] = i;
    }

    // Fisher-Yates shuffle the indices.
    // http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
    for (int i = size-1; i > 0; i--) {
        tmp = rand() % (i + 1);
        swap(swapped, i, tmp);
    }

    // 'rotate' the values in the first count swapped/random indexes
    tmp = a[swapped[--count]];
    while(count > 0) {
        a[swapped[count]] = a[swapped[count - 1]];
        count--;
    }
    a[swapped[0]] = tmp;
}

Answer 2

Always put srand() in main(), not in another function or anywhere else. This is to ensure that it's called only once, which is important so that the seed is not reset. If this happens, then you'll get the same number each time, defeating the purpose of even acquiring random numbers.