/*
 * 単純挿入法(Insertion Sort)
 * DACCHO wrote this sample program.
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void output_array(int *ptr, int n);
void insert_sort(int *ptr, int n);
void swap(int *ptr1, int *ptr2);

int main(void)
{
    int a[20];
    int i;

    srand((unsigned)time(NULL));
    for(i=0; i<20 ; i++)
        a[i] =rand() %100;

    printf("*** 単純挿入法(Insertion Sort)によるソート ***\n");
    printf("ソート前のデータの並び\n");
    
    output_array(a, 20);

    printf("Press Enter Key\n");
    getchar();

    printf("ソート後のデータの並び\n");
    insert_sort(a, 20);
    output_array(a, 20);

    printf("Press Enter Key\n");
    getchar();

    return 0;
}

void output_array(int *ptr, int n)
{
    int i;

    for(i=0; i<n; i++){
        printf("%2d : %d\n", i+1, *ptr);
        ptr++;
    }
    return;
}

void insert_sort(int *ptr, int n)
{
    int i, j, k;

    for(i=1; i<n; i++){
        k = *(ptr+i);
        
        /* 以下の行の判定を「k<*(ptr+j)」から「k>*(ptr+j)」へ変更すると降順になります */
        for(j=i-1; j>=0 && k<*(ptr+j); j--){
            *(ptr+j+1) = *(ptr+j);
        }
        *(ptr+j+1) = k;
    }
}