数を昇順に並べて表示する

一般的に使われている８通りの方法でソートしてみました。
あなたはどの方法を使っていますか？
クイックソートやツリーソートに付いては、またの機会に説明します。
TEXT FILE から DATA を入力して、昇順に並べて表示します。

前田稔(Maeda Minoru)の超初心者のプログラム入門

入力データの形式

最初にデータ件数をタイプし、続いて件数分の整数データを空白で区切って並べます。
5  2  5  3  1  4

関数の呼び出し形式

t[] に格納されたデータを昇順に並べ替えます。
void    sort(int t[], int n);
パラメータの説明。
t[] 整数データが格納された配列
n 配列に格納されているデータ件数

方法－１

基本ソート（標準ソート）などと呼ばれる方法で、最初のデータの並び方に関係なく処理時間は同じです。
  1. データ件数を n とします。
    2 5 3 1 4
  2. i を 0 から始めて n-2 まで、次の項目(3.)を繰り返します。
    次の項目(3.)の繰り返しが終わる毎に i 番目から後の数値で一番小さいものが i 番目に格納されます。
    2 5 3 1 4関数に渡された最初の状態
    1 5 3 2 40 番目に一番小さい数が格納される
    1 2 5 3 41 番目に次に小さい数が格納される
    1 2 3 5 42 番目にその次に小さい数が格納される
    1 2 3 4 53 番目にその次に小さい数が格納される
  3. j を i+1 から始めて n-1 まで、次の項目(4.)を繰り返します。
  4. i 番目＞j 番目のとき、i 番目と j 番目を入れ替えます。
void    sort(int t[], int n)
{   int     i,j,w;

    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
            if (t[i]>t[j])
            {   w= t[i];
                t[i]= t[j];
                t[j]= w;
            }
}

方法－２

隣接交換法などと呼ばれる方法で、最初のデータの並び方に関係なく処理時間は同じです。
  1. データ件数を n とします。
    5 4 3 2 1
  2. i を n-1 から始めて 1 まで、次の項目(3.)を繰り返します。
    次の項目(3.)の繰り返しが終わる毎に最後尾から順に一番大きな値が格納されます。
    5 4 3 2 1関数に渡された最初の状態
    4 3 2 1 54 番目に一番大きな数が格納される
    3 2 1 4 53 番目に次に大きな数が格納される
    2 1 3 4 52 番目にその次に大きな数が格納される
    1 2 3 4 51 番目にその次に大きな数が格納される
  3. j を 0 から始めて i-1 まで、次の項目(4.)を繰り返します。
  4. j 番目＞ j+1 番目のとき、領域の値を入れ替えます。
void    sort(int t[], int n)
{   int     i,j,w;

    for(i=n-1; i>0; i--)
        for(j=0; j<i; j++)
            if (t[j]>t[j+1])
            {   w= t[j];
                t[j]= t[j+1];
                t[j+1]= w;
            }
}

方法－３

隣接交換法の改良版で、データの並び方によってはすぐにソートが完了します。
  1. データ件数を n とします。
    5 1 2 3 4
  2. i を n-1 から始めて入れ替えが無くなるまで、次の項目(3.)を繰り返します。
    次の項目(3.)の繰り返しが終わる毎に最後尾から順に一番大きな値が格納されます。
    5 1 2 3 4関数に渡された最初の状態
    1 2 3 4 54 番目に一番大きな数が格納される
    1 2 3 4 5入れ替えが無くなったので終了する
  3. j を 0 から始めて i-1 まで、次の項目(4.)を繰り返します。
  4. j 番目＞ j+1 番目のとき、領域の値を入れ替えます。
    DATA としてゼロの値は入力されないことを前提として w!=0 でループしています。
    ゼロの値が入力されるときは、入れ替えが起こったとき、それを識別する方法を講じてください。
void    sort(int t[], int n)
{   int     i,j,w;

    w= 1;
    for(i=n-1; w!=0; i--)
        for(w=j=0; j<i; j++)
            if (t[j]>t[j+1])
            {   w= t[j];
                t[j]= t[j+1];
                t[j+1]= w;
            }
}

