1 /*
2 * Copyright 2024 Hochschule Luzern Informatik.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package ch.hslu.exercises.sw11.ex1.n41.array.sort;
17
18 import java.util.Arrays;
19 import java.util.concurrent.RecursiveAction;
20
21 /**
22 * Codebeispiel zu RecursiveAction für die Sortierung eines int-Arrays.
23 */
24 public final class SortTask extends RecursiveAction {
25
26 private static final int THRESHOLD = 5;
27 private final int[] array;
28 private final int min;
29 private final int max;
30
31 /**
32 * Erzeugt einen Array-Sortier Task.
33 *
34 * @param array Interger-Array.
35 */
36 public SortTask(final int[] array) {
37 this(array, 0, array.length);
38 }
39
40 private SortTask(final int[] array, final int min, final int max) {
41 this.array = array;
42 this.min = min;
43 this.max = max;
44 }
45
46 @Override
47 protected void compute() {
48 if (max - min < THRESHOLD) {
49 sortSequentially(min, max);
50 } else {
51 final int mid = min + (max - min) / 2;
52 invokeAll(new SortTask(array, min, mid), new SortTask(array, mid, max));
53 merge(min, mid, max);
54 }
55 }
56
57 private void sortSequentially(final int min, final int max) {
58 //Arrays.sort(array, min, max);
59 //Arrays.parallelSort(array, min, max);
60 InsertionSort.exec(array, min, max);
61 }
62
63 private void merge(final int min, final int mid, final int max) {
64 // vordere Hälfte von array in Hilfsarray buf kopieren
65 int[] buf = Arrays.copyOfRange(array, min, mid);
66 int i = 0;
67 int j = min;
68 int k = mid;
69 while (i < buf.length) {
70 // jeweils das nächstgrösste Element zurückkopieren
71 // bei k == max, Rest von buf zurückkopieren, falls vorhanden
72 if (k == max || buf[i] < array[k]) {
73 array[j] = buf[i];
74 i++;
75 } else {
76 array[j] = array[k];
77 k++;
78 }
79 j++;
80 }
81 }
82 }