List of Ordered pairs from unordered Pair in Java Problem statement is


  Write a method that can take an unordered list of airport pairs visited during a trip and return the list in order.

{"ITO", "KOA"}, {"SFO", "SEA"}, {"LGA", "CDG"}, {"KOA", "LGA"}, {"PDX", "ITO"}, {"SEA", "PDX"}

  
  should return:

(SFO,SEA)(SEA,PDX)(PDX,ITO)(ITO,KOA)(KOA,LGA)(LGA,CDG)



I have come up with this O(n^2) algorithm. I wanted to know if it can be done better than this:

private static void sortPairs(String[][] input)
    {

        for (int i = 0; i &lt; input.length; i++) {
            int j = 1;
            for (; j &lt; input.length; j++) {
                if (input[i][0].equals(input[j][1])) {
                    break;
                }
            }
            if (j == input.length) {
                swapPairs(i, 0, input);
                break;
            }
        }


        for (int i = 0; i &lt; input.length; i++) {
            int j = 1;
            for (; j &lt; input.length; j++) {
                if (input[i][1].equals(input[j][0])) {
                    break;
                }
            }
            if (j == input.length) {
                swapPairs(i, input.length - 1, input);
                break;
            }
        }


        for (int i = 2; i &lt; input.length - 1; i++) {
            int j = i - 1;
            for (; j &gt;= 0; j--) {
                if (input[j + 1][0].equals(input[j][1])) {
                    break;
                }
                swapPairs(j, j + 1, input);
                if (input[j + 1][0].equals(input[j][1])) {
                    break;
                }
            }

        }
    }

    private static void swapPairs(int i, int j, String[][] pairs)
    {
        String[] temp = pairs[i];
        pairs[i] = pairs[j];
        pairs[j] = temp;
    }
Welcome to corereview.se and thanks for sharing your code.

general coding

avoid odd ball solutions

In your inner and outer loop, you use different methods to declare the loop counter variable. 
The better way would have bee to find a solution that does not need this odd cod style. 

But since you decided to do so you should have placed a comment why you had to do this.

Same is with opening braces {: In your method signature, you place them at a new line, in the rest of the code you put them on the same line as the preceding statement.

THere is a hot discussion out there where to put these opening braces. 
I don't want to contribute to that argument, 
but all agree that you should decide on either one place and stick to that throughout your code.

business approach

The code does basically three things:


find start point
connect elements
reorder the input array


You chose a procedural approach to the problem. This is not bad by itself, but since Java is an object oriented language you should start looking for OO approaches.

But OOP doesn't mean to "split up" code into random classes.

The ultimate goal of OOP is to reduce code duplication, improve readability and support reuse as well as extending the code.

Doing OOP means that you follow certain principles which are (among others):


information hiding / encapsulation
single responsibility
separation of concerns
KISS (Keep it simple (and) stupid.)
DRY (Don't repeat yourself.)
"Tell! Don't ask."
Law of demeter ("Don't talk to strangers!")


A more OOish approach could look like this:

private static void sortPairs(String[][] input) {
    Map&lt;String,String&gt; routes = convertToMap(input);
    String start =  findFirstStart(routes);
    reorderArray(routes, start, input);
}
private static Map&lt;String,String&gt; convertToMap(
         String[][] input) {
    Map&lt;String,String&gt; routes = new HashMap();
    for(String[] route : input)
       routes.put(route[0][1]);
    return routes;
}
private static String findFirstStart( 
        Map&lt;String,String&gt; routes) {
     return routes.keySet()
          .stream()
          .filter(city-&gt;!routes.values().contains(city))
          .findAny()
          .get();
}
private static void reorderArray(
        Map&lt;String,String&gt; routes, 
        String start, 
        String[][] input) {
     for(int i = 0 ; i &lt; input.length) {
         String end = routes.get(start);
         input[i][0]=start;
         input[i][1]=end;
         start = end;
     }
}