삽입정렬(Insertion Sort) 구현

 

삽입정렬(Insertion Sort)

- 제자리 정렬 알고리즘의 하나이다.

- 카드를 순서대로 정리할때와 같은 방법이다.

- 선택정렬과 유사하지만 좀 더 효율적인 정렬이다. (시간복잡도는 O(n^2)로 동일하다.)

 

 

 

원리(오름차순 기준)

  1. 첫 번째 원소는 앞의 원소가 더 이상 존재하지 않으므로, 두 번째 원소를 기준 원소로 잡고 시작한다.

  2. 기준으로 잡은 원소의 앞(왼쪽)을 차례로 비교하면서 위치를 바꿔준다.

    ※ 즉, 두 번째 원소는 첫 번째 원소와 비교, 세 번째 원소는 두 번째, 첫 번째 원소와 비교하는 식이다.

 

 

 

코드

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 10

void SetArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        arr[i] = rand() % 100;
    }
}

void PrintArr(int arr[])
{
    for (int i = 0; i < MAX; i++)
    {
        printf("%d\n", arr[i]);
    }
}

void InsertionSortAscending(int arr[])
{
    for (int i = 1; i < MAX; i++)
    {
        int j = i - 1;
        int current = arr[i];
		
        while (j >= 0 && arr[j] > current)
        {
            arr[j + 1] = arr[j];
            j--;
        }
		
        arr[j + 1] = current;
    }
}

void InsertionSortDescending(int arr[])
{
    for (int i = 1; i < MAX; i++)
    {
        int j = i - 1;
        int current = arr[i];
		
        while (j >= 0 && arr[j] < current)
        {
            arr[j + 1] = arr[j];
            j--;
        }
		
        arr[j + 1] = current;
    }
}

void main()
{
    srand(time(NULL));
    int iArr[MAX] = { 0 };
	
    SetArr(iArr);
	
    InsertionSortAscending(iArr);
    //PrintArr(iArr);
	
    InsertionSortDescending(iArr);
    //PrintArr(iArr);
}