Java Reference
In-Depth Information
After being removed from the buckets, the elements are in the following order:
9, 34, 45, 59, 230, 231, 331, 343, 345, 453, 454
The elements are now sorted.
Radix sort takes
O(dn)
time to sort
n
elements with integer keys, where
d
is the maximum
number of the radix positions among all keys.
23.21
✓
✓
Can you sort a list of strings using a bucket sort?
Check
23.22
Show how the radix sort works using the numbers
454
,
34
,
23
,
43
,
74
,
86
, and
76
.
Point
You can sort a large amount data using an external sort.
Key
Point
All the sort algorithms discussed in the preceding sections assume that all the data to be sorted
are available at one time in internal memory, such as in an array. To sort data stored in an
external file, you must first bring the data to the memory and then sort it internally. However,
if the file is too large, all the data in the file cannot be brought to memory at one time. This
section discusses how to sort data in a large external file. This is called an
external sort
.
For simplicity, assume that two million
int
values are stored in a binary file named
largedata.dat
. This file was created using the program in Listing 23.11.
external sort
L
ISTING
23.11
CreateLargeFile.java
1
import
java.io.*;
2
3
public class
CreateLargeFile {
4
public static void
main(String[] args)
throws
Exception {
5
DataOutputStream output =
new
DataOutputStream(
a binary output stream
6
new
BufferedOutputStream(
7
new
FileOutputStream(
"largedata.dat"
)));
8
9
for
(
int
i =
0
; i <
800004
; i++)
10
output.writeInt((
int
)(Math.random() *
1000000
));
output an
int
value
11
12
output.close();
close output file
13
14
// Display first 100 numbers
15 DataInputStream input =
new
DataInputStream(
16
new
BufferedInputStream(
new
FileInputStream(
"largedata.dat"
)));
17
for
(
int
i =
0
; i <
100
; i++)
18 System.out.print(input.readInt() +
" "
);
19
20 input.close();
21 }
22 }
read an
int
value
close intput file
569193 131317 608695 776266 767910 624915 458599 5010 ... (omitted)
A variation of merge sort can be used to sort this file in two phases:
Phase I:
Repeatedly bring data from the file to an array, sort the array using an internal
sorting algorithm, and output the data from the array to a temporary file. This process is
shown in Figure 23.17. Ideally, you want to create a large array, but its maximum size
depends on how much memory is allocated to the JVM by the operating system. Assume
that the maximum array size is 100,000
int
values. In the temporary file, every 100,000
Search WWH ::
Custom Search