Problem:
The input is a sequence x1,x2,…,xn of integers in an arbitrary order, and another sequence a1,a2,..,an of distinct integers from 1 to n (namely a1,a2,…,an is a permutation of 1, 2,…, n). Both sequences are given as arrays. Design an 0(n logn) algorithm to order the first sequence according to the order imposed by the permutation. In other words, for each i, Xi should appear in the position given in ai.
For example, if x = 17, 5, 1,9, and a = 3, 2, 4, 1, then the outcome should be x = 9, 5, 17, 1. The algorithm should be in-place, so you cannot use an additional array.
Take the following analysis:
I use the seq[] to store the position indicating where the element should put. After visited a element i, I change the seq[i] to negative. By checking if the seq[i] is negative, I can know if this element has ever been visited or no.
Code:
- public class SortAccordingToAnArray {
- public static void main(String[] args) {
- int[] arr = { 5, 12, 14, 27, 3, 2, 13, 17, 7, 21 };
- int[] index = { 3, 6, 2, 9, 7, 1, 4, 8, 5, 10 };
- System.out.println(“Values: ” + Arrays.toString(arr));
- System.out.println(” Index: ” + Arrays.toString(index));
- putRightPosition(arr, index);
- System.out.println(“Values: ” + Arrays.toString(arr));
- }
- public static void putRightPosition(int[] num, int[] seq){
- for(int i=0;i
- if(seq[i]<0){
- continue;
- }
- int curr_value = num[i];
- int next_pos = seq[i]-1;
- seq[i] = -seq[i];
- while(true){
- int tmp = num[next_pos];
- num[next_pos] = curr_value;
- curr_value = tmp;
- tmp = next_pos;
- next_pos = seq[next_pos]-1;
- if(next_pos<0){
- break;
- }
- seq[tmp] = -seq[tmp];
- }//while
- }//for
- }
- }