ソートアルゴリズムの改良について

Question

最近、AtCoderを始めた初心者です。チュートリアルの問題を解いたのですが、もう少しスマートな書き方や、効率のよいアルゴリズムがあればと思い質問しました。質問内容は、

1. もっと簡潔な書き方はないか?
2. マージのアルゴリズムを改良できないか、in-placeにできないか? (log(Combination(2n, n))=O(n)?)
3. n=5の場合のチューニングをコンパイル時に自動でさせる方法はないか? (保守性が高い、メタな表記がありそう)

の3点です。自力だと力業でゴリ押す汚いコードしか書けないものですから、コンテストに参加するにはまだまだ力不足と痛感しておりますが、ご教授教示いただけますと助かります。

問題文

#include <iostream>
#include <algorithm>
#include <type_traits>
#include <utility>
#include <vector>

namespace practiceB{

template <class RandomAccessIterator, class Compare>
void sort(const RandomAccessIterator first, const RandomAccessIterator last, Compare comp)
{
	std::size_t n = std::distance(first, last);
	if(n < 2)	return;
	if(n != 5){
		auto mid = first + n / 2;
		practiceB::sort(first, mid, comp);
		practiceB::sort(mid, last, comp);

		std::vector<typename std::remove_const<typename std::remove_reference<decltype(*first)>::type>::type> tmp(n);
		std::merge(first, mid, mid, last, tmp.begin(), comp);
		std::move(tmp.begin(), tmp.end(), first);
	}
	else{
		if(!comp(first[0], first[1])){
			std::swap(first[0], first[1]);
		}
		if(!comp(first[2], first[3])){
			std::swap(first[2], first[3]);
		}
		if(!comp(first[0], first[2])){
			std::swap(first[0], first[2]);
			std::swap(first[1], first[3]);
		}
		if(comp(first[2], first[4])){
			if(comp(first[3], first[4])){
				if(comp(first[1], first[3])){
					if(!comp(first[1], first[2])){
						std::swap(first[1], first[2]);
					}
				}
				else{
					std::swap(first[1], first[2]);
					std::swap(first[2], first[3]);
					if(!comp(first[3], first[4])){
						std::swap(first[3], first[4]);
					}
				}
			}
			else{
				if(comp(first[1], first[4])){
					std::swap(first[3], first[4]);
					if(!comp(first[1], first[2])){
						std::swap(first[1], first[2]);
					}
				}
				else{
					std::swap(first[1], first[2]);
					std::swap(first[2], first[4]);
					if(!comp(first[3], first[4])){
						std::swap(first[3], first[4]);
					}
				}
			}
		}
		else{
			if(comp(first[0], first[4])){
				if(comp(first[1], first[2])){
					std::swap(first[2], first[3]);
					std::swap(first[2], first[4]);
					if(!comp(first[1], first[2])){
						std::swap(first[1], first[2]);
					}
				}
				else{
					std::swap(first[1], first[4]);
					if(!comp(first[3], first[4])){
						std::swap(first[3], first[4]);
					}
				}
			}
			else{
				std::swap(first[0], first[4]);
				std::swap(first[1], first[4]);
				if(comp(first[2], first[4])){
					if(!comp(first[3], first[4])){
						std::swap(first[3], first[4]);
					}
				}
				else{
					std::swap(first[2], first[4]);
					std::swap(first[3], first[4]);
				}
			}
		}
	}
}

}

5/16編集：標準テンプレートにmergeが実装されているらしいので、それを使うようにしました。関数が減り、見やすくはなりましたが依然としてn=5の場合がカオスです…。

Comments

[Orlofsky]

URLは https://teratail.com/help/question-tips#questionTips3-7 の [リンク] で [リンク先のタイトル](http...) に修正してください。
他のMarkdownの機能も確認しておいてください。

[Orlofsky]

教授 → 教示

[cateye]

マージソートは、安定ソートですが。それの拘らなくても良いのですか？

[majiponi]

compを呼ぶ回数を最小に > 簡潔性、保守性 >>> 必要メモリの少なさ、安定ソート

これぐらいの認識です。中身の要素はすべて異なる、という前提なので、安定ソートである必要は、ないです。

[Zuishin]

どうしてもマージソートと特定のケースへの条件分岐が必要なんですか？
それをスマートと呼ぶのは非常に抵抗がありますが。
もしそうであるなら「スマート」を定義してください。

[Orlofsky]

教授教示 → 教示

Answer 1

1. もっと簡潔な書き方はないか?

