読者です 読者をやめる 読者になる 読者になる

データ・サイエンティストは可視化の夢を見るか?

Does Data Scientist Dream of Visualization?

『競プロ』の独学を再開する

プログラミング冥府魔道

今日和。
実は「本業」があるのですが、協業している方からのレスポンス待ちになっています。
そこで偶には好きなことを、という理由で、『競プロ』の独学を再開しました。
もう、スピード勝負、あんまり考えずに写経していきます。
何故なら、いまやっている章は学部生時代、それなりに独学したところだからです。
確認で済むところは徹底的に駆け足で。



以下は一番基本的なソート、『挿入ソート』のコードの写経です。
C++ となっていますが実質 C です。
コメント・アウトしてあるところに入力例が書き込んであるので、お手元でビルドして実行させてみると insertion sort の動作が一目瞭然で理解できるでしょう。

#include <iostream>
#include <cstdio>


const int MAX_N = 100;


void trace( int A[], int N ) {
    int i;
    
    for ( i = 0; i < N; i++ ) {
        if ( i > 0 ) printf(" ");
        printf( "%d", A[i] );
    }
    printf("\n");
}


void insertionSort( int A[], int N ) {
    int i, j, v;
    
    for ( i = 1; i < N; i++ ) {
        v = A[i];
        j = i - 1;
        
        while ( j >= 0 && A[j] > v ) {
            A[j+1] = A[j];
            j--;
        }
        
        A[j+1] = v;
        trace( A, N );
    }
    
    
    return;
}


int main(int argc, const char * argv[]) {
    int i, N;
    
    int A[MAX_N];
    
    scanf("%d", &N);
    for ( i = 0; i < N; i++ ) scanf("%d", &A[i]);
    
    trace( A, N );
    insertionSort( A, N );
    
    return 0;
}


/*
6
5 2 4 6 1 3
*/


こういうことを勉強し直して、いろいろと忘却の彼方にあったものを再確認できると、なかなかストレス発散になりますね。(苦笑)