]>
Commit | Line | Data |
---|---|---|
1d09f67e TL |
1 | /* |
2 | * Licensed to the Apache Software Foundation (ASF) under one or more | |
3 | * contributor license agreements. See the NOTICE file distributed with | |
4 | * this work for additional information regarding copyright ownership. | |
5 | * The ASF licenses this file to You under the Apache License, Version 2.0 | |
6 | * (the "License"); you may not use this file except in compliance with | |
7 | * the License. You may obtain a copy of the License at | |
8 | * | |
9 | * http://www.apache.org/licenses/LICENSE-2.0 | |
10 | * | |
11 | * Unless required by applicable law or agreed to in writing, software | |
12 | * distributed under the License is distributed on an "AS IS" BASIS, | |
13 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
14 | * See the License for the specific language governing permissions and | |
15 | * limitations under the License. | |
16 | */ | |
17 | ||
18 | package org.apache.arrow.algorithm.sort; | |
19 | ||
20 | import org.apache.arrow.vector.BaseFixedWidthVector; | |
21 | import org.apache.arrow.vector.IntVector; | |
22 | import org.apache.arrow.vector.ValueVector; | |
23 | ||
24 | /** | |
25 | * Insertion sorter. | |
26 | */ | |
27 | class InsertionSorter { | |
28 | ||
29 | /** | |
30 | * Sorts the range of a vector by insertion sort. | |
31 | * | |
32 | * @param vector the vector to be sorted. | |
33 | * @param startIdx the start index of the range (inclusive). | |
34 | * @param endIdx the end index of the range (inclusive). | |
35 | * @param buffer an extra buffer with capacity 1 to hold the current key. | |
36 | * @param comparator the criteria for vector element comparison. | |
37 | * @param <V> the vector type. | |
38 | */ | |
39 | static <V extends BaseFixedWidthVector> void insertionSort( | |
40 | V vector, int startIdx, int endIdx, VectorValueComparator<V> comparator, V buffer) { | |
41 | comparator.attachVectors(vector, buffer); | |
42 | for (int i = startIdx; i <= endIdx; i++) { | |
43 | buffer.copyFrom(i, 0, vector); | |
44 | int j = i - 1; | |
45 | while (j >= startIdx && comparator.compare(j, 0) > 0) { | |
46 | vector.copyFrom(j, j + 1, vector); | |
47 | j = j - 1; | |
48 | } | |
49 | vector.copyFrom(0, j + 1, buffer); | |
50 | } | |
51 | } | |
52 | ||
53 | /** | |
54 | * Sorts the range of vector indices by insertion sort. | |
55 | * | |
56 | * @param indices the vector indices. | |
57 | * @param startIdx the start index of the range (inclusive). | |
58 | * @param endIdx the end index of the range (inclusive). | |
59 | * @param comparator the criteria for vector element comparison. | |
60 | * @param <V> the vector type. | |
61 | */ | |
62 | static <V extends ValueVector> void insertionSort( | |
63 | IntVector indices, int startIdx, int endIdx, VectorValueComparator<V> comparator) { | |
64 | for (int i = startIdx; i <= endIdx; i++) { | |
65 | int key = indices.get(i); | |
66 | int j = i - 1; | |
67 | while (j >= startIdx && comparator.compare(indices.get(j), key) > 0) { | |
68 | indices.set(j + 1, indices.get(j)); | |
69 | j = j - 1; | |
70 | } | |
71 | indices.set(j + 1, key); | |
72 | } | |
73 | } | |
74 | } |