新・アルゴリズムとデータ構造入門 Java編5:クイックソートの実装

#07:クイックソートの実装

import java.util.Scanner;

public class Main {

    static int count = 0;

    static void quickSort(int[] a, int left, int right) {
        // もし left が right-1 以上なら終了

        // pivot に a[right-1] を代入
        // curIndex を left で初期化
        for (int i = left; i < right - 1; i++) {
            // もし a[i] が pivot より小さいなら
            if (/* */) {
                // a[curIndex] と a[i] を交換
                // curIndex を 1 だけ増やす
                count++;
            }
        }

        // ピボットと a[curIndex] を交換

        // quickSort(a, left, curIndex) を呼び出す
        // quickSort(a, curIndex+1, right) を呼び出す
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        quickSort(a, 0, n);

        for (int i = 0; i < n; i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(a[i]);
        }
        System.out.println();

        System.out.println(count);
    }
}

import java.util.Scanner;

public class Main {

    static int count = 0;

    static void quickSort(int a[], int left, int right) {
        if (left >= right - 1) {
            return;
        }

        int pivot = a[right - 1];

        int curIndex = left;
        for (int i = left; i < right - 1; i++) {
            if (a[i] < pivot) {
                int cp = a[curIndex];
                a[curIndex] = a[i];
                a[i] = cp;
                curIndex++;
                count++;
            }
        }

        a[right - 1] = a[curIndex];
        a[curIndex] = pivot;

        quickSort(a, left, curIndex);
        quickSort(a, curIndex, right);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int a[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        quickSort(a, 0, n);

        for (int i = 0; i < n; i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(a[i]);
        }
        System.out.println();

        System.out.println(count);
    }
}

この動画を見るにはpaiza会員登録のうえ
有料会員登録が必要です

無料会員登録して始める

★ 実技1

実技課題「正しくクイックソートを実装する」

整数 n と要素数 n の数列 A が与えられるので、この数列をクイックソートでソートしてください。
右側のコードエリアに用意されているコードには誤りがあります。訂正し、問題を解くコードを完成させてください。

【制約】
・入力は全て整数
・ 1 ≦ n ≦ 10
・ 1 ≦ (数列 A の各要素) ≦ 100