[SSAFYcial] 삽입 정렬에 대해 알아보자!

안녕하세요 열어분!

4월 자율 기사로 돌아왔습니다 ㅎㅎㅎ

 

요즘 2학기의 마지막 프로젝트인

6주간의 자율 프로젝트로 며칠 간 밤을 새고 있는데,,

피곤하네요 ㅋㅋ

 

이번 기사도 정렬에 대해 이야기 해볼까 합니다.

 

저는 전공 Java반에서 1학기 교육을 이수했는데요,

전공 반 수업에서는 학교에서 이 정도는 배우고 왔다고 가정해서 그런지

수업 때 따로 정렬에 대해선 다루지 않아서 따로 공부를 못했었는데

 

요즘 자료구조와 알고리즘 공부의 필요성을 느끼고 

LinkedList 및 정렬부터 기본기를 쌓고 있습니다. 

 

오늘은 여러 정렬 알고리즘 중 삽입 정렬에 대해 소개해보겠습니닷

 

 

삽입 정렬

삽입 정렬은 앞에 있는 모든 원소가 정렬이 되어 있다는 가정 하에서 현재 원소의 위치를 적절하게 집어넣는 정렬입니다.

 

예를 들어,

5, 4, 3, 2, 1 이 있다고 가정해보겠습니다.

 

i는 0번째 인덱스가 아닌 1번째 인덱스의 숫자인 4부터 출발합니다.

4에서 뒤를 봤을 때 5가 자신보다 크니 서로 바꿔준다.

 

4, 5, 3, 2, 1

 

(0~1 인덱스는 정렬되었어요)

 

이제 i는 2번째 인덱스인 3에서 출발해 뒤를 봅니다.

5는 3보다 크므로 3과 5의 위치를 바꾸고,

 

그 뒤에 있는 4도 3보다 크기 때문에 둘을 바꿔줍니다.

 

이때 바꾸는 swap 방식이 조금 특이한데요.

아마 백준에서 배열 돌리기를 풀어보셨다면 익숙하실텐데, 

당기기 방식을 사용하면 됩니다.

 

이게 무슨 뜻이냐면!

 

4, 5, 3, 2, 1

다시 여기서 출발해볼게요.

3을 맨 앞으로 보낼 겁니다.

현재 4, 5 까진 이미 정렬된 상태죠.

먼저 2번째 인덱스인 i의 값(여기선 3)을 따로 저장해두고,

 

바로 앞의 바꿔야 할 값인 5를 3의 자리로 당겨옵니다.

4, 5, 5 ,2, 1

 

이제 더 앞의 값인 4를 앞으로 당겨온 뒤에,

4, 4, 5, 2, 1

 

저장해둔 3의 값을 첫번째 자리에 넣습니다.

3, 4, 5, 2, 1

 

이것이 당기기 방식입니다.

 

이런 과정을 i가 3번째 인덱스인 2로 넘어가서 그대로 반복하게 됩니다.

 

그렇게 되면 결국,

 

2, 3, 4, 5, 1

 

1, 2, 3, 4, 5

 

요렇게 정렬됩니다.

 

 

삽입 정렬의 구현은 아래의 코드를 참고하시면 됩니다.

 

n개의 원소가 주어졌을 때, 삽입 정렬을 이용해 n개의 숫자를 오름차순으로 정렬하는 코드입니다.

 

삽입 정렬 코드 (Python)

n = int(input()) # 6
arr = list(map(int, input().split())) # [5, 3, 6, 7, 4, 2]

for i in range(1, len(arr)):
    j = i - 1
    tmp = arr[i]
    while j >= 0 and arr[j] > tmp:
        arr[j+1] = arr[j]
        j -= 1
    arr[j+1] = tmp

for s in arr:
    print(s, end=" ") # [2, 3, 4, 5, 6, 7]

 

 

여기까지 삽입 정렬에 대해 알아봤습니다!

삽입 정렬의 시간 복잡도는 O(N^2)이지만,

거의 정렬이 된 배열에서는 아주 효과적입니다.

또한 데이터 셋이 적을 때는 다른 복잡한 정렬 알고리즘보다 더욱 빠를 수도 있습니다.

 

다음에도 더 유익한 기사로 찾아올게요!

감사합니다 ㅎㅎ

 

 

참고 문헌

코드트리에서 공부한 내용을 바탕으로 작성하였습니다!