#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <string.h>


int main(void){

int n, datas[128], i, k, tmp, s;


// 쉘 정렬 알고리즘이야

// 공부한지 5일 된 거면 걍 배열로 잡을께

// 메모리 할당이고 뭐고 그짓해버렸다간 

// 너 머리통 터진다


while (1){

printf("몇개나 입력할거냐 ? ");

scanf("%d", &n);

flushall();


if (n > 128 || n < 0)

printf("0 ~ 128 사이로 똑디 입력해라 ");

else break;

}


for (i = 0; i < n; i++){

printf("%d번째 데이터 : ", i);

scanf("%d", &datas[i]);

}


k = n;

while (k > 0){

s = 1;

while (s > 0){

for (i = 0; i < n - k; i++){

if (datas[i] > datas[i + k]){

tmp = datas[i];

datas[i] = datas[i + k];

datas[i + k] = tmp;

s++;

}

}


s--;

}


if (k <= 1)

break;


if (k > 2)

k = k / 2 + ((n % 2) > 0 ? 1 : 0);

else k = 1;

}


for (i = 0; i < n; i++){

printf("%d번째 데이터 : %d ", i, datas[i]);

}


return 0;

}