source: trunk/CrossPare/src/de/ugoe/cs/cpdp/util/SortUtils.java

Last change on this file was 135, checked in by sherbold, 8 years ago
  • code documentation and formatting
  • Property svn:mime-type set to text/plain
File size: 4.9 KB
Line 
1
2package de.ugoe.cs.cpdp.util;
3
4/**
5 * <p>
6 * Utility functions for sorting.
7 * </p>
8 *
9 * @author Steffen Herbold
10 */
11public class SortUtils {
12
13    /**
14     * <p>
15     * Implements a quick sort that sorts an index set together with the array.
16     * </p>
17     *
18     * @param main
19     *            the array that is sorted
20     * @param index
21     *            the index set for the array
22     */
23    public static <T extends Comparable<T>> void quicksort(T[] main, int[] index) {
24        quicksort(main, index, 0, index.length - 1, false);
25    }
26
27    /**
28     * <p>
29     * Implements a quick sort that sorts an index set together with the array.
30     * </p>
31     *
32     * @param main
33     *            the array that is sorted
34     * @param index
35     *            the index set for the array
36     * @param descending
37     *            defines the sorting order
38     */
39    public static <T extends Comparable<T>> void quicksort(T[] main,
40                                                           int[] index,
41                                                           boolean descending)
42    {
43        quicksort(main, index, 0, index.length - 1, descending);
44    }
45
46    /**
47     * <p>
48     * internal quicksort implementation
49     * </p>
50     *
51     * @param main
52     *            the array that is sorted
53     * @param index
54     *            the index set for the array
55     * @param left
56     *            defines the current partition
57     * @param right
58     *            defines the current partition
59     * @param descending
60     *            defines the sorting order
61     */
62    private static <T extends Comparable<T>> void quicksort(T[] main,
63                                                            int[] index,
64                                                            int left,
65                                                            int right,
66                                                            boolean descending)
67    {
68        if (right <= left)
69            return;
70        int i = partition(main, index, left, right, descending);
71        quicksort(main, index, left, i - 1, descending);
72        quicksort(main, index, i + 1, right, descending);
73    }
74
75    /**
76     * <p>
77     * internal partitioning of the quicksort implementation
78     * </p>
79     *
80     * @param main
81     *            the array that is sorted
82     * @param index
83     *            the index set for the array
84     * @param left
85     *            defines the current partition
86     * @param right
87     *            defines the current partition
88     * @param descending
89     *            defines the sorting order
90     */
91    private static <T extends Comparable<T>> int partition(T[] main,
92                                                           int[] index,
93                                                           int left,
94                                                           int right,
95                                                           boolean descending)
96    {
97        int i = left - 1;
98        int j = right;
99        while (true) {
100            while (compare(main[++i], main[right], descending)) // find item on left to swap
101            ; // a[right] acts as sentinel
102            while (compare(main[right], main[--j], descending)) // find item on right to swap
103                if (j == left)
104                    break; // don't go out-of-bounds
105            if (i >= j)
106                break; // check if pointers cross
107            swap(main, index, i, j); // swap two elements into place
108        }
109        swap(main, index, i, right); // swap with partition element
110        return i;
111    }
112
113    /**
114     * <p>
115     * helper function for comparator evaluation
116     * </p>
117     *
118     * @param x
119     *            first element that is compared
120     * @param y
121     *            second element that is compared
122     * @param descending
123     *            defines the sorting order
124     * @return true if x is larger than y and descending is true or y is larger than x and
125     *         descending is false
126     */
127    private static <T extends Comparable<T>> boolean compare(T x, T y, boolean descending) {
128        if (descending) {
129            return x.compareTo(y) > 0;
130        }
131        else {
132            return x.compareTo(y) < 0;
133        }
134    }
135
136    /**
137     * <p>
138     * swaps to elements
139     * </p>
140     *
141     * @param main
142     *            the array that is sorted
143     * @param index
144     *            the index set for the array
145     * @param i
146     *            index of the first element
147     * @param j
148     *            index of the second element
149     */
150    private static <T extends Comparable<T>> void swap(T[] main, int[] index, int i, int j) {
151        T tmp = main[i];
152        main[i] = main[j];
153        main[j] = tmp;
154        int b = index[i];
155        index[i] = index[j];
156        index[j] = b;
157    }
158}
Note: See TracBrowser for help on using the repository browser.