山傘のプログラミング勉強日記[Java & Unity]

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[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;
    }

}