-
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSort.java
More file actions
111 lines (78 loc) · 2.64 KB
/
Copy pathQuickSort.java
File metadata and controls
111 lines (78 loc) · 2.64 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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package Sorting;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5,3,2,1,4};
// Sort the complete array
sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
static void sort(int[] arr, int low, int high) {
// Base Condition:
// If the subarray has 0 or 1 element,
// it is already sorted.
if (low >= high)
return;
// Choose the middle element as pivot.
// Pivot is used to divide the array into
// smaller and larger elements.
int pivot = arr[low + (high - low) / 2];
// Temporary pointers used for partitioning.
// We do not modify low/high because we need
// them later for recursive calls.
int st = low;
int end = high;
// Partition the array around the pivot.
while (st <= end) {
// Move st until we find an element that
// should be on the right side of the pivot.
while (arr[st] < pivot)
st++;
// Move end until we find an element that
// should be on the left side of the pivot.
while (arr[end] > pivot)
end--;
// If pointers have not crossed,
// swap the misplaced elements.
if (st <= end) {
swap(arr, st, end);
// Move both pointers inward and continue searching.
st++;
end--;
}
}
/*
After partition:
low .... end | st .... high
Left side -> elements <= pivot
Right side -> elements >= pivot
Now sort both halves separately.
*/
sort(arr, low, end); // Sort left half
sort(arr, st, high); // Sort right half
}
static void swap(int[] array, int a, int b) {
// Standard swap logic
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
/*
Best / Average Case:
When the pivot divides the array into roughly equal halves,
the recursion tree has log n levels.
At every level, partitioning processes all n elements once.
Therefore:
Time = O(n) × O(log n)
= O(n log n)
Worst Case:
When the pivot repeatedly becomes the smallest or largest element,
the partition creates:
0 elements | n-1 elements
The recursion tree becomes skewed and has n levels.
At each level, partitioning still scans the remaining elements.
Therefore:
Time = O(n²)
Quick Sort becomes O(n²) when the pivot repeatedly creates highly unbalanced partitions.
*/