計数ソートとはc++で学ぶ

計数とは単純に数を数えるという意味らしく、
その名の通り、計数ソートは数を数えるアルゴリズムです(全部そうな気がしますが)

計数ソートのアルゴリズム

まず、以下の数列があり、これらを昇順にソートしたいとします。

A 5 0 5 3 1 4 5 0

この数列を配列Aとします。
計数ソートでは配列Aの各々の要素がいくつあるかを別の配列(Bとする)に記録することから始めます。

A 5 0 5 3 1 4 5 0

   0 1 2 3 4 5 6
B 2 1 0 1 1 3 0
B 2 3 3 4 5 8 8

上図では、要素の数を配列のindexに見立てて代入した後
各要素の累積和を求めて更新しています。
つまり、B[x]には配列Aについてのx以下の要素数が記録されていることになります。
これを利用して、ソートされた数列を作り出していきます。

次に昇順にソートされた数列を作りだされる過程をみていきます

1.

A 5 0 5 3 1 4 5 0
B 2 3 3 4 5 8 8

   1 2 3 4 5 6 7 8
C    0 

配列Aの末尾から0を取り出します。
続いて配列Bからindex0の要素数2を取り出します。
そして出力先となる配列Cのindex2に0を挿入します。
また、配列Cは便宜上index1からスタートしていることします。

配列Bから配列Cに挿入したindex0の要素数を一つ減らして1とします
挿入した要素を減らすことで、次に挿入する位置を調整しています。

2.

A 5 0 5 3 1 4 5 0
B 1 3 3 4 5 8 8

   1 2 3 4 5 6 7 8
C    0                  5

Aから末尾の位置を一つずらして、1と同じ動作を繰り返します。
Aの要素は5、Bのindex5の要素は8なので、cのindex8に5を代入し、
Bのindex5の要素数を一つ減らして7とします。

以下これを繰り返すことにより、昇順にソートすることができます。

計数ソートのオーダー

計数ソートは各要素が0以上k以下である要素数nの数列に対しO(n + k)で動作します。 動作で見る通りですね。

全探索アルゴリズム(brute force)と再帰処理

全探索アルゴリズムについて調べていたら、AIZU Online judgeにいい問題があったので、それを元に理解を深めます(個人的に)

問題は以下の通りです。

長さnの数列Aと整数mに対して、
Aの要素の中のいくつかの要素を足しあわせて
mが作れるかどうかを判定するプログラムを作成してください。
Aの各要素は１度だけ使うことができます。
数列 Aが与えられたうえで、質問として q 個の mi が与えれるので、
それぞれについて "yes" または "no" と出力してください。

制約が重くないために、
与えられた数値の全ての組み合わせを試せば問題が解けることになります。

制約

• n≤20
• q≤200
• 1≤Aの要素≤2,000
• 1≤mi≤2,000

問題の組み合わせ総数

与えられた数値が

1,3,5,7

だった場合、各々の数値をを使うか使わないかの選択になるので、
2^nの組み合わせになります。

再帰関数を使って、全探索を考える

以下引用になります。

1  makeCombination()
2    for i = 0 to n-1
3      S[i] = 0 // i を選択しない
4    rec(0)
5
6  rec(i)
7    if i == n
8      print S
9      return
10
11   rec(i + 1)
12   S[i] = 1 // i を選択する
13   rec(i + 1)
14   S[i] = 0 // i を選択しない

S配列をS[i] = 1の時その要素を選択する0は選択しないことを表す配列とします。
選択するかしないかを再帰関数により分岐させ、2^n - 1までのビット列を生成します。

この考え方を利用して、再帰関数を考えます。
solve(i,m)を「i番目以降の要素を使ってmを作れる場合trueを返す」という関数にすると、
solve(i,m)はより小さい部分であるsolve(i + 1,m)とsolve(i + 1,m - A[i])に分割することができます。
m - A[i]というところが、「i番目以降の要素を使う」に対応しています。