マージソートをやめてクイックソートにするのが良いと思います。
最初の比較で重い方をピボットに選べば N == 5 の時に 6 回以内の比較で終了します。このため、他のケースと場合分けする必要がありません。

1. マージのアルゴリズムを改良できないか、in-placeにできないか? (log(Combination(2n, n))=O(n)?)

アルゴリズムの特性上、要素の挿入が必要となり、in-place にすると大量の移動が発生します。改良にはなりません。クイックソートならば、挿入が必要ありません。

ただし、配列の代わりに連結リストを用いることにより、挿入の負荷を減らすことはできます。しかしこの場合はノード操作自体の負荷がかかるので、高々 26 要素のソートであれば、かえって性能が落ちることが予想されます。

1. n=5の場合のチューニングをコンパイル時に自動でさせる方法はないか? (保守性が高い、メタな表記がありそう)

ソートアルゴリズムをこのケースに最適化させるのが良いと思います。

Comments

[Zuishin]

最悪のケースとなるソート済みの入力 1, 2, 3, 4, 5 を考えます。

最初に 1 と 2 を取り出して比較し、2 をピボットに選びます。
比較回数を極力減らすため、アルゴリズムは、前半をソートし、ピボットをその後に置き、後半をソートすることで全体のソートが成るということにします。

次に 2 と残りの要素を比較し、小さいものを前半に、大きいものを後半に集めます。
前半は 1 になったので、要素数 1 で確定です。次にピボットの 2 が置かれます。

残り 3, 4, 5 をクイックソートします。
まず 3 と 4 を取り出して 4 をピボットに選びます。
4 と 5 を比較することで前半は 3 に、後半は 5 に確定しました。

比較は 1-2, 2-3, 2-4, 2-5, 3-4, 4-5 の 6 回で、これが最悪のケースです。なお、最良のケースは 3 を最初のピボットに選ぶことによる 6 回の比較なので、この場合は最悪と最良の差はありません。

[Zuishin]

根本的に、要素数が少ないので計算量やメモリの使用量のチューニングは意味を成しません。この問題のボトルネックは明らかに入出力を伴う比較関数であり、それをいかに減らすかが鍵です。また最適化すべきは大量の入力ではなく小数の入力に対してです。

プログラムを改良するならば、一つのアルゴリズムに固執せず最適なアルゴリズムを選択することをまず考えるべきでしょうし、ボトルネックがどこにあるのかを最重要視しなければならないと思います。

たとえば Ajax であれば、サーバーと百回やり取りする代わりに計算量が O(n) で済むアルゴリズムと、サーバーとのやり取りは一回で済むが計算量が O(n^2) であるアルゴリズムでは、後者を選ぶ方が良い選択である場合も多々あります。

[majiponi]

今、5!=120個の置換1つ1つで試して、教わったアルゴリズムを試しているのですが、15432の場合、比較回数が1-5,5-4,5-3,5-2,1-4,4-3,4-2,1-3,1-2の10回となってしまったのですが、私は何か勘違いをしているのでしょうか…?

[Zuishin]

いえ、どうも私がボケていたようです。考え直します。

Answer 2

チュートリアルの問題を解いたのですが、

始めに、Practice-Bは初心者向きの問題では無いです。
（こんなところにこんな問題を置くなという運営に対する文句もありますが…）

もっと簡潔な書き方はないか?

簡潔さだけに関して言えば、n == 5 のケースを除いて、std::stable_sort を使えば、
マージソートを自前で実装する必要が無いと思います。

merge については、現状以下のような手順になっているかと思いますが、

1. tmpにコピー
2. tmpの先頭から、比較を行いながら入力の配列に書き込んでいく

以下のようにすれば、std::distance は消せると思います。

1. 入力配列の先頭から、比較を行いながらtmpに書き込んでいく
2. tmpから入力の配列にコピー。 std::copy が使えます。

マージのアルゴリズムを改良できないか、in-placeにできないか? (log(Combination(2n, n))=O(n)?)

in-place なソートアルゴリズムと言えば、ヒープソートが有名です。
マージソート同様、比較回数がO(nlogn)で抑えられています。
マージソートでinplaceかつ簡潔に記述できるアルゴリズムはよく知らないです。

n=5の場合のチューニングをコンパイル時に自動でさせる方法はないか?

これも分かりません。すみません。
Ratedの競技プログラミングコンテンストでこのようなコーナーケースが出るとは思えないですが、
ソースコードを出力するプログラムを別途書くのが一般的ではないでしょうか。