クイックソート | アルゴリズム [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<Integer> arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr.add(Integer.parseInt(str[i]));
}
ArrayList<Integer> result = quickSort(arr);
printArrayList(result);
}
private static void printArrayList(ArrayList<Integer> 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<Integer> quickSort(ArrayList<Integer> inputArray) {
if (inputArray.size() <= 1) {
return inputArray;
}
int half = inputArray.size()/2;
ArrayList<Integer> left = new ArrayList<>();
ArrayList<Integer> 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<Integer> r = quickSort(left);
r.add(inputArray.get(half));
r.addAll(quickSort(right));
return r;
}
}

🍮 アルゴリズムの改善

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

🤔 GitHubリポジトリ

Ruby/PythonでのAOJの回答は下のリポジトリに保存しておきます。

morizyun/aoj-ruby-python - GitHub

😎 参考リンク

🚜 (参考) クイックソートと挿入ソート

  • 一定以上のサイズの配列なら、クイックソートは挿入ソートよりも早い
  • 小さい配列なら、挿入ソートがクイックソートよりも早い

📚 おすすめの書籍