Sorting an array

There's an array of values from 1 to n. It isn't sorted. We have to sort it, but there are only to ways to move: third element to beginning or last element to beginning. How to do that ?

#include <stdio.h>

#define TREE_MAX     16
#define TREE_POWER_2 65536

#define ARRAY_SIZE 4

int tree[TREE_POWER_2][TREE_MAX];

void show(int *a)
{
    int i;
    for(i = 0; i < ARRAY_SIZE; i++)
        printf("%d", a[i]);
}

void swap_third(int *a)
{
    int tmp = a[0];
    a[0] = a[2];
    a[2] = tmp;
}

void swap_last(int *a)
{
    int tmp = a[0];
    a[0] = a[ARRAY_SIZE-1];
    a[ARRAY_SIZE-1] = tmp;
}

int sorted(int *a)
{
    int i;
    for(i = 1; i < ARRAY_SIZE; i++)
        if(a[i - 1] > a[i])
            return 0;
    return 1;
}

int main(void)
{
    int i, nsorted = 0;

    /*
     * tree:
     *    0000 0000
     *    0000 0001
     *    0000 0010
     *    0000 0011
     *    ...
     *    1111 1111
     *
     * 0 means swap_last
     * 1 means swap_third
     */


    for(i = 0; i < TREE_POWER_2; i++){
        int *a = tree[i];
        int  n = i, j = 0;

        for(j = 0; j < TREE_MAX; j++){
            a[j] = n % 2;
            n /= 2;
        }
    }

    for(i = 0; i < TREE_POWER_2; i++){
        int a[ARRAY_SIZE] = { 4, 2, 1, 3 };
        int j;

        for(j = 0; j < TREE_MAX; j++){
            printf("iteration %02d: ", j + 1);
            show(a);
            if(tree[i][j]){
                printf(" (third) ");
                swap_third(a);
            }else{
                printf(" (last ) ");
                swap_last(a);
            }
            printf(" -> ");
            show(a);
            putchar('\n');

            if(sorted(a)){
                puts("  sorted!");
                nsorted++;
                break;
            }
        }

        if(j == TREE_MAX)
            puts("  not sorted :(");
    }

    printf("---\nstats (with %d iterations)\nsorted: %d, not sorted: %d\n",
            TREE_MAX, nsorted, TREE_POWER_2 - nsorted);

    return 0;
}

No need to thank me.