Sorting an array in O(N) time

Question

given an array A of the integers 1,2,3,...,N and the character " "(space) we want to sort it to be [1,2,3,...,N," "], where we can only swap integers with " ", but not with each other, so swap(3," ") is allowed while swap(1,2) is not.

My attempt at it was to denote the space be "-1", and search for it in O(N) time, then go over the array again from i=1 to N+1 and if I see for example A[2] = 7, I would swap A[7] with " ", then I'd swap A[2] with " " while keeping track of " "'s position since It's the only way to swap, that way 7 would end up at A[7] ( with the exception of index shifting) The code I wrote is the following:

public static int[] arraySort(int[] array){

    int space = 0;

    for(int i = 0; i<array.length; i++ ){
        if(array[i] == -1){
            space = i;
        }
    }

    for(int i = 0; i<array.length; i++){
        if(array[i] != i+1 && array[i] !=-1){
            swap(array, array[i]-1 , space);
            space = array[i]-1;
            swap(array, i, space);
            space = i;
        }
    }
    return array;
}

public static void swap(int[] arr, int ind1, int ind2){

    int temp = arr[ind2];
    arr[ind2] = arr[ind1];
    arr[ind1] = temp;
}

It did work, however for input such as A[7,3,5,4,6,1,2,-1] it failed, I'm aware that I might be sending an integer to the head of the array but I can't see why it wouldn't get back out since a different number goes there then it would eventually go to its position. Help? or an idea of how to fix this( while still keeping it in O(N) time if possible?

Answer 1

Using counting sort technique. All the time put the space at the end of the array. You have an array with size N+1. Now, try to read the array from the first place. For example, it is 3. You should put 3 in the 3rd place of the array. To do this, swap the current 3rd value of the array with space, and then swap the first place of the array with the 3rd, and then swap the first with the last item of the array. The latter step will be done to keep the space at the end of the array.

public static int[] arraySort(int[] array){
    int N = array.length - 1;
    for(int i = 0; i < N; i++){
        int currentNum = array[i]-1;
        swap(array, currentNum, N); // swap currentNum-th item with space as the last memebr of the array
        swap(array, i, currentNum); // swap the current item with its place
        swap(array, i, N); // swap the space with the last item.
    }

    return array;
}

public static void swap(int[] arr, int ind1, int ind2){
    int temp = arr[ind2];
    arr[ind2] = arr[ind1];
    arr[ind1] = temp;
}

In the above code, we assume that the location of the space in the start array is in the last. If it is not, you can find it in O(N) and swap it with the last place of the array.

Answer 2

Step 1 make a lookup array

You make make an array N+1 long, where each value in the lookup array indicates where it is in the array to be sorted. You can make Lookup[0] refer to where the space is. It will take O(n) time to make such an array. So in the case [7,3,5,4,6,1,2,-1] you make an array [7,5,6,1,3,2,4,0]

Step 2 move the space to start of the array

you can find the current index of the space by lookup[0], if it is already at index 0, then go to the next step, otherwise swap with index 0. You should then update the loop array to reflect the change. ie lookup[value that was at 0] = [where the space started].

Step 3 swap the space with the next element in the array

Now swap the space with 1. You can find it with the lookup array.

Step 4 repeat

Now move the space to index 1 if need, and swap with 2. Then move the space to index 2 and swap with 3. Repeat until it is sorted.

Total time is N to make the lookup array, and 2 swaps for each element, total O(3N).

Answer 3

The algorithm you describe is pretty much right, but you made a couple mistakes.

First, you might have to swap multiple times at the same position. Second, if you hit the space you have to put it in the right place. Here is your loop fixed. Note that I stop the iteration one position earlier.

for(int i = 0; i<array.length-1; i++){
    while (array[i] != i+1){
        if (space==i) {
            // it's the space
            swap(array, i, array.length-1);
            space = array.length-1;
        } else {
            swap(array, array[i]-1, space);
            space = array[i]-1;
            swap(array, space, i);
            space = i;
        }
    }
}

Notice that after we move a number, we always end with space = i, so we'll do the space in the next inner iteration. We can optimize this, ending up with what looks like @OmG's method, except that he missed the while loop too:

swap(array, space, array.length-1);

for(int i = 0; i<array.length-1; i++){
    while (array[i] != i+1){
        int currentTarget = array[i]-1;
        //move space to current target
        swap(array, currentTarget, array.length-1);
        //move current element to its target
        swap(array, currentTarget, i);
        //put the space back where it belongs
        swap(array, i, array.length-1);
    }
}

It is important to understand why this is still O(n), even though we've added an inner loop: Each iteration of the inner loop fixes the position of exactly one number, after which we will never move that number again. This can happen at most n times, since there are only that many numbers to fix.