CODEWITHSUNDEEP
javasorting
mohamed Shawky
mohamed Shawky

Reputation: 29

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

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:

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

Upvotes: 0

Views: 728

Answers (2)

Enrico Giurin
Enrico Giurin

Reputation: 2273

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

Upvotes: 0

Maurice Perry
Maurice Perry

Reputation: 9651

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

Upvotes: 1

Related Questions