Crossfire JXClient, Trunk
build
windows-installer
unpacked
java-se-8u41-ri
demo
applets
SortDemo
QSortAlgorithm.java
Go to the documentation of this file.
1
/*
2
* Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
3
*
4
* Redistribution and use in source and binary forms, with or without
5
* modification, are permitted provided that the following conditions
6
* are met:
7
*
8
* - Redistributions of source code must retain the above copyright
9
* notice, this list of conditions and the following disclaimer.
10
*
11
* - Redistributions in binary form must reproduce the above copyright
12
* notice, this list of conditions and the following disclaimer in the
13
* documentation and/or other materials provided with the distribution.
14
*
15
* - Neither the name of Oracle nor the names of its
16
* contributors may be used to endorse or promote products derived
17
* from this software without specific prior written permission.
18
*
19
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
20
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
23
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
26
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
27
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
28
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
*/
31
32
/*
33
* This source code is provided to illustrate the usage of a given feature
34
* or technique and has been deliberately simplified. Additional steps
35
* required for a production-quality application, such as security checks,
36
* input validation and proper error handling, might not be present in
37
* this sample code.
38
*/
39
40
41
49
public
class
QSortAlgorithm
extends
SortAlgorithm
{
50
55
private
boolean
pauseTrue
(
int
lo,
int
hi)
throws
Exception {
56
super.pause(lo, hi);
57
return
true
;
58
}
59
74
void
QuickSort
(
int
a
[],
int
lo0,
int
hi0)
throws
Exception {
75
int
lo = lo0;
76
int
hi = hi0;
77
int
mid;
78
79
if
(hi0 > lo0) {
80
81
/* Arbitrarily establishing partition element as the midpoint of
82
* the array.
83
*/
84
mid =
a
[(lo0 + hi0) / 2];
85
86
// loop through the array until indices cross
87
while
(lo <= hi) {
88
/* find the first element that is greater than or equal to
89
* the partition element starting from the left Index.
90
*/
91
while
((lo < hi0) &&
pauseTrue
(lo0, hi0) && (
a
[lo] < mid)) {
92
++lo;
93
}
94
95
/* find an element that is smaller than or equal to
96
* the partition element starting from the right Index.
97
*/
98
while
((hi > lo0) &&
pauseTrue
(lo0, hi0) && (
a
[hi] > mid)) {
99
--hi;
100
}
101
102
// if the indexes have not crossed, swap
103
if
(lo <= hi) {
104
swap
(
a
, lo, hi);
105
++lo;
106
--hi;
107
}
108
}
109
110
/* If the right index has not reached the left side of array
111
* must now sort the left partition.
112
*/
113
if
(lo0 < hi) {
114
QuickSort
(
a
, lo0, hi);
115
}
116
117
/* If the left index has not reached the right side of array
118
* must now sort the right partition.
119
*/
120
if
(lo < hi0) {
121
QuickSort
(
a
, lo, hi0);
122
}
123
124
}
125
}
126
127
private
void
swap
(
int
a
[],
int
i,
int
j) {
128
int
T;
129
T =
a
[i];
130
a
[i] =
a
[j];
131
a
[j] = T;
132
133
}
134
135
@Override
136
public
void
sort
(
int
a
[])
throws
Exception {
137
QuickSort
(
a
, 0,
a
.length - 1);
138
}
139
}
QSortAlgorithm
Definition:
QSortAlgorithm.java:49
QSortAlgorithm.pauseTrue
boolean pauseTrue(int lo, int hi)
Definition:
QSortAlgorithm.java:55
QSortAlgorithm.QuickSort
void QuickSort(int a[], int lo0, int hi0)
Definition:
QSortAlgorithm.java:74
QSortAlgorithm.swap
void swap(int a[], int i, int j)
Definition:
QSortAlgorithm.java:127
a
Xmixed mixed mode execution(default) -Xint interpreted mode execution only -Xbootclasspath set search path for bootstrap classes and resources Xbootclasspath a
Definition:
Xusage.txt:1
QSortAlgorithm.sort
void sort(int a[])
Definition:
QSortAlgorithm.java:136
SortAlgorithm
Definition:
SortAlgorithm.java:48
Generated by
1.8.17