方法－４

隣接交換法をさらに改良した方法で、シェーク法などと呼ばれています。
前回の方法では小さな値が後に格納されているとき繰り返し回数が増えます。
そこでシェークを振るように後に大きな値を、前に小さな値を交互に寄せ集めます。
  1. データ件数を n とします。
    10 2 3 4 5 6 7 8 9 1
  2. i を 0 から始めて入れ替えが無くなるまで、3. と 4. を交互に繰り返します。
    3. の繰り返しが終わる毎に最後尾から順に一番大きな値が、4. の繰り返しが終わる毎に最前列から 順に一番小さな値が格納されます。
    10 2 3 4 5 6 7 8 9 1関数に渡された最初の状態
    2 3 4 5 6 7 8 9 1 109 番目に一番大きな数が格納される
    1 2 3 4 5 6 7 8 9 100 番目に一番小さな数が格納される
    1 2 3 4 5 6 7 8 9 10入れ替えが無くなったので終了する
  3. j を 0 から始めて n-i-2 まで、項目(5.)を繰り返します。
    入れ替えが無くなったら終了です。
  4. j を n-2-i から始めて 0 まで、項目(5.)を繰り返します。
    入れ替えが無くなったら終了です。
  5. j 番目＞ j+1 番目のとき、領域の値を入れ替えます。
    DATA としてゼロの値は入力されないことを前提として w!=0 でループしています。
    ゼロの値が入力されるときは、入れ替えが起こったとき、それを識別する方法を講じてください。
void    sort(int t[], int n)
{   int     i,j,w;

    w= 1;
    for(i=0; w!=0; i++)
    {   for(w=j=0; j<n-1-i; j++)
            if (t[j]>t[j+1])
            {   w= t[j];
                t[j]= t[j+1];
                t[j+1]= w;
            }
        if (w==0)   break;
        for(w=0,j=n-2-i; j>=0; j--)
            if (t[j]>t[j+1])
            {   w= t[j];
                t[j]= t[j+1];
                t[j+1]= w;
            }
    }
}

方法－５

二つの配列を用いて小さな値から順に取り出す方法で、データの並び方による処理時間の違いはほとんどありません。
  1. データ件数を n とします。
    1 5 2 4 3
  2. データを作業用の配列 tw[] にコピーします。
  3. i を 0 から始めて n-1 まで、次の項目(4.)を繰り返します。
    繰り返しが終わると t[i] に w の値を代入して tw[p] に大きな値をセットします。
    次の項目(4.)の繰り返しが終わる毎に、配列 t[] には先頭から順に小さな値が格納されて行きます。
    1 0 番目に一番小さな数が格納される
    1 2 1 番目に次に小さな数が格納される
    1 2 3 2 番目にその次に小さな数が格納される
    1 2 3 4 3 番目にその次に小さな数が格納される
    1 2 3 4 54 番目にその次に小さな数が格納される
  4. tw[] の中から一番小さな値を見つけて、値を w に その番号を p にセットします。
    この値が次の t[i] に格納する値です。
    30000 は値を取り出したことを示す印として使っています。
void    sort(int t[], int n)
{   int     i,j,w,p;

    for(i=0; i<n; i++)  tw[i]= t[i];
    for(i=0; i<n; i++)
    {   w= tw[0];
        p= 0;
        for(j=1; j<n; j++)
            if (w>tw[j])
            {   w= tw[j];  p= j;   }
        t[i]= w;
        tw[p]= 30000;
    }
}

方法－６

