In-place rearrangement - Index-based sort - parking lot problem

Image we have a parking lot with 100 spots, there are 99 cars in each spot, and given one empty spot and array of random unique integers between 0 and 98, e.g. 1, 3, 5, 0, 2, 4.., we want to move cars at index i to array[i].  We can only move car from one spot to another spot, can't park car in any places except those designated spots.

The above similar is analogous to a problem we could face in sorting application, sometimes we have to rearrange the blocks in a disk so we can scan the blocks repeatedly in certain order.  If the disk is full, then we have to rearrange the blocks in-place. Loading one block into memory is to park one car in the extra spot.

This issue is also related to index-based sort problem, that is if the data sort we need to sort is big, in stead of sorting the data, we index the record then sort the indices in stead.

The basic in-place array rearrangement operation is called rotation. We can define a rotation operation at index i like this:

input: array[i], 3, 2, 1, n-1, ..., 0

int startPos = i;

int next_value = array[startPos];

while( startPos ! = next_value ){
       int next_index = next_value;
       next_value = array[next_index];

       array[next_index] = startPos;
       startPos  = next_index;

       if(next_index == i)
              break;
}

One thing we need to improve above is to label the item which we already process, we can simply do negation operation on it. Here is the code:

public static void circleArrange(int[] array){

for(int i=0; i<array.length; i++){

if(array[i]<0) //negative item is already moved

continue;

int startPos = i;

int next_value = array[startPos];

while( startPos != next_value ){

int next_index = next_value;

next_value = array[next_index];

array[next_index] = (startPos + 1) * -1; //mark it negative 

startPos  = next_index;

if(next_index == i)

break;

}

}

for(int i = 0; i< array.length; i++){

if(array[i]<0)

array[i] = array[i]*-1 -1;

}

}