forked from rpj911/LeetCode_algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSort.java
More file actions
149 lines (116 loc) · 4.32 KB
/
QuickSort.java
File metadata and controls
149 lines (116 loc) · 4.32 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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
package Algorithms.sort;
/*********************************************************
*
* 08-722 Data Structures for Application Programmers
* Lab 5 Comparing MergeSort with QuickSort
*
* A simple QuickSort implementation
*
*********************************************************/
import java.util.*;
public class QuickSort {
//private static final int SIZE = 100000;
private static final int SIZE = 10000;
private static Random rand = new Random();
public static void main(String args[]) {
int[] array = new int[SIZE];
for (int i = 0; i < SIZE; i++)
//array[i] = rand.nextInt();
array[i] = i;
//int[] array = {3, 4, 6, 1, 7, 8, 6};
// reversely ordered
/*
for(int i=0;i<SIZE; i++) array[i] = SIZE - i;
*/
quickSort(array);
// to make sure sorting works.
// add "-ea" vm argument
assert isSorted(array);
System.out.println(isSorted(array));
//printArray(array);
}
public static void printArray(int[] arr) {
System.out.println();
for(int i: arr) {
System.out.println(i + " ");
}
}
public static void quickSort(int[] arr) {
recQuickSort(arr, 0, arr.length - 1);
}
private static void recQuickSort(int[] arr, int left, int right) {
// Just the input parameter.
if (arr == null || left >= right) {
return;
}
// we just set the right node to be pivot.
int pivPosition = partition(arr, left, right, arr[right]);
recQuickSort(arr, left, pivPosition - 1);
recQuickSort(arr, pivPosition + 1, right);
}
// partition the array and return the new pivot position.
private static int partition(int[] arr, int left, int right, int pivot) {
// set the pivot.
int l = left - 1 ;
int r = right;
/*
example:
let 6 to be the pivot.
(1) At the beginning:
3 4 6 1 7 8 6
l r
(2) After the first while loop:
3 4 6 1 7 8 6
l r
(3) swap them, then continue to move i and j:
3 4 1 6 7 8 6
l r
(3) swap them, then continue to move i and j:
3 4 1 6 7 8 6
l pivot
r
(4) swap the left and the pivot.
3 4 1 6 7 8 6
l pivot
*/
while (true) {
// Find the first element which does not fulfill the rule
// It will not move out of range because the right node is pivot.
// 使用< 很重要，这样可以避免l跑到pivot的位置，就是right的位置
//while (l < r && arr[++l] <= pivot);
while (arr[++l] < pivot);
// Find the first element which does not fulfill the rule
// Don't need to move r to be left of LEFT.
while (r > l && arr[--r] > pivot);
// If r <= l, means that all the elements is in the right place.
if (r <= l) {
break;
}
// Swap the first two elements that does not fit the rule.
swap(arr, r, l);
}
// The l pointer point to the first element which is bigger than the pivot.
// So we can put the pivot just here. Because put a big or equal one in the last will not change the rule that:
// all the smaller one is in the left and the right one is in the right.
swap(arr, l, right);
return l;
}
// private helper method to swap two values in an array
private static void swap(int[] arr, int dex1, int dex2) {
int tmp = arr[dex1];
arr[dex1] = arr[dex2];
arr[dex2] = tmp;
}
/**********************************************************
* Check if array is sorted. A simple debugging tool
**********************************************************/
private static boolean isSorted(int[] array) {
return isSorted(array, 0, array.length - 1);
}
private static boolean isSorted(int[] array, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (array[i] < array[i - 1])
return false;
return true;
}
}