삽입정렬
삽입정렬이란?
삽입정렬은 크기가 n인 집합일 때,
2개, 3개, 4개 ... n-1개씩 비교대상이 늘어나는 것이 특징이다.
단, 사이클마다 대상 집합이 이미 정렬되어 있는 경우에는 비교가 일어나지 않는다. 그래서 무조건(정렬이 되어 있든 아니든) 비교하는 버블정렬보다 평균적으로는 성능이 좋다.
아래에서 예시로 정렬할 때 오름차순을 목표로 한다.
특징
1.정렬 대상이 처음에는 2개.
사이클을 반복할 때마다 1개씩 커집니다. 최대 n-1까지 커진다.
2.정렬 대상의 가장 오른쪽 요소가 대상 중에서 가장 큰 값인지 확인한다.
그렇지 않다면 그 것의 적절한 위치를 찾아준다. 자신보다 큰 요소를 만날 때 까지 탐색한다.
3.적절한 곳을 찾았다면, 자신보다 큰 요소들을 모두 한칸씩 앞으로 이동시킨다. 그리고 새로 생긴 곳에 위치시킨다.
예시
5 1 6 4 2 3
데이터 집합 크기는 6이다.
일단 비교 대상은 2개다. 5와 1.
가장 오른쪽 요소인 1이 가장 큰값을 가지는지 확인해본다.
1을 뽑는다. 1보다 큰 수 5 앞에 놓아야 한다.
5를 이동시켜서 오른쪽으로 밀어서 공간을 만든다.
빈 곳에 1을 삽입한다.
결과 : 1 5 6 4 2 3
비교 대상은 3개다. 1, 5, 6
가장 오른쪽 요소 6이 가장 큰 값을 가지는지 확인한다. (6을 그 앞의 숫자 5와 비교한다.)
6이 더 크다.
그 앞의 요소들은 이미 정렬을 거친 숫자들이니까 확인할 필요가 없다. (!!)
다음 단계로 넘어간다.
비교 대상은 4개다. 1, 5, 6, 4
가장 오른쪽 요소 4가 가장 큰 값을 가지는지 확인한다. (4를 그 앞의 수 6과 비교한다.)
4가 작으니까 이동이 필요하다.
4를 뽑는다.
6, 5, 1 순으로 탐색해보니까 1 앞에 오면 된다.
5와 6을 오른쪽으로 민다. 빈 공간에 4를 삽입한다.
결과 : 1 4 5 6 2 3
삽입정렬 코딩해보기 1
#include <stdio.h>
#include <string.h>
void InsertionSort(int dataset[], int length){
int i=0, j=0, target=0;
for(i=1; i<length; i++){
if(dataset[i-1] < dataset[i]){
continue; // 맨 오른쪽 요소가 가장 크다면 정렬이 필요 없다.
}
target = dataset[i]; // 맨 오른쪽 요소의 적절한 위치 탐색시작
for(j=0; j<i; j++){
if(dataset[j] > target){
// 데이터를 쭈욱 민다.
memmove(&dataset[j+1], &dataset[j], sizeof(dataset[0])*(i-j));
dataset[j] = target;
break;
}
}
}
}
int main(void){
int dataset[] = {5, 3, 6, 4, 1, 2};
int length = sizeof(dataset) / sizeof(int);
int i = 0;
InsertionSort(dataset, length);
for(i=0; i<length; i++){
printf("%d ", dataset[i]);
}
return 0;
}
memmove() 함수
메모리에 내용을 이동시키는 함수이다. C표준함수.
배열처럼 연속된 데이터를 이동시킬 때 유용하다.
반복문으로 이 함수의 기능을 구현할 수 있지만 성능이 떨어진다.
void* memmove(void* dest, const void *src, size_tn)
dest: 복사의 대상이 되는 목적지 주소
src: 복사할 원본이 있는 주소
size_tn : 복사할 메모리 길이 (byte)
memmove() 함수는 데이터를 '이동'시키고 memcpy() 함수는 데이터를 '복사'한다.
삽입정렬 코딩해보기 2
memmove() 메모리 복사 없이, 배열의 데이터 복사하는 방식으로 정렬해본다.
i와 j로 만든 이중 for문인데,
i는 1부터 시작한다. 비교 집합의 맨 오른쪽 수가 i인데 temp 변수에 기억해둔다.
j 반복문 안에서, temp 보다 큰 수가 있다면 하나씩 오른쪽으로 당긴다.
적절한 위치를 발견하는 순간 temp에 저장된 값을 삽입한다.
input.txt 입력 설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다.
6
11 7 5 6 10 9
출력 설명
오름차순으로 정렬된 수열을 출력합니다.
5 6 7 9 10 11
#include <stdio.h>
int main(int argc, char** argv){
int a[100], num=0, temp=0, i=0, j=0;
freopen("input.txt", "rt", stdin);
scanf("%d", &num); // 데이터 개수
for(i=0; i<num; i++){ // 데이터 저장
scanf("%d", &a[i]);
}
for(i=1; i<num; i++){ // 오름차순으로 정렬
temp = a[i]; // a[i]의 적당한 위치를 탐색 시작
for(j=i-1; j >= 0; j--){ // 오른쪽에서 왼쪽으로 순회
if(a[j] > temp){
a[j+1] = a[j];
}else{
break;
}
}
a[j+1] = temp; // 적당한 위치에 삽입.
}
for(i=0; i<num; i++){ // 정렬 결과
printf("%d ", a[i]);
}
return 0;
}
데이터집합이 3 2 4 5 라고 가정한다.
i는 인덱스 1부터 temp 에는 2 가 들어가 있다.
j는 인덱스 i-1부터 시작하니까 0 이 들어가 있다.
for문의 조건을 확인한다.
j는 0보다 크거나 같으니까, 반복문 안의 코드가 실행된다.
3이 2보다 크니까 if문 조건을 만족한다.
그래서 인덱스 1 자리에 인덱스 0의 값이 복사된다.
그 결과 3 3 4 5 가 된다.
반복문 안의 코드 수행이 끝났으니까, j--가 수행된다.
j는 -1이 된다.
다시 for문의 조건을 확인한다. j>=0 을 만족하지 못하니까 반복문을 종료한다.
j는 -1인 채로 남아 있었으니까, arr[j+1] 은 arr[0]을 의미한다.
그래서 인덱스 0 자리에 temp값 2를 넣는다.
그 결과 2 3 4 5 가 된다.
