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
23.8 External Sort
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