Cài đặt Sắp xếp ngoài (Java code)

Xem thuật toán

Cài đặt bằng Java của thuận toán Sắp xếp ngoài, công nhận chạy nhanh hơn nhiều so với ngày xưa code bằng Pascal.

Algorithm: External Sort
Author: Katatunix

ESort.java

package esort;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.Reader;
import java.io.StreamTokenizer;
import java.io.Writer;

public class ESort {
    public static String tmpFileName1 = "tmp1.txt";
    public static String tmpFileName2 = "tmp2.txt";

    public static void sortMergeWrite(int[] a, String inFile, String outFile) {
        try {
            new QSort(a).qsort();
            Reader r = new BufferedReader(new FileReader(inFile));
            StreamTokenizer stok = new StreamTokenizer(r);
            stok.parseNumbers();

            Writer w = new BufferedWriter(new FileWriter(outFile));

            int len = a[10000];
            int i = 0;

            stok.nextToken();

            while (true) {
                if (i == len && stok.ttype == StreamTokenizer.TT_EOF)
                    break;
                int z;
                if (i == len)
                    z = (int) stok.nval;
                else if (stok.ttype == StreamTokenizer.TT_EOF)
                    z = a[i];
                else
                    z = Math.min(a[i], (int) stok.nval);
                w.write(String.valueOf(z));
                w.write(13);
                w.write(10);

                if (z == a[i])
                    i++;
                else
                    stok.nextToken();
            }
            r.close();
            w.close();
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

    public static String esort(String fileName) {
        createInFile();
        String inFile = tmpFileName1;
        String outFile = tmpFileName2;
        ManageMainFile man = new ManageMainFile(fileName);
        while (true) {
            int[] a = man.readNextBlock();
            if (a == null || a[10000] == 0) break;
            sortMergeWrite(a, inFile, outFile);
            String tmp = inFile;
            inFile = outFile;
            outFile = tmp;
        }
        return inFile;
    }

    private static void createInFile() {
        try {
            Writer w = new BufferedWriter(new FileWriter(tmpFileName1));
            w.close();
        }
        catch (Exception ex) {
            ex.printStackTrace();
        }
    }

}

ManageMainFile.java

package esort;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.Reader;
import java.io.StreamTokenizer;

public class ManageMainFile {
    Reader r;
    StreamTokenizer stok;

    public ManageMainFile(String fileName) {
        try {
            r = new BufferedReader(new FileReader(fileName));
            stok = new StreamTokenizer(r);
            stok.parseNumbers();
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

    public int[] readNextBlock() {
        try {
            int[] a = new int[10001];
            a[10000] = 0;
            for (int i = 0; i < 10000; i++) {
                stok.nextToken();
                if (stok.ttype == StreamTokenizer.TT_EOF) break;
                if (stok.ttype == StreamTokenizer.TT_NUMBER) {
                    a[10000]++;
                    a[i] = (int) stok.nval;
                }
            }
            return a;
        } catch (Exception ex) {
            return null;
        }
    }

    public void closeFile() {
        try {
            r.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

QSort.java

package esort;

public class QSort {
    int[] a;
    int len;

    public QSort(int[] a) {
        this.a = a;
        len = a[10000];
    }

    public void qsort() {
        sort(0, len - 1);
    }

    public void sort(int l, int r) {
        if (l >= r) return;
        int x = a[(l + r) / 2];
        int i = l, j = r;
        while (i <= j) {
            while (a[i] < x) i++;
            while (x < a[j]) j--;
            if (i <= j) {
                int tmp;
                tmp = a[i]; a[i] = a[j]; a[j] = tmp;
                i++;
                j--;
            }
        }
        sort(l, j);
        sort(i, r);
    }

}

MakeInput.java

package test;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.Writer;
import java.util.Random;

public class MakeInput {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int N = 50000;
        int max = 2000000000;
        Random random = new Random();
        try {
            Writer w = new BufferedWriter(new FileWriter("file.txt"));
            for (int i = 0; i < N; i++) {
                int x = random.nextInt(max);
                if (random.nextInt(2) == 0) x = -x;
                w.write(String.valueOf(x));
                w.write(13);
                w.write(10);
            }
            w.close();
        }
        catch (Exception ex) {
            ex.printStackTrace();
        }
        System.out.println("OK");
    }

}

TestESort.java

package test;

import esort.ESort;

public class TestESort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        String outFile = ESort.esort("file.txt");
        System.out.println(outFile);
    }

}

Hoặc download toàn bộ project tại http://www.mediafire.com/?nzwzymgfktj

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s