Thursday, March 5, 2015

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;
}
}


2 comments:

  1. In your while loop, you have 2 condition judges to quit the loop:
    startPos!=next_value
    next_index==i.
    I think you can reduce to one.

    ReplyDelete
    Replies
    1. yes, you may be right. also the code is prune to input error, for example, if input is 1, 2, 0, 4, 1. Let me work on it today. I will also work on the circle sort algorithm.

      Delete