sort array of characters in the order of occurrence within a string

Question

If I have an array of characters filled with characters, and I have a String initialized with some initial value, then how can I make sure that the characters in the array are sorted in the order of occurents of how they appear within the string.

You can make the following additional assumptions:

unused characters should appear at the end in their original order.
if multiple occurrences of the same character occur within the array, they can refer to the same occurrence within the string.

Example, assume following two initialized variables:

char [] arr= new char[5] { 'a', 'd', 'v', 'd', 'j' };
String str = "dad";

Then the expected result would be that the variable arr would have sorted the characters as follows:

{ 'd', 'a', 'd', 'v', 'j' }

For what ultimate goal? What would be the purpose of doing this? Showing your coding attempt may answer these questions but for some reason, I doubt it. — DevilsHnd - 退職した, Jan 17 '17 at 06:17
yes i want the code i mean that if we have char [ ] arr = new arr[5] and have values {a, d, v, d, j} according to "dad" the sorted array will be {d, a, d, v, j}@ScaryWombat @Maurice Perry — mohamed Shawky, Jan 17 '17 at 06:19
[Questions asking for homework](http://stackoverflow.com/help/on-topic) help must include a summary of the work you've done so far to solve the problem, and a description of the difficulty you are having solving it. — YoYo, Jan 17 '17 at 06:42
An [Open letter to students with homework problems](http://meta.softwareengineering.stackexchange.com/q/6166/167417) for students and those who might answer them — AxelH, Jan 17 '17 at 06:58
What would be the expected result if `char[] arr = { 'a', 'd', 'v', 'd', 'j', 'd' }`. — SubOptimal, Jan 17 '17 at 10:42

Maurice Perry · Accepted Answer · 2017-01-17T07:27:33.227

Here is a possible solution:

public static void main(String[] args) throws IOException  {
    char [] arr= { 'a', 'd', 'v', 'd', 'j' };
    String str = "dad";
    int pos = 0;
    for (char c: str.toCharArray()) {
        int i = locate(c, arr, pos);
        if (i >= 0) {
            char x = arr[pos];
            arr[pos] = arr[i];
            arr[i] = x;
            ++pos;
        }
    }
    System.out.println(toString(arr));
}

private static int locate(char c, char[] arr, int start) {
    for (int i = start; i < arr.length; ++i) {
        if (arr[i] == c) {
            return i;
        }
    }
    return -1;
}

UPDATE: the toString method

private static String toString(char[] arr) {
    StringBuilder buf = new StringBuilder();
    buf.append('{');
    boolean first = true;
    for (char c: arr) {
        if (first) {
            first = false;
        } else {
            buf.append(',');
        }
        buf.append(c);
    }
    buf.append('}');
    return buf.toString();
}

UPDATE 2: to preserve the order of the elements that are not in the string.

        if (i >= 0) {
            char x = arr[i];
            for (int k = pos; k < i; ++k) {
                char y = arr[k];
                arr[k] = x;
                x = y;
            }
            arr[i] = x;
            ++pos;
        }

Where does the `toString` come from? Did you mean to use `Arrays.toString()` ? — Sid, Jan 17 '17 at 06:53
Ok, you don't need to do that, `Arrays.toString()` will take care of it. The solution works, btw. I would try and find a functional solution with no mutations. Just out of curiosity. Thanks. — Sid, Jan 17 '17 at 06:56
If I right understand the requirement of the OP, then your solution is wrong for input `{'a','d','v','x','d','j'}`. The output should be `{d,a,d,v,x,j}` instead of `{d,a,d,x,v,j}`. — SubOptimal, Jan 17 '17 at 07:44

score 0 · Answer 2 · edited May 23 '17 at 11:53

I wrote this solution which (partially) solves the problem.

    String source = "pippo";
    Comparator<Character> comparator = new Comparator<Character>() {

        private int countChar(String s, char c) {
            return s.length() - s.replace(Character.toString(c), "").length();
        }
        @Override
        public int compare(Character o1, Character o2) {
            return countChar(source, o2) - countChar(source, o1);
        }
    };
    Character[] charObjectArray = source.chars().mapToObj(c -> (char)c).toArray(Character[]::new);
    Arrays.sort(charObjectArray , comparator);

What is still missing is the implementation of this feature:

if multiple occurrences of the same character occur within the array, they can refer to the same occurrence within the string.

The method to count occurrences of char in a String was found here: https://stackoverflow.com/a/8910767/379173

sort array of characters in the order of occurrence within a string

2 Answers2