FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/Sorts/BitonicSort.java at master · iDev-git/Java · GitHub
iDev-git
Java
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java
/
Sorts
/
BitonicSort.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
74 lines (65 loc) · 2.19 KB
Breadcrumbs
Java
/
Sorts
/
BitonicSort.java
Copy path
File metadata and controls
74 lines (65 loc) · 2.19 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
package
Sorts
;
/* Java program for Bitonic Sort. Note that this program
works only when size of input is a power of 2. */
public
class
BitonicSort
{
/* The parameter dir indicates the sorting direction,
ASCENDING or DESCENDING; if (a[i] > a[j]) agrees
with the direction, then a[i] and a[j] are
interchanged. */
void
compAndSwap
(
int
a
[],
int
i
,
int
j
,
int
dir
) {
if
((
a
[
i
] >
a
[
j
] &&
dir
==
1
) || (
a
[
i
] <
a
[
j
] &&
dir
==
0
)) {
// Swapping elements
int
temp
=
a
[
i
];
a
[
i
] =
a
[
j
];
a
[
j
] =
temp
;
}
}
/* It recursively sorts a bitonic sequence in ascending
order, if dir = 1, and in descending order otherwise
(means dir=0). The sequence to be sorted starts at
index position low, the parameter cnt is the number
of elements to be sorted.*/
void
bitonicMerge
(
int
a
[],
int
low
,
int
cnt
,
int
dir
) {
if
(
cnt
>
1
) {
int
k
=
cnt
/
2
;
for
(
int
i
=
low
;
i
<
low
+
k
;
i
++)
compAndSwap
(
a
,
i
,
i
+
k
,
dir
);
bitonicMerge
(
a
,
low
,
k
,
dir
);
bitonicMerge
(
a
,
low
+
k
,
k
,
dir
);
}
}
/* This funcion first produces a bitonic sequence by
recursively sorting its two halves in opposite sorting
orders, and then calls bitonicMerge to make them in
the same order */
void
bitonicSort
(
int
a
[],
int
low
,
int
cnt
,
int
dir
) {
if
(
cnt
>
1
) {
int
k
=
cnt
/
2
;
// sort in ascending order since dir here is 1
bitonicSort
(
a
,
low
,
k
,
1
);
// sort in descending order since dir here is 0
bitonicSort
(
a
,
low
+
k
,
k
,
0
);
// Will merge wole sequence in ascending order
// since dir=1.
bitonicMerge
(
a
,
low
,
cnt
,
dir
);
}
}
/*Caller of bitonicSort for sorting the entire array
of length N in ASCENDING order */
void
sort
(
int
a
[],
int
N
,
int
up
) {
bitonicSort
(
a
,
0
,
N
,
up
);
}
/* A utility function to print array of size n */
static
void
printArray
(
int
arr
[]) {
int
n
=
arr
.
length
;
for
(
int
i
=
0
;
i
<
n
; ++
i
)
System
.
out
.
print
(
arr
[
i
] +
" "
);
System
.
out
.
println
();
}
public
static
void
main
(
String
args
[]) {
int
a
[] = {
3
,
7
,
4
,
8
,
6
,
2
,
1
,
5
};
int
up
=
1
;
BitonicSort
ob
=
new
BitonicSort
();
ob
.
sort
(
a
,
a
.
length
,
up
);
System
.
out
.
println
(
"
\n
Sorted array"
);
printArray
(
a
);
}
}
Back
|
FazBrowse Home
|
New Git URL