[Aizu Online Judge] クイックソート (ALDS1_6_C: Quick Sort)

クイックソート

クイックソート | アルゴリズムとデータ構造 | Aizu Online Judge

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の7章3節 クイックソートをやります。C言語の回答をJavaで書き直しているだけですが、 タイプミスやエラーが出るので苦労しています。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

この問題はパーティションとクイックソートを組み合わせて解く問題となります。解答するために、ソート結果が安定化どうかを調べる必要があるので、 別の安定なソートのアルゴリズムを使う必要があります。

コード

import java.util.Scanner;

public class ALDS1_6_C {

    public static int MAX = 100000;
// public static Data []L;
// public static Data []R;
    public static Data[]L = new Data[MAX / 2 + 2];
    public static Data[]R = new Data[MAX / 2 + 2];
    public static final  int SENTINEL = 2000000000;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Data []A = new Data[n];
        Data []B = new Data[n];
        for(int i = 0; i < n; i++) {
            String s = scan.next();
            int t = scan.nextInt();
            A[i] = new Data(s.charAt(0), t);
            B[i] = new Data(s.charAt(0), t);
        }
        scan.close();
//     L = new Data[n / 2 + 2];
//     R = new Data[n / 2 + 2];
        mergeSort(A, n, 0, n);
        quickSort(B, n, 0, n - 1);

        int stable = 1;
        for(int i = 0; i < n; i++) {
            if(A[i].getSuit() != B[i].getSuit()) {
                stable = 0;
                break;
            }
        }
        if(stable == 1) {
            System.out.println("Stable");
        }else {
            System.out.println("Not stable");
        }
        for(int i = 0; i < n; i++) {
            System.out.println(B[i].getSuit() + " " + B[i].getValue());
        }

//     System.out.println(" ");
//     for(int i = 0; i < n; i++) {
//         System.out.println(A[i].getSuit() + " " + A[i].getValue());
//     }

    }
    public static void merge(Data[] A, int n, int left, int mid, int right) {
        int i, j, k;
        int n1 = mid - left;
        int n2 = right - mid;
        for(i = 0; i < n1; i++) {
            //L[i] = A[left + i];
            L[i] = new Data(A[left + i].getSuit(), A[left + i].getValue());
        }
        for(i = 0; i < n2; i++) {
            //R[i] = A[mid + i];
            R[i] = new Data(A[mid + i].getSuit(), A[mid + i].getValue());
        }
        L[n1] = new Data(' ', SENTINEL);
        R[n2] = new Data(' ', SENTINEL);
        //L[n1].setValue(SENTINEL);
        //R[n2].setValue(SENTINEL);
        i = 0;
        j = 0;
        for(k = left; k < right; k++) {
            if(L[i].getValue() <= R[j].getValue()) {
                //A[k] = L[i ++];
                A[k] = new Data(L[i].getSuit(), L[i].getValue());
                i++;
            }else {
                //A[k] = R[j ++];
                A[k] = new Data(R[j].getSuit(), R[j].getValue());
                j ++;
            }
        }
    }

    public static void mergeSort(Data[] A, int n, int left, int right) {
        int mid;
        if(left + 1 < right) {
            mid = (left + right) / 2;
            mergeSort(A, n, left, mid);
            mergeSort(A, n, mid, right);
            merge(A, n, left, mid, right);
        }
    }

    public static int partition(Data[] A, int n, int p, int r) {
        int i, j;
        Data t, x;
        //Data x = new Data(A[r].getSuit(), A[r].getValue());
        x = A[r];
        i = p - 1;
        for(j = p; j < r; j++) {
            if(A[j].getValue() <= x.getValue()) {
                i ++;
                t = A[i];
                //Data t = new Data(A[i].getSuit(), A[i].getValue());
                A[i] = A[j];
//             A[i].setSuit(A[j].getSuit());
//             A[i].setValue(A[j].getValue());
                A[j] = t;
//             A[j].setSuit(t.getSuit());
//             A[j].setValue(t.getValue());
            }
        }
        t = A[i + 1];
        //Data t = new Data(A[i + 1].getSuit(), A[i + 1].getValue());
        A[i + 1] = A[r];
        //A[i + 1].setSuit(A[r].getSuit());
        //A[i + 1].setValue(A[r].getValue());
        A[r] = t;
        //A[r].setSuit(t.getSuit());
        //A[r].setValue(t.getValue());
        return i + 1;
    }

    public static void quickSort(Data []A, int n, int p, int r) {
        int q;
        if(p < r) {
            q = partition(A, n, p, r);
            quickSort(A, n, p, q - 1);
            quickSort(A, n, q + 1, r);
        }
    }
}


class Data {
    private char suit;
    private int value;
    public Data(char suit, int value) {
        this.suit = suit;
        this.value = value;
    }
    public char getSuit() {
        return suit;
    }
    public int getValue() {
        return value;
    }
    public void setSuit(char suit) {
        this.suit = suit;
    }
    public void setValue(int value) {
        this.value = value;
    }

}