secretest
BAN USERHere is a simple recursive solution that does not modify the ordering array, and runs in O(n)
I borrowed some test case arrays from other answers, i hope that is ok:
import java.util.Arrays;
public class ImposedSort {
public static void main(String[] args) {
int[] input = {17,5,1,9};
int[] order = {3,2,4,1};
// int[] input = {30,40,10,20,70,50,60,100,80,90};
// int[] order = {3,4,1,2,7,5,6,10,8,9};
//int[] arr = { 5, 12, 14, 27, 3, 2, 13, 17, 7, 21 };
//int[] index = { 4, 7, 3, 10, 8, 2, 5, 9, 6, 1 };
System.out.println("Unsorted Input: "+ Arrays.toString(input));
System.out.println("Ordering: "+ Arrays.toString(order));
recursiveImposedSort(input, order, 0);
System.out.println("Sorted Input: "+ Arrays.toString(input));
System.out.println("Ordering: "+ Arrays.toString(order));
}
static void recursiveImposedSort(int[] input, int[] order, int k){
if ( k==input.length){
return;
}
int orderK = order[k];
int inputK = input[k];
recursiveImposedSort(input, order, k + 1);
input[orderK-1]=inputK;
}
}
My first instinct was recursive as well -
- secretest August 21, 2014I just submitted a solution that works like this.
The key is to 'remember' the values you need before making the recursive call. That way you dont have to worry about the values changing later, and when the recursion bubbles back up, you just set the value you were remembering in to its correct location.. (assuming my code does in fact work ;) )