#/***********************************************************
#    inssort.rb -- 挿入ソート
#***********************************************************/

def inssort(n,  a)  # a..n-1] を昇順に 
    for i in 1...n
        x = a[i]
        j = i - 1; while (j >= 0 && a[j] > x)
            a[j + 1] = a[j]
            j -= 1
        end
        a[j + 1] = x
    end
end

#      **** a[N] を番人として使う *************
=begin
#include <limits.h>  # INT_MAX の定義を含むファイル 
INT_MAX = 2147483647
def inssort(n,  a)
    a[n] = INT_MAX;  # 番人 
    for (i = n - 2; i >= 0; i -= 1) 
        x = a[i]
        for (j = i + 1; a[j] < x; j += 1)
            a[j - 1] = a[j]
        a[j - 1] = x
    end
end
=end
#       ***************************************

N = 20
a = []
a = []

printf("Before:")
for i in 0...N
    a[i] = (rand * 100 + 1).to_i
    printf(" %2d", a[i])
end
printf("\n")
inssort(N, a)
printf("After: ")
for i in 0...N; printf(" %2d", a[i]); end
printf("\n")

exit 0