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 /**
19 * Codevorlage zu RecursiveAction für die Sortierung eines int-Arrays.
20 */
21 public final class QuicksortRecursive {
22 /**
23 * Public method exposed to client, sorts given array using Sort
24 * Algorithm in Java.
25 *
26 * @param array input array.
27 */
28 public static void quicksort(int[] array) {
29 QuicksortRecursive.quicksort(array, 0, array.length - 1);
30 }
31
32 /**
33 * Recursive quicksort logic.
34 *
35 * @param array input array.
36 * @param startIdx start index of the array.
37 * @param endIdx end index of the array.
38 */
39 public static void quicksort(int[] array, int startIdx, int endIdx) {
40 if (startIdx < endIdx) {
41 final int partitionIndex = partition(array, startIdx, endIdx);
42
43 quicksort(array, startIdx, partitionIndex - 1);
44 quicksort(array, partitionIndex + 1, endIdx);
45 }
46 }
47
48 /**
49 * Divides array from pivot, left side contains elements less than Pivot
50 * while right side contains elements greater than pivot.
51 *
52 * @param array array to partitioned.
53 * @param left lower bound of the array.
54 * @param right upper bound of the array.
55 * @return the partition index.
56 */
57 public static int partition(int[] array, int left, int right) {
58 final int pivot = array[right];
59
60 int i = left - 1;
61
62 for (int j = left; j < right; j++) {
63 if (array[j] <= pivot) {
64 i++;
65 exchange(array, i, j);
66 }
67 }
68
69 exchange(array, i + 1, right);
70
71 return i + 1;
72 }
73
74 private static void exchange(final int[] array, final int i, final int j) {
75 final int temp = array[i];
76 array[i] = array[j];
77 array[j] = temp;
78 }
79 }