View Javadoc
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.mergesort;
17  
18  import java.util.Arrays;
19  import java.util.HashSet;
20  import java.util.Set;
21  import java.util.concurrent.RecursiveAction;
22  
23  /**
24   * Codebeispiel zu RecursiveAction für die Sortierung eines int-Arrays.
25   */
26  public final class MergesortTask extends RecursiveAction {
27  
28      private final int threshold;
29      private final int[] array;
30      private final int min;
31      private final int max;
32  
33      /**
34       * Erzeugt einen Array-Sortier Task.
35       *
36       * @param array Interger-Array.
37       */
38      public MergesortTask(final int[] array) {
39          this(array, 0, array.length);
40      }
41  
42      public MergesortTask(final int[] array, final int threshold) {
43          this(array, 0, array.length, threshold);
44      }
45  
46      private MergesortTask(final int[] array, final int min, final int max) {
47          this.array = array;
48          this.min = min;
49          this.max = max;
50          this.threshold = 50;
51      }
52  
53      private MergesortTask(final int[] array, final int min, final int max, final int threshold) {
54          this.array = array;
55          this.min = min;
56          this.max = max;
57          this.threshold = threshold;
58      }
59  
60      @Override
61      protected void compute() {
62          if (max - min < threshold) {
63              InsertionSort.exec(array, min, max);
64          } else {
65              final int mid = min + (max - min) / 2;
66              invokeAll(new MergesortTask(array, min, mid), new MergesortTask(array, mid, max));
67              merge(min, mid, max);
68          }
69      }
70  
71      private void merge(final int min, int mid, int max) {
72          // vordere Hälfte von array in Hilfsarray buf kopieren
73          int[] buf = Arrays.copyOfRange(array, min, mid);
74          int i = 0;
75          int j = min;
76          int k = mid;
77          while (i < buf.length) {
78              // jeweils das nächstgrösste Element zurückkopieren
79              // bei k == max, Rest von buf zurückkopieren, falls vorhanden
80              if (k == max || buf[i] < array[k]) {
81                  array[j] = buf[i];
82                  i++;
83              } else {
84                  array[j] = array[k];
85                  k++;
86              }
87              j++;
88          }
89      }
90  }