FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Algorithms/src/select/QuickSelect.java at master · jingedawang/Algorithms · GitHub
jingedawang
/
Algorithms
Public
Notifications
You must be signed in to change notification settings
Fork
17
Star
102
Code
Issues
3
Pull requests
0
Discussions
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Discussions
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Algorithms
/
src
/
select
/
QuickSelect.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
96 lines (89 loc) · 2.34 KB
Breadcrumbs
Algorithms
/
src
/
select
/
QuickSelect.java
Copy path
File metadata and controls
96 lines (89 loc) · 2.34 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
/**
* Copyright 2022 jingedawang
*/
package
select
;
import
utils
.
ArrayGenerator
;
import
utils
.
ArrayPrinter
;
/**
* Quick select algorithm.
*
* This select algorithm is a variant of quick sort algorithm by always cutting half of the branch when dividing.
*/
public
class
QuickSelect
implements
Select
{
/**
* Demo code.
*/
public
static
void
main
(
String
[]
args
) {
int
[]
arr
=
ArrayGenerator
.
fixedArray
();
System
.
out
.
println
(
"Let's select items from this array:"
);
ArrayPrinter
.
print
(
arr
);
Select
select
=
new
QuickSelect
();
System
.
out
.
println
();
int
result
=
select
.
select
(
arr
,
4
);
System
.
out
.
println
(
"The 4-th smallest number is "
+
result
+
"."
);
}
/**
* Quick select.
*
* @param arr Integer array from which select.
* @param i The order of the element to be selected.
* @return The selected element.
*/
@
Override
public
int
select
(
int
[]
arr
,
int
i
) {
return
quickSelect
(
arr
,
0
,
arr
.
length
-
1
,
i
);
}
/**
* The recursive procedure in quick select.
*
* @param arr The array from which select.
* @param p The start index of the sub-array from which select.
* @param r The end index of the sub-array from which select.
* @param i The order of the element to be selected.
* @return The selected element.
*/
protected
int
quickSelect
(
int
[]
arr
,
int
p
,
int
r
,
int
i
) {
if
(
i
<
0
||
i
>=
arr
.
length
) {
throw
new
IndexOutOfBoundsException
(
"Selected index "
+
i
+
" is out of array bound."
);
}
if
(
p
==
r
) {
return
arr
[
p
];
}
int
q
=
partition
(
arr
,
p
,
r
);
int
k
=
q
-
p
;
if
(
k
==
i
) {
return
arr
[
q
];
}
else
if
(
k
>
i
) {
return
quickSelect
(
arr
,
p
,
q
-
1
,
i
);
}
else
{
return
quickSelect
(
arr
,
q
+
1
,
r
,
i
-
k
-
1
);
}
}
/**
* Partition the array into two parts.
* <p>
* After this method, elements greater than pivot are put right, others are put left.
*
* @param arr The array to be sorted.
* @param p The start index of the sub-array to be sorted.
* @param r The end index of the sub-array to be sorted.
* @return The index of the pivot after partition.
*/
protected
int
partition
(
int
[]
arr
,
int
p
,
int
r
) {
int
x
=
arr
[
r
];
int
i
=
p
-
1
;
int
temp
;
for
(
int
j
=
p
;
j
<
r
;
j
++) {
if
(
arr
[
j
] <=
x
) {
i
++;
temp
=
arr
[
i
];
arr
[
i
] =
arr
[
j
];
arr
[
j
] =
temp
;
}
}
temp
=
arr
[
i
+
1
];
arr
[
i
+
1
] =
arr
[
r
];
arr
[
r
] =
temp
;
return
i
+
1
;
}
}
Back
|
FazBrowse Home
|
New Git URL