Sorting strings in custom lexicographic order

Question

Sorting string array according to lexicographic order with a custom ordering (a permutation of abcdefghijklmnopqrstuvwxyz). This is the code:

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * @author sabertooth
 */
public class SortString {
    /**
     * @param args the command line arguments
     */
    private static char[] index;
    private static BufferedReader br;

    public static void main(String[] args) throws Exception {
        // TODO code application logic here
        br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());

        for (int i = 0; i < testCases; i++) {
            String dictionary = br.readLine();

            index = new char[dictionary.length()];
            index = dictionary.toCharArray();

            int set = Integer.parseInt(br.readLine());

            String[] unsortedInput = new String[set];
            String[] sortedInput = new String[set];
            for (int j = 0; j < set; j++) {
                unsortedInput[j] = br.readLine();
            }

            if (unsortedInput.length <= 1) {
                System.out.println(unsortedInput[0]);
            } else {
                // merge sort on this array
                sortedInput = mergeSort(unsortedInput);
                for (int k = 0; k < sortedInput.length; k++) {
                    System.out.println(sortedInput[k]);
                }
            }
        }
    }

    private static String[] mergeSort(String[] unsortedInput) {
        if (unsortedInput.length <= 1) {
            return unsortedInput;
        }

        String[] left;
        String[] right;
        int middle = unsortedInput.length / 2;
        if (unsortedInput.length % 2 == 0) {
            left = new String[middle];
            right = new String[middle];
        } else {
            left = new String[middle];
            right = new String[middle + 1];
        }
        System.arraycopy(unsortedInput, 0, left, 0, middle);
        System.arraycopy(unsortedInput, middle, right, 0, unsortedInput.length - middle);

        left = mergeSort(left);
        right = mergeSort(right);
        return merge(left, right);
    }

    private static String[] merge(String[] left, String[] right){
        List<String> leftList = new ArrayList<String>();
        List<String> rightList = new ArrayList<String>();
        List<String> result = new ArrayList<String>();

        leftList.addAll(Arrays.asList(left));
        rightList.addAll(Arrays.asList(right));

        while (leftList.size() > 0 || rightList.size() > 0) {
             if (leftList.size() > 0 && rightList.size() > 0) {
                // my own comparison
                if (compare(leftList.get(0), rightList.get(0)) == -1) {
                    // leftString is less than right string
                    result.add(leftList.get(0));
                    leftList = leftList.subList(1, leftList.size());
                } else
                if (compare(leftList.get(0), rightList.get(0)) == 1) {
                    //left string is greater than right string
                    result.add(rightList.get(0));
                    rightList = rightList.subList(1, rightList.size());
                } else
                if (compare(leftList.get(0), rightList.get(0)) == 0) {
                    // leftString is equal to right string
                    result.add(leftList.get(0));
                    leftList = leftList.subList(1, leftList.size());
                }
            } else
            if (leftList.size() > 0) {
                for (int i = 0; i < leftList.size(); i++) {
                    result.add(leftList.get(i));
                }
                leftList.clear();
            } else
            if (rightList.size() > 0) {
                for (int i = 0; i < rightList.size(); i++) {
                    result.add(rightList.get(i));
                }
                rightList.clear();
            }
        }
        String[] sortedInput = new String[result.size()];
        for (int i = 0; i < result.size(); i++) {
            sortedInput[i] = result.get(i);
        }
        return sortedInput;
    }

    private static int compare(String leftString, String rightString) {
        // return -1 if left string is less than right string else left string is greater than right string return 1

        int min = Math.min(leftString.length(), rightString.length());
        int response = 0;
        for (int i = 0; i < min; i++) {
            if (compareChar(leftString.charAt(i), rightString.charAt(i)) == -1) {
                response = -1;
                break;
            } else
            if (compareChar(leftString.charAt(i), rightString.charAt(i)) == 1) {
                response = 1;
                break;
            } else
            if (compareChar(leftString.charAt(i), rightString.charAt(i)) == 0) {
                response = 0;

            }
        }
        return response;
    }

    private static int compareChar(char x, char y) {
        // returns true if x < y
        int indexofx = 0;
        int indexofy = 0;
        int response = 0;
        for (int i = 0; i < index.length; i++) {
            if (index[i] == x) {
                indexofx = i;
            }
            if (index[i] == y) {
                indexofy = i;
            }
        }
        if (indexofx < indexofy) {
            response = -1;
        } else
        if (indexofx > indexofy) {
            response = 1;
        } else
        if (indexofx == indexofy) {
            response = 0;
        }
        return response;
    }
}

