Search on the blog

2012年2月14日火曜日

Sort in Java

Played around with Java to try some sort functionalities.

What I did:
1. Just sort an integer array
2. Sort an integer array in non-increasing order
3. Sort a string array in non-decreasing order of the length
4. Sort substrings (implemented a simple suffix-array-like algorithm)

Interesting stuff:
1. Comparator is like functor in C++.
2. Anonymous class is cool! I liked this style. You can write, on the spot, an implementation of its super class (or interface).
3. Java's string data structure is clever. The way it retains strings enable to share a memory with some strings. In the code test4(), all the substrings share a memory.
4. Looks like Java Api codes are way more legible than that of C++.

Source code:
I'll post the source code below.
import java.util.Arrays;
import java.util.Comparator;

public class Test {
    public static void main(String args[]) {
        test1();
        test2();
        test3();
        test4();
    }
    
    private static void test1() {
        int xs[] = {4, 1, 4, 6, 3, 8, 10, 0};
        
        Arrays.sort(xs);
        
        System.out.println(Arrays.toString(xs));
    }
    
    private static void test2() {
        Integer xs[] = {4, 1, 4, 6, 3, 8, 10, 0};
        
        Arrays.sort(xs, new Comparator<Integer>() {
            public int compare(Integer x, Integer y) {
                return y-x;
            }
        });

        System.out.println(Arrays.toString(xs));        
    }
    
    private static void test3() {
        String names[] = {
                "hanako",
                "taro",
                "yu",
                "sho",
                "amataro",
                "takafumi"                
        };
        
        Arrays.sort(names, new Comparator<String>() {
            public int compare(String x, String y) {
                return x.length() - y.length();
            }
        });

        System.out.println(Arrays.toString(names));
    }
    
    private static void test4() {
        String text = "Oh, say can you see," +
                 "by the dawn's early light" +
                 "What so proudly we hailed" +
                 "at the twilight's last gleaming?" +
                 "Whose broad stripes and bright stars," +
                 "through the perilous fight." +
                 "O'er the ramparts we watched" +
                 "were so gallantly streaming?";
        
        String word = "gallant";
        
        // build a suffix array
        String suffix[] = new String[text.length()];
        for (int i = 0; i < text.length(); i++)
            suffix[i] = text.substring(i);
        Arrays.sort(suffix);
        
        // search the word
        int lo = 0;
        int hi = text.length() - 1;
        
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            
            if (suffix[mid].compareTo(word) < 0)
                lo = mid + 1;
            else
                hi = mid;    
        }
        
        if (suffix[lo].startsWith(word))
            System.out.println(word + " is found!");
        else
            System.out.println(word + " is not found!");            
    }
    
}

0 件のコメント:

コメントを投稿