-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSortSolution.java
More file actions
89 lines (75 loc) · 3.11 KB
/
Copy pathQuickSortSolution.java
File metadata and controls
89 lines (75 loc) · 3.11 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package arrays;
import java.util.Arrays;
public class QuickSortSolution {
public static void main(String[] args) {
// Test cases
testQuickSort(new int[]{6, 8, 4, 2, 7, 3, 1, 5}); // Output: [1, 2, 3, 4, 5, 6, 7, 8]
testQuickSort(new int[]{10, -5, 0, 3, 2}); // Output: [-5, 0, 2, 3, 10]
testQuickSort(new int[]{1}); // Edge case: Single element, Output: [1]
testQuickSort(new int[]{}); // Edge case: Empty array, Exception
testQuickSort(null); // Edge case: Null array, Exception
}
/**
* Sorts the given integer array in ascending order using quick sort.
*
* @param nums The integer array to be sorted.
* @return The sorted integer array.
* @throws IllegalArgumentException If the input array is null or empty.
*/
public static int[] quickSort(int[] nums) {
if (nums == null) {
throw new IllegalArgumentException("Input array cannot be null.");
}
if (nums.length == 0) {
throw new IllegalArgumentException("Input array cannot be empty.");
}
// Call the recursive quick sort function
quickSortRecursive(nums, 0, nums.length - 1);
return nums;
}
private static void quickSortRecursive(int[] nums, int low, int high) {
if (low < high) {
int partitionIndex = partition(nums, low, high);
// Recursively sort the two halves
quickSortRecursive(nums, low, partitionIndex - 1);
quickSortRecursive(nums, partitionIndex + 1, high);
}
}
private static int partition(int[] nums, int low, int high) {
int pivot = nums[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (nums[j] < pivot) {
i++;
swap(nums, i, j);
}
}
// Swap the pivot element to its correct position
swap(nums, i + 1, high);
return i + 1;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
/**
* Helper method to test the function with various inputs.
*
* @param nums The integer array to be sorted.
*/
public static void testQuickSort(int[] nums) {
System.out.println("Input Array: " + Arrays.toString(nums));
try {
int[] result = quickSort(nums);
System.out.println("Sorted Array (Quick Sort): " + Arrays.toString(result));
} catch (IllegalArgumentException e) {
System.out.println("Error: " + e.getMessage());
}
System.out.println();
}
}
/*
Algorithm Time Complexity Space Complexity Best Use Case
Merge Sort O(n log n) O(n) Stable sort, better for large datasets or datasets that require stability.
Quick Sort O(n log n) O(\log n) Faster in practice for small to medium-sized datasets, but not stable. */