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.ex2.quicksort;
17  
18  import java.util.concurrent.RecursiveAction;
19  
20  /**
21   * Codevorlage zu RecursiveAction für die Sortierung eines int-Arrays.
22   */
23  public final class QuicksortTask extends RecursiveAction {
24  
25      private final int threshold;
26      private final int[] array;
27      private final int min;
28      private final int max;
29  
30      /**
31       * Erzeugt einen Array-Sortier Task.
32       *
33       * @param array Interger-Array.
34       */
35      public QuicksortTask(int[] array, final int threshold) {
36          this(array, 0, array.length - 1, threshold);
37      }
38  
39      private QuicksortTask(final int[] array, final int min, final int max, final int threshold) {
40          this.array = array;
41          this.min = min;
42          this.max = max;
43          this.threshold = threshold;
44      }
45  
46      private static void insertionSort(int[] array, int left, int right) {
47          for (int i = left + 1; i <= right; i++) {
48              final int key = array[i];
49              int j = i - 1;
50              while (j >= left && array[j] > key) {
51                  array[j + 1] = array[j];
52                  j--;
53              }
54              array[j + 1] = key;
55          }
56      }
57  
58      @Override
59      protected void compute() {
60          if (max > min) {
61              if (max - min < threshold) {
62                  insertionSort(array, min, max);
63              } else {
64                  final int pivotIndex = QuicksortRecursive.partition(array, min, max);
65                  invokeAll(new QuicksortTask(array, min, pivotIndex - 1, threshold), new QuicksortTask(array, pivotIndex + 1, max, threshold));
66              }
67          }
68      }
69  
70  }