-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSort.java
More file actions
108 lines (93 loc) · 1.83 KB
/
Copy pathQuickSort.java
File metadata and controls
108 lines (93 loc) · 1.83 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
package sortingAnalysis;
public class QuickSort
{
private static long comparisons = 0;
private static long movements= 0;
// Constructors
public QuickSort()
{
}
// Getters
public static long getComparisons()
{
return comparisons;
}
public static long getMovements()
{
return movements;
}
public static void quickSort(int[] list)
{
comparisons = 0;
movements = 0;
quickSort(list, 0, list.length - 1);
}
public static void quickSort(int[] list, int first, int last)
{
if (last > first)
{
int pivotIndex = partition(list, first, last);
quickSort(list, first, pivotIndex - 1);
quickSort(list, pivotIndex + 1, last);
movements++;
}
comparisons++;
}
// Partition the array list [first..last]
public static int partition(int[] list, int first, int last)
{
int pivot = list[first]; // Choose the first element as the pivot
int low = first + 1; // Index for forward search
int high = last; // Index for backward search
movements++;
movements++;
movements++;
while (high > low)
{
// Search forward from left
while (low <= high && list[low] <= pivot)
{
low++;
comparisons++;
}
// Search backward from right
while (low <= high && list[high] > pivot)
{
high--;
comparisons++;
}
// Swap two elements in the list
if (high > low)
{
int temp = list[high];
list[high] = list[low];
list[low] = temp;
movements++;
movements++;
movements++;
}
comparisons++;
comparisons++;
}
while (high > first && list[high] >= pivot)
{
high--;
comparisons++;
}
// Swap pivot with list[high]
if (pivot > list[high])
{
list[first] = list[high];
list[high] = pivot;
comparisons++;
movements++;
movements++;
return high;
}
else
{
comparisons++;
return first;
}
}
}