データ構造とアルゴリズム勉強会 #2

第2回目の内容

・安定なソート(構造体)
・スタック
・キュー

安定なソート(構造体)

問題:ALDS1_2_C
ソートの復習の問題となります。
同じ値の要素の順番が入れ替わらないようなソートを安定なソートと言いますが、ここではソートが安定か否かを判定する処理が追加されます。
問題ではバブルソートと選択ソートを指定されていますが、この部分は前回述べたので省略します。
また、問題で与えられるのはトランプのカードであり、例えばハートの6なら「H6」、スペードの13なら「S13」という風に入力されるので、まとめて扱うために構造体という概念を導入します。

struct card{
    char suit; //カードの種類
    char value; //カードの数字
};

このchar,valueはメンバ変数と呼ばれ、構造体の中に含まれる要素を指定します。カードはchar型の変数suit,valueに格納されるので、例えばH6ならHがsuit、6がvalueという名前を持っているというイメージでよいです。入力を受け取る処理は以下のようになります。

int N; cin >> N;
vector<card> a(N), b(N); //is_stableの判定のために2つ必要

for(int i=0; i < N; ++i){
    cin >> a[i].suit >> a[i].value;
    b[i].suit = a[i].suit;
    b[i].value = a[i].value;
}

ソートの安定性の判定のために配列は2つ設定していますが、本質的に重要なのは構造体の指定です。a[i]の中には変数suitとvalueがあるので、それぞれを指定してあげます。

次にソートの安定性の判定です。
バブルソートはそもそも安定なソートなので、これと選択ソートの要素が一致しているかを判定します。

void bubble_sort(vector<card> &a){(省略)}

void selection_sort(vector<card> &b){(省略)}

bool is_stable(vector<card> &a, vector<card> &b){
    for(int  i=0; i < a.size(); ++i){
        if(a[i].suit != b[i].suit) return false;
    }

    return true;
}

返り値はbool型とし、ソートが安定ならtrue、不安定ならfalseを返します。
バブルソート、選択ソートが終わった配列のそれぞれの要素同士を比べ、カードの種類suitが違っていればソートは不安定と判定します(配列の大きさは同じなので、for文の回す回数はa.size()でもb.size()でも構いません)。というのも、バブルソートは安定なので、同じインデックスの場所に選択ソートが違う種類のカードを格納していればそれはどこかで同じ値のカードの順番が入れ替わっているということになるからです。
この問題から学べることは以上です。

スタック

問題:ALDS1_3_A
スタックとは、順番にデータを受け入れていき、最後に受け取ったデータから(新しい方から)順に取り出していくデータ構造です。
例えば[0, 1, 2, 3, 4]とデータを受け取ったら、データを取り出す順番は4, 3, ...となります。
実装は以下のようになります。

int top = 0, S[1000]; //データの受け入れ場所となる配列、データを受け取る番号を指定

//データの受け取り
void push(int x){
    ++top;
    S[top] = x;
}

//データの取り出し
int pop(){
    --top;
    return S[top+1];

topはデータを出し入れする場所、つまり先ほどの配列で言えば4の次の場所を指定する変数です。S[1000]は大きさ1000の配列で、ここを使ってデータを出し入れしていきます。
push関数ではデータを受け入れますが、まずtopをインクリメントしてそこに受け取ったデータを格納します。つまりS[0]には何も入りません。
popではデータを取り出しますが、一旦topをデクリメントしてそこから+1した場所のデータを取り出します。例えば5を取り出したら配列は[0, 1, 2, 3]になりますが、次に取り出したいのは3で、これのインデックスは3,もしtopをデクリメントしなかったらtop=4のままでありデータを取り出せなくなってしまいます。またpushでデータを格納しようとしても1つ配列に空きができてしまいます。そのような理由でtopをデクリメントします。

キュー

問題:ALDS1_3_B
キューはスタックとは違い、要素をいれた順番でそのまま取り出します。例えばタピオカに群がる人々は(モラルがあれば)並んだ順番に買っていくでしょう。
実装はこのような感じです。

struct process{(省略)};

const int MAX = 100005;
process Q[MAX];
int head = 0, tail = n;

void enqueue(process x){
    Q[tail] = x;
    tail = (tail+1)%MAX; //余りにすることでメモリのオーバーフローを防ぐ。
}

process dequeue(){
    process x = Q[head];
    head = (head+1)%MAX; //余り
    return x;
}

constで変数MAXを変更できないようにしています。Qが作業領域となるので十分な大きさを確保しておきます。何かデータの列があるとして、headがその先頭を、tailがその最後を指定しています。tailは便宜的にnとしておきます。enqueue関数でデータをQのデータ列の末尾に与えますが、tailを更新する際にMAXで割った余りにしておくとよろしいです。仮にMAXを超える回数の処理がなされた時、次に格納されるデータのインデックスが100006ではなく1となり、Qの領域を再利用できるからです。
dequeueでは先頭を取り出して返り値とし、またheadの値も更新しますがやはりこちらもMAXで割った余りにします。

まとめ

問題自体の実装・考察は他にもありますが、ここでは新たに学んだデータ構造・アルゴリズムを整理して書き出すことを目的としていますので今後も適宜省略していきます。今回は構造体・スタック・キューを学びました。構造体はデータをより効率よく扱うことができるツールとして有用で、またスタックとキューは対照的で、かつ基本的なデータの受け取り・取り出しを学ぶのに最適なデータ構造でした。