001 /*
002 * Java Genetic Algorithm Library (jenetics-3.5.0).
003 * Copyright (c) 2007-2016 Franz Wilhelmstötter
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 *
017 * Author:
018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
019 */
020 package org.jenetics.internal.util;
021
022 import static org.jenetics.internal.util.array.swap;
023
024 /**
025 * Implementations of this class doesn't sort the given array directly, instead
026 * an index lookup array is returned which allows to access the array in
027 * an sorted order. The arrays are sorted in descending order.
028 *
029 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
030 * @since 3.0
031 * @version 3.0
032 */
033 public abstract class IndexSorter {
034
035 // This value has been chosen after JMH benchmarking.
036 // Benchmark Mode Samples Score Score error Units
037 // o.j.i.u.IndexSorterPerf.heapSort160 avgt 14 5560.895 80.158 ns/op
038 // o.j.i.u.IndexSorterPerf.heapSort250 avgt 14 9516.441 119.648 ns/op
039 // o.j.i.u.IndexSorterPerf.heapSort320 avgt 14 12722.461 103.487 ns/op
040 // o.j.i.u.IndexSorterPerf.heapSort80 avgt 14 2473.058 27.884 ns/op
041 // o.j.i.u.IndexSorterPerf.insertionSort160 avgt 14 10877.158 550.338 ns/op
042 // o.j.i.u.IndexSorterPerf.insertionSort250 avgt 14 25731.100 925.196 ns/op
043 // o.j.i.u.IndexSorterPerf.insertionSort320 avgt 14 41864.108 1801.247 ns/op
044 // o.j.i.u.IndexSorterPerf.insertionSort80 avgt 14 2643.726 165.315 ns/op
045 //private static final int INSERTION_SORT_THRESHOLD = 80;
046 private static final int INSERTION_SORT_THRESHOLD = 80;
047
048 static final IndexSorter INSERTION_SORTER = new InsertionSorter();
049 static final IndexSorter HEAP_SORTER = new HeapSorter();
050
051 /**
052 * This method must be implemented by the different sorting algorithms.
053 *
054 * @param array the array to sort
055 * @param indexes the index lookup array -
056 * ∀ i ∈ [0, N): index[i] = i
057 * @return the given {@code indexes} which is now "sorted"
058 */
059 abstract int[] sort(final double[] array, final int[] indexes);
060
061 /**
062 * Return an new sorted index lookup array. The given array is not touched.
063 *
064 * @param array the array to sort.
065 * @return the index lookup array
066 */
067 public static int[] sort(final double[] array) {
068 final IndexSorter sorter = array.length < INSERTION_SORT_THRESHOLD
069 ? INSERTION_SORTER
070 : HEAP_SORTER;
071
072 return sorter.sort(array, indexes(array.length));
073 }
074
075 static int[] indexes(final int length) {
076 final int[] indexes = new int[length];
077 for (int i = length; --i >= 0;) {
078 indexes[i] = i;
079 }
080 return indexes;
081 }
082
083 @Override
084 public String toString() {
085 return getClass().getSimpleName();
086 }
087
088 }
089
090 /**
091 * Heap sort implementation.
092 */
093 final class HeapSorter extends IndexSorter {
094
095 @Override
096 int[] sort(final double[] array, final int[] indexes) {
097 // Heapify
098 for (int k = array.length/2; k >= 0; --k) {
099 sink(array, indexes, k, array.length);
100 }
101
102 // Sort down.
103 for (int i = array.length; --i >= 1;) {
104 swap(indexes, 0, i);
105 sink(array, indexes, 0, i);
106 }
107
108 return indexes;
109 }
110
111 private static void sink(
112 final double[] array,
113 final int[] indexes,
114 final int start,
115 final int end
116 ) {
117 int m = start;
118 while (2*m < end) {
119 int j = 2*m;
120 if (j < end - 1 && array[indexes[j]] > array[indexes[j + 1]]) ++j;
121 if (array[indexes[m]] <= array[indexes[j]]) break;
122 swap(indexes, m, j);
123 m = j;
124 }
125 }
126
127 }
128
129 /**
130 * Insertion sort implementation.
131 */
132 final class InsertionSorter extends IndexSorter {
133
134 @Override
135 int[] sort(final double[] array, final int[] indexes) {
136 for (int i = 1, n = array.length; i < n; ++i) {
137 int j = i;
138 while (j > 0) {
139 if (array[indexes[j - 1]] < array[indexes[j]]) {
140 swap(indexes, j - 1, j);
141 } else {
142 break;
143 }
144 --j;
145 }
146 }
147
148 return indexes;
149 }
150
151 }
|