4

I am trying to sort an ArrayList using a predefined array of indices. My current example uses a copy of the original ArrayList for sorting and therefore is not scalable for ArrayLists of larger objects

package sortExample;

import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;

public class sortExample {

    public static void main(String[] args) {

        String [] str = new String[] {"a","b","c","d"};
        ArrayList<String> arr1 = new ArrayList<String>(Arrays.asList(str));

        int [] indices = {3,1,2,0};

        ArrayList<String> arr2 = new ArrayList(arr1.size());

        for (int i = 0; i < arr1.size(); i++) {
          arr2.add("0");
        }

        int arrIndex = 0;
        for (int i : indices){
            String st = arr1.get(arrIndex);
            arr2.set(i, st); 
            arrIndex++;
        }

      System.out.println(arr1.toString());
      System.out.println(arr2.toString());
    }

}
Improve this question
7
  • what's your question? it's a bit complicated how you do it but it works...... Commented Nov 19, 2015 at 11:31
  • Is it possible to sort the ArrayList arr1 using an index array without creating the copy arr2 ? Commented Nov 19, 2015 at 11:35
  • Why You don't just use Collections.sort()? Commented Nov 19, 2015 at 11:45
  • 2
    You don't have to worry about the second list! It will only hold references to the already existing objects and therefore it's size is independant from the object's size! Commented Nov 19, 2015 at 12:45
  • @VDanyliuk In this case, to use Collections.sort(), it would be necessary to include the list of indices in the objects to be sorted. Commented Nov 19, 2015 at 15:47

4 Answers 4

Reset to default
2

For reusing same data, please see my solution:

public static void main(String[] args) {

    String[] strs = new String[]{"a", "b", "c", "d"};
    int[] indices = {3, 1, 2, 0};

    String tmp;
    for (int i = 0; i < strs.length; i++) {
        if (i != indices[i]) {
            tmp = strs[i];
            strs[i] = strs[indices[i]];
            strs[indices[i]] = tmp;

            indices[indices[i]] = indices[i];
            indices[i] = i;
        }
    }

    for (int i : indices) {
        System.out.print(i + " ");
    }
    System.out.println();
    for (String str : strs) {
        System.out.print(str + " ");
    }
}

Output is:

0 1 2 3
d b c a

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

@scs - reordering an array in place according to an array of indices is going to be more complex, than copy to another array according to an array of indices. The reorder in place time complexity is O(n), as every swap puts at least one element in place. There's somewhat faster variation of this that permutes cycles, that rotates sub-sets (or all of) the original array. For cycles of 2, it's still a swap, for cycles of 3 or more, if they exist, then the rotate method is a bit faster, temp = 1st element, 1st element = 2nd element, 2nd element = 3rd element, ... , nth element = temp.
@rcgldr I must admit that I did not do research on the reordering algorithm in depth - the O(n) complexity was sufficient for my needs.
@hsnkhrmn: I see now that the answer above uses switching and is more elegant than my example. I gave your solution a vote up. In my question I was thinking about a java function that I might have overlooked where the solution is a one-liner.
@rcgldr There will be at most n/2 switch operations only. As said compexity is O(n) here. When sorting comes into action (via comparator) at best O(nlogn). If you look for one liner code, TreeMap<Integer, String> seems like to be a solution. Add to TreeMap by real index of valu and value, when finished get values of tree. Values will be sorted by keys.
2

Alternate reorder in place based on cycles. Note that indices will be changed to {0,1,2,3}. I don't have Java installed (yet), so I converted working C++ code to what I think is proper Java syntax.

    for (int i = 0; i < arr1.size(); i++) {
        if(i != indices[i]) {
            String st = arr1.get(i);
            int t = indices[i];
            int k = i;
            int j;
            while(i != (j = indices[k])){
                arr1.set(k, arr1.get(j));
                indices[k] = k;
                k = j;
            }
            arr1.set(k, st);
            indices[k] = k;
        }
    }

For this specific case {3,1,2,0}, all this does is swap 0 and 3. The longest cycle occurs when the indices are rotated, such as {3 0 1 2}, in which case st=arr1[0], arr1[0] = arr1[3], arr[3] = arr1[2], arr1[2] = arr1[1], arr1[1] = st.

Improve this answer

Comments

1

There is a (a little bit) more simple solution:

int [] indices = {3,1,2,0};
ArrayList<String> arr2 = new ArrayList<String>();

for (int i = 0; i < arr1.size(); i++) {
    arr2.add(arr1.get(indices[i]));
}
Improve this answer

Comments

1

At the below, just use "indices" for a new array.

public class Sorting {
    public static void main(String[] args) {
         String [] str = new String[] {"a","b","c","d"};

            int [] indices = {3,1,2,0};

            String sorted [] = new String [str.length] ;
            int i = 0;
            for (String string : str) {
                sorted[indices[i]] = string;
                i++;
            }

            for (String string : sorted) {
                System.out.print(string + " ");
            }
    }
}

prints: d b c a

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.