The problem is when I run this for some of the inputs the output is correct and for other the output is not correct. I have been debugging it but not able to find the bug.

EDITS:

Adriana was playing with the English alphabet. When she was done playing with the alphabet, she realised that she had jumbled up the positions of the letters. Now, given a set of words, she wondered what would be the dictionary ordering of these words based on the new alphabet ordering which she made.

In other words, given a permutation of the English alphabet, E and a set of words S, you need to output the lexicographical ordering of the words in the set S based on the new alphabet, E.

Input:

The first line will contain a single integer, T, denoting the number of test cases. T lines follow.

For each test case:

The first line will contain a string, E, the new alphabet ordering, which will be a permutation of abcdefghijklmnopqrstuvwxyz

The next line will contain a single integer M, the size of the set S. S lines follow, each containing a single word, containing lowercase latin characters.

Output: for each test case, output S lines, each line containing one word from the set S, ordered lexicographically.

Constraints

1 <= T <= 1000 
1 <= M <= 100 
1 <= |W| <= 50

Sample Input:

2
abcdefghijklmnopqrstuvwxyz
2
aa
bb
bacdefghijklmnopqrstuvwxyz
2
aa
bb

Sample Output:

aa
bb
bb
aa

Answer 1

The string comparison function is incorrect: you only compare on the shortest length, returning 0 for A and AB. When a string is a prefix of the other, you should compare the lengths.

The character comparison function is unnecessarily complicated and considers all characters outside of index to be identical to the first letter in index. You should only reorder lowercase letters according to the index string.

    private static int compare(String leftString, String rightString) {
        // return -1 if left string is less than right string else left string is greater than right string return 1

        int len1 = leftString.length();
        int len2 = rightString.length();
        int min = Math.min(len1, len2);
        for (int i = 0; i < min; i++) {
            int cmp = compareChar(leftString.charAt(i), rightString.charAt(i));
            if (cmp != 0) {
                return cmp;
            }
        }
        return len1 == len2 ? 0 : (len1 < len2 ? -1 : 1);
    } 

    /* lexicographical comparison with custom order for lowercase letters */
    private static int compareChar(char x, char y) {
        if (x == y)
            return 0;
        int indexofx = index.indexOf(x);
        int indexofy = index.indexOf(y);
        if (indexofx >= 0) {
            x = (char)('a' + indexofx);
        }
        if (indexofy >= 0) {
            y = (char)('a' + indexofy);
        }
        // if index is a permutation of the lowercase letters,
        // we can assume x != y 
        return x < y ? -1 : 1;
    }
}

Answer 2

This should work for any given permutation. Why use custom sort function (unless you have to sort custom class objects) when java provide you inbuilt one?

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;

class TestClass {
    public static ArrayList<String> res;
    static void sort(String dictionary, String[] words, int count){
        String eng = "abcdefghijklmnopqrstuvwxyz";
        String[] tempArray = new String[count];
        String temp="";
        char ch;
        int index, m=0;
        for(String x : words){
            temp = "";
            for(int l =0 ;l<x.length(); l++){
                ch = x.charAt(l);
                index = dictionary.indexOf(ch);
                temp = temp + eng.charAt(index);
            }
            tempArray[m] = temp;
            m++;
        }

        Arrays.sort(tempArray);
        for(String x : tempArray){
            temp = "";
            for(int l =0 ;l<x.length(); l++){
                ch = x.charAt(l);
                index = eng.indexOf(ch);
                temp = temp + dictionary.charAt(index);
            }
            res.add(temp);

        }
    }
    public static void main(String args[] ) throws Exception {
        res = new ArrayList<String>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int N = Integer.parseInt(line);
        int count;
        String [] words;
        String dictionary;
        for (int i = 0; i < N; i++) {
            dictionary = br.readLine();
            count = Integer.parseInt(br.readLine());
            words = new String[count];
            for(int j =0; j<count; j++){
                words[j] = br.readLine();
            }
            sort(dictionary,words,count);
        }
        for(String x : res)
        System.out.println(x);
    }
}

I guess this is some sort of algorithmic challenge. is it? :)