昨日のパナソニックプログラミングコンテストは先週の日立に続けて冷えたので、しばらく基礎固めにいそしみます。
蟻本のレベルが高すぎてまだ早いので「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」をテキストにＡＯＪ（会津オンラインジャッジ）を使って勉強を進めます。
平行してＡｔＣｏｄｅｒ Problemsのリコメンの精進も継続します。
（ＡｔＣｏｄｅｒ Problemsの精進は現在４４７ＡＣ。）
まずはソートアルゴリズムの基本、挿入ソートから。
ＡＯＪのALDS 1_1_A です。
プログラムの挙動を可視化するためforループの終わりに”＃”、whileループの終わりに”＊”を出力します。
２番目の数字からスタートしているのは、１番目は１周も回らずに終わるからですね。
挿入ソート：
#include <bits/stdc++.h>
using namespace std;
using namespace std;
int main(){
int N;
cin >>N;
vector <int> a(N);
for (int i=0;i<N;i++){
cin>>a[i];
}
for(int k=0;k<N;k++){
if(k<N-1){
cout<<a[k]<<" ";
}
else cout<<a[k]<<endl;
}
for (int i=1;i<N;i++){
int v=a[i];
int j=i-1;
while((j>=0)&&(a[j]>v)){
a[j+1]=a[j];
j--;
cout<<"*"<<endl;
}
a[j+1]=v;
for(int k=0;k<N;k++){
if(k<N-1){
cout<<a[k]<<" ";
}
else cout<<a[k]<<endl;
}
cout<<"#"<<endl;
}
return 0;
}
int N;
cin >>N;
vector <int> a(N);
for (int i=0;i<N;i++){
cin>>a[i];
}
for(int k=0;k<N;k++){
if(k<N-1){
cout<<a[k]<<" ";
}
else cout<<a[k]<<endl;
}
for (int i=1;i<N;i++){
int v=a[i];
int j=i-1;
while((j>=0)&&(a[j]>v)){
a[j+1]=a[j];
j--;
cout<<"*"<<endl;
}
a[j+1]=v;
for(int k=0;k<N;k++){
if(k<N-1){
cout<<a[k]<<" ";
}
else cout<<a[k]<<endl;
}
cout<<"#"<<endl;
}
return 0;
}
入力
6
8 3 1 5 2 1
8 3 1 5 2 1
出力
8 3 1 5 2 1
*
3 8 1 5 2 1
#
*
*
1 3 8 5 2 1
#
*
1 3 5 8 2 1
#
*
*
*
1 2 3 5 8 1
#
*
*
*
*
1 1 2 3 5 8
#
*
3 8 1 5 2 1
#
*
*
1 3 8 5 2 1
#
*
1 3 5 8 2 1
#
*
*
*
1 2 3 5 8 1
#
*
*
*
*
1 1 2 3 5 8
#