[2750][c]수 정렬

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

 

<코드1>

 

void swap(int * a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

int main(void) {
int num,*numList;
scanf("%d", &num);
numList = (int*)malloc((sizeof(int))*num);
for (int i = 0; i < num; i++) {
scanf("%d", &numList[i]);
for (int j = i - 1; j >= 0; j--) {
if (numList[j] > numList[j + 1])
swap(&numList[j], &numList[j + 1]);

else break;
}
}
for (int i = 0; i < num; i++)
printf("%d ", numList[i]);

free(numList);

return 0;
}

<풀이1>

문제가 어렵지 않다. 어떻게 하면 더 짧게 할 수 있을지 고민된다.

일단 맨 처음에 입력받을 수의 개수를 scanf로 받고

그 수 만큼 동적으로 배열을 만든다.

이 후 수를 입력 받으며 정렬을 동시에 해준다.

입력 받은 그 수는 가장 뒤에 넣고 (이 때 이 앞에 있는 숫자들은 정렬된 상태이다.)

앞에 수들과 비교하며 자기 위치를 찾는다.

 

이 방법의 시간 복잡도를 계산 해보자.

먼저 n개의 수를 입력받으므로 n번은 기본적으로 돌고

최대 O(n)=n*n =n^2 

최소 O(n)=n => 저장을 해야하기 때문에 일단 n번 돌게 되고

               else break;문 넣어주어서 시간 복잡도 줄어들게 된다!

 

 

더 좋은 방법이 있을까???

 

삽입 정렬 , 거품 정렬 있다고 한다.

거품 정렬은 시간이 적게 걸린다하니 일단 자구 다시 공부 하기 전까지~