Fix dependency sorting in CoordinatorLayout

For our purposes we need every view to be compared against
each other when sorting. Collections.sort() is stable and
efficient, and thus doesn't guarantee that, therefore we now
need to use a selection sort which does guarantee that.

It is less efficient, but it is much better than removing
all of the sorting and doing a O(N^2) loop in every draw.

BUG: 24126029
Change-Id: Ida34244d62b9c7519b4cded3ab23bef95a01f1f0
diff --git a/design/src/android/support/design/widget/CoordinatorLayout.java b/design/src/android/support/design/widget/CoordinatorLayout.java
index 617b307..2ca18c3 100644
--- a/design/src/android/support/design/widget/CoordinatorLayout.java
+++ b/design/src/android/support/design/widget/CoordinatorLayout.java
@@ -566,7 +566,9 @@
             for (int i = 0; i < childCount; i++) {
                 mDependencySortedChildren.add(getChildAt(i));
             }
-            Collections.sort(mDependencySortedChildren, mLayoutDependencyComparator);
+            // We need to use a selection sort here to make sure that every item is compared
+            // against each other
+            selectionSort(mDependencySortedChildren, mLayoutDependencyComparator);
         }
     }
 
@@ -2637,4 +2639,37 @@
                     }
                 };
     }
+
+    private static void selectionSort(final List<View> list, final Comparator<View> comparator) {
+        if (list == null || list.size() < 2) {
+            return;
+        }
+
+        final View[] array = new View[list.size()];
+        list.toArray(array);
+        final int count = array.length;
+
+        for (int i = 0; i < count; i++) {
+            int min = i;
+
+            for (int j = i + 1; j < count; j++) {
+                if (comparator.compare(array[j], array[min]) < 0) {
+                    min = j;
+                }
+            }
+
+            if (i != min) {
+                // We have a different min so swap the items
+                final View minItem = array[min];
+                array[min] = array[i];
+                array[i] = minItem;
+            }
+        }
+
+        // Finally add the array back into the collection
+        list.clear();
+        for (int i = 0; i < count; i++) {
+            list.add(array[i]);
+        }
+    }
 }