1370: [정렬] 삽입 정렬
[만든사람 : 2015 개정 교육과정 고등학교 정보과학 (주)삼양미디어]
문제 설명
정보과학 교과서 154p
----
삽입 정렬(insertion sort)는 데이터들이 이미 정렬되어있는 상태에서 새로운 데이터가 추가되어 앞으로 당겨지는 과정을 반복하는 정렬 방법이다.
새로운 데이터가 반복적으로 추가되어 앞으로 이동하며 삽입되는 과정을 반복하며 정렬되기 때문에 삽입 정렬이라고 부른다.
n개의 정수 데이터를 입력받아 오름차순으로 정렬하여 출력하는 프로그램을 작성해보자.
단, 정렬 함수 sort() 를 사용할 수 없다.
#include <stdio.h>
int n, d[3010];
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &d[i]);
for(int i=2; i<=n; i++) //2번 데이터부터 새로 삽입된다고 생각한다.
{
int j=i;
while(j-1>=1 && d[j-1]>d[j]) //왼쪽에 있는 값이 오른쪽 값보다 크면, 자리를 바꾼다.
{
int t = d[j-1];
d[j-1] = d[j];
d[j] = t;
j--; //왼쪽으로 한 칸 이동해서 같은 방법으로 다시 비교한다.
}
}
for(int i=1; i<=n; i++)
printf("%d ", d[i]);
}
----
삽입 정렬(insertion sort)는 데이터들이 이미 정렬되어있는 상태에서 새로운 데이터가 추가되어 앞으로 당겨지는 과정을 반복하는 정렬 방법이다.
새로운 데이터가 반복적으로 추가되어 앞으로 이동하며 삽입되는 과정을 반복하며 정렬되기 때문에 삽입 정렬이라고 부른다.
n개의 정수 데이터를 입력받아 오름차순으로 정렬하여 출력하는 프로그램을 작성해보자.
단, 정렬 함수 sort() 를 사용할 수 없다.
#include <stdio.h>
int n, d[3010];
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &d[i]);
for(int i=2; i<=n; i++) //2번 데이터부터 새로 삽입된다고 생각한다.
{
int j=i;
while(j-1>=1 && d[j-1]>d[j]) //왼쪽에 있는 값이 오른쪽 값보다 크면, 자리를 바꾼다.
{
int t = d[j-1];
d[j-1] = d[j];
d[j] = t;
j--; //왼쪽으로 한 칸 이동해서 같은 방법으로 다시 비교한다.
}
}
for(int i=1; i<=n; i++)
printf("%d ", d[i]);
}
입력 설명
첫 번째 줄에 데이터의 개수(n)가 입력된다.
두 번째 줄에는 n개의 데이터(k)가 스페이스를 사이에 두고 한 줄로 입력된다.
[1 <= n <= 3000]
[0 <= k <= 2147483647]
두 번째 줄에는 n개의 데이터(k)가 스페이스를 사이에 두고 한 줄로 입력된다.
[1 <= n <= 3000]
[0 <= k <= 2147483647]
출력 설명
오름 차순으로 정렬한 결과를 스페이스를 사이에 두고 한 줄로 출력한다.
입력 예시 Copy
5
9 8 3 4 7
출력 예시 Copy
3 4 7 8 9