クイックソート | アルゴリズム [AOJ 10029][Ruby/Java]

今回は、『AOJ 10029 - ソートアルゴリズム(クイックソート)』についての記事です。RubyとJavaのサンプルソースを載せています。

勉強のために「クイックソート」と、マージソートを書いてみました。一般的にはマージソートよりもクイックソートの方が高速です。しかし、AOJで実際にプログラムを書いて実感しましたが『クイックソートのアルゴリズムはソート対象によって計算量が変わる』特徴があります。計算量が安定しているという意味では、マージソートの方が優れていることを知りました。

🐯 概要

algorithm-quick-sort

1. 未整列のデータ群から任意の1つを取り出す
1. これを基準に未整列のデータ群を大小2つに分ける
1. 分割したデータ群について1－2を繰り返す
1. データ群が分割できなくなったところで結果を連結する

🐰 特徴

t(n) をn要素配列にクイックソートを行う時間と定義すると、 t(n) = 2*t(n/2) + o(n) となる。
- o(n) が部分配列分割に必要な線形作業
最悪時は、1要素を整列するために全要素を調べることになり、それがn - 1回繰り返されるのでo(nの2乗)となる

Rubyコード

class Array
  def quick_sort
    return self if length <= 1
    base = pop
    smaller, bigger = partition { |e| e < base }
    push base
    smaller.quick_sort + [base] + bigger.quick_sort
  end
end

_n = gets.to_i
puts gets.chomp.split(' ').map(&:to_i).quick_sort.join(' ')

Javaコード

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.System;
import java.util.ArrayList;

class Main {
    public static void main(String[] a) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(r.readLine());
        String tmp = r.readLine();
        String[] str = tmp.split(" ");

        ArrayList arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arr.add(Integer.parseInt(str[i]));
        }

        ArrayList result = quickSort(arr);
        printArrayList(result);
    }

    private static void printArrayList(ArrayList result) {
        StringBuilder st = new StringBuilder();
        for (int i = 0; i < result.size(); i++) {
            st.append(result.get(i));
            if (i != result.size() - 1) {
                st.append(" ");
            }
        }
        System.out.println(st);
    }

    private static ArrayList quickSort(ArrayList inputArray) {
        if (inputArray.size() <= 1) {
            return inputArray;
        }

        int half = inputArray.size()/2;
        ArrayList left = new ArrayList<>();
        ArrayList right = new ArrayList<>();

        for (int i = 0; i < inputArray.size(); i++) {
            if (i == half) {
                continue;
            } else if (inputArray.get(half) > inputArray.get(i)) {
                left.add(inputArray.get(i));
            } else {
                right.add(inputArray.get(i));
            }
        }

        ArrayList r = quickSort(left);
        r.add(inputArray.get(half));
        r.addAll(quickSort(right));
        return r;
    }
}

🏀 アルゴリズムの改善

スタックが深さが問題になる可能性があるので、深さを最小にするために小さな部分配列を最初に処理するとよい
「3個の中央値」にもとづて軸を選択する
大きな配列にクイックソートを使い、小さな配列に挿入ソートを組み合わせることで20-25％の改善がみられる(セジウィック、 1978)
- Sun4では実験結果にもとづて4になっていた