今更ながらJavaでSortアルゴリズムを実装した

はじめに

Javaに親しむ一貫として、有名なSortアルゴリズムを3つ実装してみた。

今回実装したのは、QuickSort、BucketSort、MergeSortの3つ。

(ジェネリクスの扱いになれてなくて、結局int型配列で実装した)

package motacapla.lib;

public class Sort<T> {
    private final int[] array;
    public Sort(int[] array) {
        this.array = array;
    }
    public int[] quickSort() {
        quickSortRecur(0, array.length-1);
        return array;
    }
    private void quickSortRecur(int left, int right) {   
        if(left >= right) return;     
        int pivot = array[(left+right)/2];
        while(left <= right) {
            while(pivot > array[left]) left++;
            while(pivot < array[right]) right--;
            if(left <= right) {
                int tmp = array[left]; 
                array[left] = array[right]; 
                array[right] = tmp;
                left++; right--;
            }
        }
        quickSortRecur(left, pivot);
        quickSortRecur(pivot, right);
    }    
    public int[] bucketSort(int maxValue) {
        int[] answer = new int[maxValue+1];
        for(int i=0; i<array.length; i++) answer[array[i]]++;
        int[] answerArray = new int[array.length];
        for(int i=0, j=0; i<answer.length; i++) {
            while(answer[i] > 0) {
                answerArray[j] = i;
                answer[i]--;
                j++;
            }
        }
        return answerArray;
    }
    public int[] mergeSort() {
        mergeSortRecur(0, array.length-1);
        return array; 
    }    
    private void mergeSortRecur(int l, int r) {
        if (l < r) { 
            int m = (l+r)/2;   
            mergeSortRecur(l, m); 
            mergeSortRecur(m+1, r);   
            merge(l, m, r); 
        } 
    }
    private void merge(int l, int m, int r) {
        int n1 = m - l + 1; 
        int n2 = r - m; 
        int L[] = new int [n1]; 
        int R[] = new int [n2]; 

        for (int i=0; i<n1; ++i) L[i] = array[l + i]; 
        for (int j=0; j<n2; ++j) R[j] = array[m + 1+ j]; 

        int i = 0, j = 0; int k = l; 
        while (i < n1 && j < n2) { 
            if (L[i] <= R[j]) { 
                array[k] = L[i]; 
                i++; 
            } 
            else { 
                array[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
        while (i < n1) { 
            array[k] = L[i]; 
            i++; 
            k++; 
        } 
        while (j < n2) { 
            array[k] = R[j]; 
            j++; 
            k++; 
        } 
      }
}

テスト

1ケースのみだが、テストコードも書いたので以下に示す。

package motacapla.lib;

import static org.junit.Assert.*;

import org.junit.Test;

public class SortTest {
    static final int ary_size = 10;
    @Test
    public void testquickSort() {    
        int [] array = new int[ary_size];
        int [] answer = new int[ary_size];
        for(int i=0; i<ary_size; i++) {
            array[i] = ary_size-i;
            answer[i] = i+1;            
        }
        Sort<Integer> srt = new Sort<Integer>(array);
        assertArrayEquals(answer, srt.quickSort());        
    }

    @Test
    public void testbucketSort() {    
        int [] array = new int[ary_size];
        int [] answer = new int[ary_size];
        int maxValue = 0;
        for(int i=0; i<ary_size; i++) {
            array[i] = ary_size-i;
            answer[i] = i+1;            
            maxValue = Math.max(maxValue, answer[i]);
        }
        Sort<Integer> srt = new Sort<Integer>(array);
        assertArrayEquals(answer, srt.bucketSort(maxValue));        
    }    
    @Test
    public void testmergeSort() {    
        int[] actual = { 5, 1, 6, 2, 3, 4 };
        int[] expected = { 1, 2, 3, 4, 5, 6 };
        Sort srt = new Sort(actual);
        actual = srt.mergeSort();
        for(int i=0; i<actual.length; i++) {
            System.out.println(actual[i]);
        }
        assertArrayEquals(expected, srt.mergeSort());        
    }       
}

TODO

RadixSortやHeapSortも実装したい！