[Python][이코테] 삽입 정렬

삽입 정렬

삽입 정렬은 말 그대로 '삽입' 하여 정렬하는 것이다.

 

예를 들어 0~9까지 숫자를 오름차순 하고 싶은데 앞의 '선택 정렬'은 가장 작은 숫자를 '찾아서' 순서대로 맞춘다.

 

하지만 삽입 정렬은 일부러 찾는 것이 아닌 앞 인덱스와 비교하여 현재 인덱스 값 보다 앞 인덱스 값이 크면 '선택'하여 앞으로 보내는 것이다.

 

---

삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다.

 

삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.

 

선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break
print(array)

 

중요한 점이 삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.

 

7 5 9 0 3 1 6 2 4 8 일 때

 

1.

5는 7보다 작으므로 5와 7 교체

5 7 9 0 3 1 6 2 4 8

 

2.

9는 7보다 크니 유지

 

3. 

0은 9보다 작으므로 0과 9를 교체

5 7 0 9 3 1 6 2 4 8

 

이후 다시 0은 7보다 작으므로 교체 5 0 7 9 3 1 6 2 4 8

-> 0은 5보다 작으므로 교체 0 5 7 9 3 1 6 2 4 8

 

(반복)

 

이런 식으로 운영된다.

 

---

 

삽입 정렬의 시간복잡도는 코드로 보듯이 단순 생각하면 $O(N^2)$이다. 하지만 만약 처음부터 모든 값이 정렬되어 있다고 가정한다면 최선의 경우 O(N)의 시간 복잡도를 갖는다.

 

따라서 거의 정렬된 상태로 입력이 주어지는 문제는 다른 정렬 알고리즘보다 삽입 정렬 알고리즘이 효율이 좋다.

 

 

이것이 취업을 위한 코딩 테스트다 with 파이썬

IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. 최근 5년간의 코딩 테스트 기출문제를 분석하여 반드시 알아야 하는 알고리즘을 8가지로 정리하였다. 8가지 핵심 알고리즘 이론을 쉽게 설명하고, 관련 실전 문제를 풀이했다. 출제 유형 분석, 이론 설명, 기출문제 풀이까지! 어떤 코딩 테스트도 이 책 한 권으로 대비할 수 있을 것이다. 코딩 테스트에서 주로 선택하는 파이썬을 기반으로 설명되어 있으며, 파이썬 코드 외에도 C/C++, 자바 코드를 추가로 제공한다.

저자

나동빈

출판

한빛미디어

출판일

2020.08.05