solve関数をc++で実装

再帰処理を行うsolve関数をc++で実装してみます。

// 入力値のmから選んだ要素を引いていく再帰関数
// 0なら組み合わせで生成できる数値
int solve(int i,int m){
    if(m == 0) return 1;
    if(i >= n) return 0;
    return solve(i + 1,m) || solve(i + 1,m - A[i]);
}

solveを使うmain関数を見ます。
入力された数列の各々の数値において、 与えられた数列で作りだせるかどうかをsolve関数を使って
判定しています。

int n,A[50];

int main(){
    int q,m;
    
    scanf("%d",&n);
    
    for(int i = 0;i < n;++i){
        scanf("%d",&A[i]);
    }
    
    scanf("%d",&q);
    
    for(int i = 0;i < q;++i){
        scanf("%d",&m);
        if(solve(0,m))printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

2分探索アルゴリズムの考え方とc++のソース

2分探索アルゴリズムとは

2分探索(binary search)アルゴリズムは、まず昇順or降順にソートした後に、探索開始位置を2分しながら
数値の大小をチェックし探索していくアルゴリズムになります。

では、2分探索のアルゴリズムの使用例を見ていきます。

2分探索アリゴリズムの使用例

以下のような要素を10個持つ数列があるとします。

10 8 12 6 14 4 16 2 18 20

この数列を2分探索を行うために、昇順または降順にソートします。
今回は、昇順にソートします。

2 4 6 8 10 12 14 16 18 20

では、この数列から4が存在するかどうかを
2分探索アルゴリズムを使い、探索してみます。

2分探索では探索位置を記憶するための変数として、
左辺値(left)・中央値(center)・右辺値(right)
を使います。
役割をそれぞれ説明すると、

左辺値(left)=先頭要素の位置

中央値(center)=左辺値と右辺値を足して2で割った中間の要素の位置

右辺値(right)=末尾の要素の位置

をそれぞれ示しています。

では、2分探索を実行してみます。

2分探索を実行する

1.中央位置を決定する

数列を配列だとみなすと、
leftが0、rightが9なので、centerが(0 + 9) / 2 = 4(小数点を切り捨てた)になるので、
探索位置はのindexは4です。

数列の要素4に該当するのは、

10です。

2.中央値とkeyとなる数値の大小をチェックする

探索値10とkey4の大小を調べます。

4 < 10なので、rightの9をcenterの4にし、
centerの値を再度計算します。

center = (0 + 4) / 2 = 2

後は、このように
1.2の計算を繰り返すことにより、
半分づつ探索位置をずらしながら、
探索を実行していきます。

では、2分探索のルールに従い探索を続けていきます。

center2の数値は6
一致しないので、
再度計算します。

rightに中央の位置を代入して、

right = 2

中央の位置を計算して、

center = (0 + 2) / 2 = 1

centerのindex1の数値は4となり一致したので、
2分探索終了です。

探索回数は3回でした。

探索値が大きかった場合

探索値が大きかった場合はleftを変更しますが、

leftの位置をずらす場合は、
left = center + 1
とします。

これは、keyとなる数値が探索数列内の値を超えていた場合 ループしてしまうからです。

2分探索の実行回数

2分しながら探索していていくことから、
探索回数はO(logn)になります。

c++のソースコード

最後にc++のソースコードを載せます

#include <iostream>

bool binarySearch(int numbers[],int length,int key){
    int left = 0;
    int right = length;
    int center;
    
    while(left < right){
        center = (left + right) / 2;
        if(key == numbers[center]) return true;
        else if(key > numbers[center]) left = center + 1;
        else right = center;
    }
    return false;
}

int main(int argc, const char * argv[]) {
    int numbers[] = {2,4,6,8,10,12,14,16,18,20};
    printf("%d",binarySearch(numbers, 10, 4));
    printf("%d",binarySearch(numbers, 10, -2));
    return 0;
}