기본 정렬2. 삽입 정렬(Insertion Sort)

1. 삽입 정렬(Insertion Sort)의 기본 개념

2. 삽입 정렬의 예시와 손 코드 구상

3. 삽입 정렬의 코드 구현

4. 삽입 정렬의 실제 활용

 

 

 

 

1. 삽입 정렬(Insertion Sort)의 기본 개념

 

삽입 정렬의 기본 원리를 3단계로 요약하면 다음과 같습니다. 

 

첫 번째. 삽입 정렬은 두 번째 인덱스부터 시작합니다. 

 

두 번째. 해당 인덱스(key 값) 앞에 있는 데이터부터 비교해서, key 값이 더 작으면 그 데이터 값을 뒤 인덱스로 복사한다

 

세 번째. 이를 key 값이 더 큰 데이터를 만날 때까지 반복하고 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

 

 

이를 시각화하여 표현하면 다음과 같다. 

(출처: commons.wikimedia.org/wiki/File:Insertion-sort-example.gif )

 

 

 

즉 n번째 인자를 그 이전의 인자와 비교를 하고 순서를 바꿈으로써 순서를 맞추는 것이 삽입 정렬의 기본 원리이자 핵심이다. 

 

2. 삽입 정렬의 예시와 손 코드 구상

 

(1) 예시를 통한 원리의 이해 

 

예를 들어서 [9, 3, 2, 5]의 리스트가 있다고 가정해봅시다. 

 

이때 삽입 정렬의 순서를 풀어서 설명하면 다음과 같습니다. 

 

1회 실행: key 값은 9 -> 인덱스(0)이므로 앞의 인자가 없음. 따라서 그대로 종료. [9, 3, 2, 5]

 

2회 실행: key 값은 3 -> 인덱스(1)이므로 앞의 인자 9와 비교를 진행 및 순서 교체. [3, 9, 2, 5]

 

3회 실행: key 값은 2 -> 인덱스(2)이므로 앞의 인자 3,9 와 비교를 진행 및 순서 교체. [2, 3, 9, 5]

 

4회 실행: key 값은 5 -> 인덱스(3)이므로 앞의 모든 인자와 비교를 지행 및 순서 교체. [2, 3, 5, 9]

 

모든 비교 및 정렬이 종료되었습니다. 이런식으로 key 값와 indexing을 기준으로 정렬하는 삽입 정렬의 원리를 예시로 한 번 알아 봤습니다. 

 

 

(2) 손 코드 구상

 

첫 번째. for stand in range(len(data_as_list)) 기본 반복 횟수 설정

 

두 번째. key 값의 설정 = data_as_list[stand]

 

세 번째. for num in range(start -> stand, stop -> 0, step -> -1) 왜냐하면 앞의 인자랑 계속 비교를 해야 하기 때문에

 -> 반복문 안에서 data_as_list[stand] < data_as_list[num - 1]이면 순서 바꾸기

 

 

 

 

3. 삽입 정렬의 코드 구현

 

 

위의 코드에서 원리는 간단하기에 별도의 주석을 달지 않았습니다. 손 코드를 잘 구성하면 위와 같이 깔끔하고 정리된 코드를 몇 번의 시도를 통해 만들 수 있는 장점이 있습니다. 

 

4. 삽입 정렬의 실제 활용

삽입 정렬의 실제 활용

 

0부터 100까지 20개의 난수를 random 패키지를 통해서 생성하였습니다. 기본 데이터 구조를 당연히 리스트 형태입니다. 

 

첫 번째 print 결과에서 보실 수 있듯 순서가 전혀 정렬 되지 않은 모습을 볼 수 있습니다. 그러나 insertion sort를 실행한 리스트 형태를 보면 오름차순으로 깔끔하게 정렬된 모습을 보실 수 있습니다. 

 

이로서 삽입 정렬에 대한 것을 기본 원리부터 실제 활용가지 모두 알아보았습니다.