二つの配列を用いて小さな値から順に取り出す方法で、データの並び方による処理時間の違いはほとんどありません。
方法ー５との違いは、毎回値を直接 w に格納しないで、その場所だけを p に記憶しておきます。
従って作業領域 w は使いません。
  1. データ件数を n とします。
    1 5 2 4 3
  2. データを作業用の配列 tw[] にコピーします。
  3. i を 0 から始めて n-1 まで、次の項目(4.)を繰り返します。
    繰り返しが終わると t[i] に tw[p] の値を代入して tw[p] に大きな値をセットします。
    次の項目(4.)の繰り返しが終わる毎に、配列 t[] には先頭から順に小さな値が格納されて行きます。
    1 0 番目に一番小さな数が格納される
    1 2 1 番目に次に小さな数が格納される
    1 2 3 2 番目にその次に小さな数が格納される
    1 2 3 4 3 番目にその次に小さな数が格納される
    1 2 3 4 54 番目にその次に小さな数が格納される
  4. tw[] の中から一番小さな値を見つけて、その番号を p にセットします。
    30000 は値を取り出したことを示す印として使っています。
void    sort(int t[], int n)
{   int     i,j,p;

    for(i=0; i<n; i++)  tw[i]= t[i];
    for(i=0; i<n; i++)
    {   for(p=0,j=1; j<n; j++)
            if (tw[p]>tw[j])    p= j;
        t[i]= tw[p];
        tw[p]= 30000;
    }
}

方法－７

挿入法と呼ばれる方法でデータは頭から順に取り出す代わりに、格納するときにシーケンスを崩さないように 後方にずらして挿入します。
最初から揃っている方が「ずらす手間」が少ない分だけ処理時間が早くなります。
  1. データ件数を n とします。
    1 5 2 4 3
  2. データを作業用の配列 tw[] にコピーします。
  3. i を 0 から始めて n-1 まで頭から順にデータを取り出します。
  4. シーケンスを崩さないで取り出したデータを格納する位置を調べます。
  5. 格納する位置から後方のデータを一つずつ後方にずらします。
  6. 空いた場所にデータを格納します。
  7. 配列 t[] には先頭から取り出したデータが順に格納されて行きます。
    1 0 番目に一番目に取り出した数が格納される
    1 5 1 番目に二番目に取り出した数が格納される
    1 2 5 1 番目に三番目に取り出した数が挿入される
    1 2 4 5 2 番目に四番目に取り出した数が挿入される
    1 2 3 4 52 番目に五番目に取り出した数が挿入される
void    sort(int t[], int n)
{   int     i,j,p;

    for(i=0; i<n; i++)  tw[i]= t[i];
    for(i=0; i<n; i++)
    {   for(p=0; p<i && tw[i]>t[p]; p++);
        for(j=i; j>p; j--)  t[j]= t[j-1];
        t[p]= tw[i];
    }
}

方法－８

今までの方法は直接データを入れ替え(コピー)していましたが、レコードなどデータ長が大きい場合に 毎回入れ替えるのは処理時間の無駄です。
そこでデータそのものは入れ替えずに、場所を示す添え字を入れ替える間接ソートが考えられます。
今まで述べた全ての方法に間接ソートを用いることが出来るのですが、今回は基本ソートに応用してみます。
  1. p[] に t[] のデータを昇順に参照できる添え字を求めます。
    p[n] には、最初 0～n-1 を格納します。

  2. ソートが済んだデータを小さい順に取り出して t[] に格納するために w[] にコピーしておきます。

  3. p[i] を添え字として t[p[i]] から小さい順に取り出すことができるように p[] を入れ替えます。
    方法は基本ソートと同じです。

  4. p[i] が指す値を順に w[p[i]] から取り出して t[i] に格納します。

void    sort(int t[], int n)
{   int     i,j,w;
    int     p[MAX];

    for(i=0; i<n; i++)
    {   tw[i]= t[i];
        p[i]= i;
    }
    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
            if (t[p[i]]>t[p[j]])
            {   w= p[i];
                p[i]= p[j];
                p[j]= w;
            }
    for(i=0; i<n; i++)  t[i]= tw[p[i]];
}

この後のページに「再起関数を使ったソート」と「Binary Tree ソート」を掲載しています。
再起関数を使ってソート
Binary Tree ソート

超初心者のプログラム入門(C/C++)

※・