Sorting Array Data without Modifying Content

Question

I'm trying to write a simple program that reads several integers, puts them into an array and then call a function that sorts them in ascending order. The twist though, is that I want to sort them without changing the content of the array. Is there any way of doing this?

    int selection_sort(int *, int);             //prototype

    int selection_sort(int * num,int n)                
    //num is the first address of the array and n is array length
    {
    int min, target, i, j, temp;
    for(i=0; i<n; i++)
    {
        min = num[i];
        target = i;
        for(j=i+1; j<n;j++)
        {
            if(num[j]<min)
            {
                min = num[j];
                target = j;
            }
        }
        if(target != i)                       
        {
        //My intuition tells me that here's where I need to work some magic
        temp = &num[i];                   
        &num[i] = &num[target];           //Here's what I was planning on doing
        &num[target] = temp;
        }
    }
    }

If I remove the ampersands the function works like a traditional sorting function, so when I print it in the main function the array contents have been changed. So I thought that if I changed the addresses around, then when I printed it, then the original (not-sorted) array would show, sadly the compiler doesn't allow me to do this.

Answer 1

Assuming you have a data array A with N elements in it that you can't (afford to) change, you can create a parallel array P initialized such that P[i] == i for each element in 0..N-1. You can then arrange that the sorting algorithm permutes the array P such that A[P[i]] is the i^th element in the sorted order. It isn't a standard sort operation, so you'll have to write your own sort code, but it isn't a dreadfully difficult sort to write.

An alternative option is to use a parallel array of pointers. If the elements in A are of type T (so you have T A[N]; as the declaration of the array), then you could create a parallel array T *P[N]; and initialize each element such that P[i] == &A[i]. Then you can sort P using the standard qsort() function and an appropriate comparator that follows the pointers to the values. This is arguably a better solution because it leverages the standard sorting code. Once it is sorted, you can use *P[i] to access the i^th value in A in sorted order, without having affected A itself at all.

Answer 2

If you want to swap the elements around inside of your original array (and thus lose the original entered sorting, but only use the same initial memory footprint) you're describing a Bubble Sort.

It does require the elements to be moved around in the initial array of memory so it is technically modifying the input, but I'm not sure if this is what you were implying.

You essentially compare each item with the one to the right in sequence as you walk forwards through the array and swap them if they're in the wrong order, and repeat the process n times.

More: http://en.wikipedia.org/wiki/Bubble_sort