paiza * qiita記事投稿キャンペーンに参加してみた：Aランクスキル「本の整理 C編」

はじめに

paizaとqiitaの記事投稿キャンペーンに参加してみました。の流れでBランクの問題にもチャレンジ内容を解説しました。
・関連記事
https://qiita.com/hyonkichi/items/b17aef92bb560d6a53f3
https://qiita.com/hyonkichi/items/33890d18cf8d2ff57e0e
https://qiita.com/hyonkichi/items/a483c3bea4942be878ca

問題

#解答コード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
    // 自分の得意な言語で
    // Let's チャレンジ！！
    char str[1000000];
    char *pstr;
    int i,j;
    int book_num;
    int book_list[100000]={0};
    int chg_cnt=0;
    int id_buf, id_min_pos;
    
    //冊数取得
    fgets(str, sizeof(str), stdin);
    sscanf(str, "%d\n", &book_num);
    //printf("book_num=%d\n",book_num);
    
    //本棚情報取得
    fgets(str, sizeof(str), stdin);
    pstr = strtok((char*)str, " ");
    for(i=0; i<book_num; i++)
    {
        book_list[i] = atoi(pstr);
        //printf("book_list[%d]=%d\n",i,book_list[i]);
        pstr = strtok(NULL, " ");
    }    
    
    //本の入れ替え回数算出
    for(i=0; i<(book_num-1); i++)
    {
        id_min_pos = i;
        for(j=(i+1); j<book_num; j++)
        {
            if(book_list[id_min_pos] > book_list[j])
            {
                id_min_pos = j;
            }
        }
        
        if(i!=id_min_pos)
        {
            id_buf = book_list[i];
            book_list[i] = book_list[id_min_pos];
            book_list[id_min_pos] = id_buf;
            chg_cnt++;
        }
    }

    printf("%d",chg_cnt);
    return 0;
}

解説

与えられた本のリストをソートし、その過程で本の入れ替えが行われた回数を計算します。具体的には、選択ソートというアルゴリズムを使用して本のリストを昇順に並べ替え、その際に必要となった入れ替えの回数をカウントします。
プログラムの流れを以下示します。

変数の定義と初期化:

str[1000000]は、標準入力から取得した文字列を格納するためのバッファです。
book_list[100000]は、与えられた本のリストを格納するための配列です。最大100,000冊の本がリストに含まれることを前提としています。
chg_cntは、本の入れ替えが行われた回数をカウントするための変数です。
id_bufは、ソート中に本の位置を一時的に入れ替えるために使用する変数です。
id_min_posは、現在の範囲で最小の本の位置を保持する変数です。

本の冊数と本棚情報の入力:

最初に、入力から本の冊数を取得し、book_numに格納します。
次に、本棚にある本のリストを取得し、スペース区切りで分割して整数に変換し、book_list配列に格納します。この際、strtok関数を使用して文字列を分割しています。

選択ソートによる本の入れ替え回数の計算:

選択ソートは、リストの中から最小の要素を選び、それを現在の位置に移動させるアルゴリズムです。このプログラムでは、外側のforループがリストの各要素を走査し、その要素に対応する最小値を見つけます。
内側のforループでは、現在の要素とそれ以降の要素を比較し、最小の要素の位置を見つけます。
最小の要素が現在の位置にない場合、2つの要素を入れ替え、chg_cntを増加させます。これにより、入れ替えが発生した回数をカウントできます。

結果の出力:

ソートが完了すると、chg_cntの値を出力します。この値は、与えられた本のリストをソートするために行われた入れ替えの回数を表します。
選択ソートアルゴリズムについて
選択ソートは、非常にシンプルなソートアルゴリズムであり、以下の手順で動作します。
リストの最初の要素を基準にし、それ以降の要素と比較して最小の要素を見つける。
最小の要素を現在の位置と入れ替える。
この操作をリスト全体に対して繰り返す。
選択ソートの計算量はO(n^2)であり、特に大きなリストに対しては効率的ではありませんが、入れ替えの回数が明示的に計算されるため、この問題のように入れ替えの回数が重要な場合には適しています。

ちなみに

はじめにコードを提出した際、いくつか"ランタイムエラー"になったので、見直したところ、char str[x];のサイズが足りておらず標準入力を受けきれていませんでした。
デフォルトでchar str[1000];が記述されるので、ここは触らないものだと決めつけてました..