プログラミング原人の進化ログ

プログラミング原人の進化論

オレ プログラミング ベンキョウ スル。マナンダ コト カク。

アルゴリズム-ソート

数列の転倒数をマージソート で求める

転倒数を求める問題を解きました。バブルソートの交換回数を数えることによっても求めることができますが、より高速なマージソート を用いた解法を実装します。 問題 次の問題を解きます。 反転数 | アルゴリズムとデータ構造 | Aizu Online Judge 考え方 マ…

C++でクイックソートを実装する

もっとも高速なソートであると言われているクイックソートを実装します。前回実装したパーティションを利用します。最後に問題を解きます。 パーティションの記事はここ↓ programgenjin.hatenablog.com 目標 クイックソートを実装できるようになる。 クイッ…

C++でパーティションを実装する

高速ソートアルゴリズムに関して、今回はパーティションを実装します。パーティションはクイックソートで利用されています。 流れとしては、パーティションの説明と実装の後、最後に問題を1題解いてみます。 目標 パーティションを実装できるようになる パ…

C++でマージソートを実装してみる

今まで初等的なソートアルゴリズムである挿入ソート、バブルソート、選択ソートを実装してきました。 しかし、これらは簡単に実装できるものの、遅いです。そこで、今度はより高速なソートアルゴリズムを実装してみたいと思います。今回はマージソートです。…

C++で実装する初等的ソートアルゴリズム4 【シェルソート】

初等的ソートアルゴリズム第4弾。今回はシェルソートを実装してみます。挿入ソートの応用です。 挿入ソートがわからない方はこちら↓ programgenjin.hatenablog.com 目標 シェルソートを理解する。例によって問題を解きます。 シェルソート あらかじめある程…

C++で実装する初等的ソートアルゴリズム3【選択ソート】

初等的ソートアルゴリズム第3弾。今回は選択ソートです。 目標 選択ソートを理解することを目指します。例によって問題を解くことで理解を深めます。 選択ソート 計算量は。前方のソートずみ部分に、未ソート部分から小さい順に要素を選択して加えていくこと…

C++で実装する初等的ソートアルゴリズム2【バブルソート】

初等的ソートアルゴリズム第2弾。 今回はやたらと耳にすることが多いバブルソートです。 目標 バブルソートを理解する。実際に問題を解いてみます。 バブルソート 数列を昇順にソートします。計算量はです。 アルゴリズム 昇順になっていない隣接要素がなく…

C++で実装する初等的ソートアルゴリズム1【挿入ソート】

最近プロコンのためにアルゴリズムの勉強始めたので、メモを残しておきます。まずは基本であるソートをやっていこうかと。今回は挿入ソートです。 目標 挿入ソートを理解する。プロコンの問題を解くことで実装も行う。 挿入ソート 挿入ソートは初等的なソー…