삽입정렬(insertion_sort)

삽입정렬 : 정렬이 되어있지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치해 삽입하면서 정렬하는 방법

삽입정렬을 카드에 비유해보면, '1', '4', '5'가 적힌 카드가 있을 때 '3'이 적힌 카드를 '4'와 '5' 사이에 넣는 것과 같다.

그림

코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 10

void makeArray(int A[]){ // 배열 만드는 함수
    int i, j;
	srand(time(NULL));
    for(i = 0; i < SIZE; i++)
    	A[i] = rand() % 100; // 중복 제거 안 함
    	/* // 중복을 제거하고 싶은 경우
    	for(j = 0; j < i; j++){
    	    if(A[i] == A[j])
    	        i--;
    	} 
    	*/
}

void printArray(int A[]){ // 배열 출력 함수
    for(int i = 0; i < SIZE; i++)
        printf("[%d] ", A[i]);
    printf("\n\n");
}

void insertion_sort(int A[], int n){
    int key, i, j;
    for(int i = 1; i < n; i++){ // 기준점 잡기(1부터 시작)
        key = A[i]; // 기준값을 key에 대입
        for(j = i - 1; j >= 0 && A[j] > key; j--) // 왼쪽으로 이동하면서 비교
            A[j + 1] = A[j]; // 현재 인덱스 j의 값을 한 칸 오른쪽으로 이동
        A[j + 1] = key; // j < 0 이거나 A[j] < key일 때
    }
}

void main(){
    int list[SIZE]; // 배열 선언
    makeArray(list); // 난수로 배열 채우기
    printArray(list); // 정렬되기 전
    getchar();
    insertion_sort(list, SIZE);
    printArray(list); // 정렬된 후
}