[정렬 알고리즘 - 1] 삽입정렬(Insertion Sort), 선택정렬(Insertion Sort)

Insertion Sort(삽입 정렬)

---

먼저 알아볼 정렬 알고리즘은 삽입 정렬(Insertion Sort) 입니다! 말그대로 두 수를 비교해서 조건(크거나 작거나)에 맞으면 사이에 끼워 넣는(삽입)하는 알고리즘입니다. 그림으로 보면 바로 알 수 있어요!

그림에서 보면 기준점(노란색)을 정하고 앞으로 비교하면서 맞는 곳에 집어넣는 것을 알 수 있습니다. pseudo code로 보면 다음과 같습니다.

A배열이 1~n까지 있을 때 정렬
for i= 2 ~ n
	key = A[i]
	j = i-1
	while(j>0 && A[i] > key)
		A[j+1] = A[j]
	A[j+1] = key

매우 간단!!!! 코드를 보면 기준점 key를 잡고 그 전의 성분들을 비교해가면서 정렬을 해주는 알고리즘!! 코드도 매우 간단합니다!

int testcase[6] = {8, 2, 4, 9, 3, 6};
for(int i=1; i<6; i++)
{
    int cmp = testcase[i];
    int j;
    for(j=i-1; j>=0; j--)
    {
        if(testcase[j] > cmp) testcase[j+1] = testcase[j];
        else             break;
    }
    testcase[j+1] = cmp;
}

Selection Sort(선택 정렬)

---

선택정렬은 말그대로 옮길 위치를 선택해서 옮기는 알고리즘입니다. 이건 너무 간단해서 코드를 보면 바로 이해가 될거라고 생각합니다!

for(int i=0; i<6; i++)
{
    int locate = i;
    int cmp = testcase[i];
    for(int j=i+1;j<6;j++)
    {
        if(testcase[j] < cmp)
        {
            cmp = testcase[j];
            locate = j;
        }
    }
    int tmp = testcase[i];
    testcase[i] = testcase[locate];
    testcase[locate] = tmp;
}