パンチカードとグレイ符号

  1. パンチカード


    1. パンチカードとは

      　パンチカードは、厚紙の縁に、縁まで貫通した穴（角穴）と貫通しない丸穴の2種類の穴をあけたカードです。角穴は丸穴にパンチを特殊なハサミを入れて作ります。丸穴に棒を差し込んで、棒を上げると、カードを引き抜くことができます。縁まで拡がる角穴は、棒を上げてもカードを抜き取ることはできません。丸穴を１、角穴を０で表現します。

    2. 情報の符号化と検索

      　個人情報カードを作成します。性別の穴をあけ、男性を０、女性を１とします。この穴に棒を差し込んで引き上げると、女性のカードを引き抜くことができます。
      　８種の職業欄を設け、3個の穴で職業を表現します。特定の職業のカードを引き抜くには、どうしたらよいでしょうか？
      　ヒント：複数の棒を利用します。

    3. カードの整列

      　カードに2進数の番号の穴をつけておきます。この穴を利用すると、次で述べる方法で１０００枚のカードを10回の操作で整列できます。
      まず、最初に１の桁に棒を通し、カードを引き抜きます。このカードを、元のカードの後ろに並べます。この操作で、「1 の桁」が１のカードが後ろにきます。たとえば、2,3,4 のカードの場合、3 が後ろにきて 2,4,3 の順になります。
      　次に、２の桁で同じ操作をします。これで、1,2 の桁に関しては順に並びます。
      4,8 の桁で同様な操作をすれば、カードの整列ができます。
      千枚のカードは10個の穴(2進数)で表現できますから、10回の操作で整列できます。（210=1024）

      例 / 以後が並べ替えられたカードです。/ 以後が抜き取られたカードです。
      5,3,6,9,10,12,4,2,1,11,7,8 //最初の並び
6,10,12,4,2,8/5,3,9,1,11,7 //1の桁で並べかえ
12,4,8,5,9,1/6,10,2,3,11,7　//２の桁
8,9,1,10,2,3,11/12,4,5,6,7  //４の桁
1,2,3,4,5,6,7,8,9,10,11,12  //8の桁

    4. 演習

      5,3,2,7,8 4枚のカードの並べ替えをしてください。
      ヒント ：2進数で並べ直します。

  2. 基数ソート


    1. プログラムの手法

      　このパンチカードの並べ替え手法は、計算機プログラムでは基数ソートと呼ばれる方法に対応します。10進数の場合、基数は 1,10,100,1000 の桁の数になります。最初１桁目の数を基数として並べます。
      　以後、並べ替える桁を増やしながら、前の順番を変更しないよう、並べ替えます。この方法は（メモリが余分に必要ですが）、データ数をn、桁数をmとしたとき、ほぼ、n * m で並べ替えが可能で、高速なソート手法になります。2進数の場合、m = log2nですから、n * log2n で並べ替えができます。

    2. 問題

      パンチカードでは、 log2n で並べ替えができました。この違いはなんでしょう？

    3. プログラム

      void RadixSort(int x[ ], int n, int r) 関数が、実際の並べ替えをします。並べかえる桁の数を rad[i] に記録します。この値順に、y[] に値を記録します。

      //http://www1.cts.ne.jp/~clab/hsample/Sort/Sort5.html　より
// RadixSort.cpp : コンソール アプリケーション用のエントリ ポイントの定義

#include "stdafx.h"
#include  <stdio.h>

#define NUM_DATA 10  //定数

int rad[NUM_DATA];    /* 基数に対応する数を記録する整数(int)配列  */
int y[NUM_DATA];      /* 作業用の整数配列 */

/* n 個のデータを表示する関数 */
/* x[ ]：表示するデータ */
/* n：データの数 */
void ShowData(int x[ ], int n)
{
    int i;
    for (i = 0; i < n ; i++)
        printf("%d\t", x[i]);//整数x[i]を表示
                printf("\n");//改行
}

/* 基数法でソートを行う */
/* x[ ]：ソートするデータ */
/* n：データの数 */
/* r：基数の最大値 4桁の数なら1000*/
void RadixSort(int x[ ], int n, int r)  
{                                       
    int i, j, k;                        
    int m = 1;    // 基数

    while (m <= r) {
        for (i = 0; i < n; i++)     //i++ ：iを１増す
            rad[i] = (x[i] / m) % 10;   /* 基数を取り出し rad[i] に保存 %は余り演算*/

        k = 0;                          /* 次のデータの位置*/
        for (i = 0; i <= 9; i++)        /* 基数は 0 から 9 */
            for (j = 0; j < n; j++)
                if (rad[j] == i)       //基数の小さいものからy[]にコピー
                    y[k++] = x[j];     //y[k++]は　y[k]に保存後、kを増加

        for (i = 0; i < n; i++)
            x[i] = y[i];                /* x[ ] にコピーし直す */
        
          /*  途中経過を表示  */
        printf("\nソート中:%d の桁でソート\n",m);
        ShowData(x, n);
                                
        m *= 10;       /*  基数を取り出す桁を一つ上げる */
    }
}


//ここから実行開始
void main(void)
{      /* ソートするデータ */
    int x[NUM_DATA] = { 5489, 1473, 7853, 1058, 9448,
                        1118, 7979, 2163, 1856, 3117};

    int n = 10;        /* ソートするデータ数 */
    int r = 1000;      /* ソートするデータから取り出す基数（最大1000） */
        
    /* ソート前のデータを表示 */
    printf("ソート前:\n");
    ShowData(x, n);
    
    RadixSort(x, n, r);
                
}
      実行のようす
      ソート前:
5489    1473    7853    1058    9448    1118    7979    2163    1856    3117

ソート中:1 の桁でソート
1473    7853    2163    1856    3117    1058    9448    1118    5489    7979

ソート中:10 の桁でソート
3117    1118    9448    7853    1856    1058    2163    1473    7979    5489

ソート中:100 の桁でソート
1058    3117    1118    2163    9448    1473    5489    7853    1856    7979

ソート中:1000 の桁でソート
1058    1118    1473    1856    2163    3117    5489    7853    7979    9448

    4. 演習

      ２４５，３６４，１８３，581,４５３，を基数法で並べ替えてください。

  3. 演習、課題


    1. 並べ替え

      　0011,0101,1010,1100,0111,0010, を基数のパンチカードがある。これを、下の桁から順にソートした結果を表示してください。

    2. アンケート

      パンチカードによる検索は理解できましたか？
      　１．できた　　２．多分　　３．よくわからん
      パンチカードのよる並べ替えは理解できましたか
      　　１．できた　　２．多分　　３．よくわからん
      プログラムによるRadixSortは理解できましたか？
      　　１．できた　　２．多分　　３．よくわからん