005文字列検索---3方向分割文字列の高速ソート

3方向分割文字列の高速ソート

本文は『アルゴリズム(第4版)』

を参照する

三方向分割文字列快速ソート

1.実装コード

2.まとめ

本稿では『アルゴリズム(第4版)』を参照
3方向分割文字列の高速ソート
1.実装コード

package algorithms.stringrank;

public class Quick3string {
    	private static int charAt(String s, int d){
    		if(d < s.length()) return s.charAt(d);
    		return -1;
    	}
    	public static void sort(String[] a){
    		sort(a, 0, a.length-1, 0);
    	}
    	private static void sort(String[] a, int lo, int hi, int d){
        	if(lo >= hi) return;
        	int lt = lo, gt = hi;
        	int v = charAt(a[lo],d);
        	int i = lo + 1; 
        	
        	while(i <= gt){
        		int t = charAt(a[i], d);
        		if      (t < v)   exch(a, lt++, i++);
        		else if (t > v)   exch(a, i, gt--);
        		else i++;
        		//System.out.println((char)t);
        	}
        	sort(a, lo, lt-1, d);
        	if(v >= 0 ) sort(a, lt, gt, d+1);
        	sort(a, gt+1, hi, d);
        } 
    	private static void exch(String[] a, int i, int j){
    		String temp = a[i];
    		a[i] = a[j];
    		a[j] = temp;
    	}
    	public static void main(String[] args) {
    		String[] a = new String[]{"by","air","she","shell","the","okay","bump","shirt","shells","sh","the","shells","the"};
    		String[] b = new String[]{
    	            "003.322.805.822.840.438.220.274",
    	            "055.786.157.416.245",
    	            "077.134.673.105.355.003.758.727.066",
    	            "085.013.435.523.224",
    	            "152.441.564.586.073",
    	            "152.177.480",
    	            "152.465.444.522.626.526.568",
    	            "152.177.480.748.018.647.570",
    	            "323.624",
    	            "356.773.718.782.171.536.871",
    	            "364.180.121.483.601.678.067",
    	            "402.107.014",
    	            "472.602.046",
    	            "472.602.046.263.170",
    	            "472.602.046.263.803",
    	            "527.530.350.778.137.513.335",
    	            "536.017.404.734.537.134.241",
    	            "604.255.236.550",
    	            "640.117.263.314.358.353.678",
    	            "677.873.326.803.167.528.474",
    	            "733.212.422",
    	            "783.850.435.605.204.862.722.563.417",
    	            "800.461.476.404.442.666.212",
    	            "810.454.842.314.848.623",
    	            "823.405.158.606",
    	            "833.204.283.833.320.664.236",
    	            "854.367.556.645.628.764.760"
    		};
    		sort(b); 
    		for(String s : b)
    		  System.out.println(s);
    
    	}

} 

出力:

  ：
003.322.805.822.840.438.220.274
055.786.157.416.245
077.134.673.105.355.003.758.727.066
085.013.435.523.224
152.177.480
152.177.480.748.018.647.570
152.441.564.586.073
152.465.444.522.626.526.568
323.624
356.773.718.782.171.536.871
364.180.121.483.601.678.067
402.107.014
472.602.046
472.602.046.263.170
472.602.046.263.803
527.530.350.778.137.513.335
536.017.404.734.537.134.241
604.255.236.550
640.117.263.314.358.353.678
677.873.326.803.167.528.474
733.212.422
783.850.435.605.204.862.722.563.417
800.461.476.404.442.666.212
810.454.842.314.848.623
823.405.158.606
833.204.283.833.320.664.236
854.367.556.645.628.764.760

2.まとめ