일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- docker
- 백준 온라인 저지
- 백준온라인저지
- leetcode
- 데이터 엔지니어
- SQL
- 빅데이터를 지탱하는 기술
- Pseudo Lab
- airflow architecture
- terraform
- Data Engineering
- Dynamic Programming
- 그리디
- Spark
- hackerrank
- data_engineer
- 2023년 목표
- docker image
- Airflow
- docker container
- MySQL
- Python
- dsf
- airflow webserver
- datacamp
- 알고리즘
- BOT
- delete join
- telegram
- 프로그래머스
Archives
- Today
- Total
Lim Seunghyun Space
[알고리즘] 삽입 정렬 본문
1. 삽입 정렬 의미
2. 삽입 정렬 개념
3. 삽입 정렬 예시
4. 삽입 정렬 구현 (With Python3)
삽입 정렬 의미
- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
삽입 정렬 개념
- 삽입 정렬은 정렬하고자 하는 리스트의 크기가 n이라면 n-1번 반복하여 key 값을 기준으로 삽입할 위치를 찾아 반복하는 알고리즘
- 삽입 정렬의 첫 번째 시작은 두 번째 값이 key가 되어 첫 번째 값과 비교하여 첫 번째 값보다 작은 경우 첫 번째 값은 뒤로 밀리고 key가 첫 번째로 이동한다.
- 두 번째 바퀴에서는 세 번째 값이 key가 되고 두 번째 값과 비교하여 작은 경우 서로 위치를 교환한다. 이때 key는 두 번째 값이 되고 이제 key는 첫 번째 값과 비교해서 작은 경우 서로 위치를 교환한다.
- 위의 케이스를 계속 반복하여 오름차순으로 정렬을 실행한다.
삽입 정렬 예제
- 삽입 정렬을 이용하여 [5,4,2,1,3]을 오름차순으로 정렬시
- 첫 번째 바퀴에서는 두 번째 값인 4가 key가 되어 첫번째 값인 5와 비교해서 값이 더 작으므로 서로의 위치를 교환한다.
- 두 번째 바퀴에서는 세 번째 값인 2가 key가 되어 두번째 값인 5와 비교해서 값이 더 작으므로 서로의 위치를 교환한다. 이후 key는 첫번째 값인 4와 비교해서 값이 더 작으므로 서로의 위치를 교환한다.
- 세 번째 바퀴에서는 네 번째 값인 1이 key가 되어 세번째 값인 5와 비교해서 값이 더 작으므로 서로의 위치를 교환한다. 그 다음 key는 두번째 값인 4와 비교하여 값이 더 작으므로 서로의 위치를 교환한다. 마지막으로 key는 첫번째 값인 2와 비교해서 값이 더 작으므로 서로의 위치를 교환한다.
- 네 번째 바퀴에서는 다섯번째 값인 3이 키가 되어 네번째 값인 5와 비교해서 값이 더 작으므로 서로의 위치를 교환한다. 그다음 key는 세번째 값인 4와 비교해서 값이 더 작으므로 서로의 위치를 교환한다. 그 다음 key는 두 번째 값인 2와 비교했을 때 값이 더 크므로 그 상태를 유지하면서 정렬이 종료된다.
삽입 정렬 구현 (With Python3)
def insertionSort(x):
for i in range(1, len(x)):
key = x[i]
j = i - 1 # 이전 인덱스 값
while x[j] > key and j >= 0: # 이전 인덱스 값이 key보다 작고 인덱스가 리스트의 범위를 벗어나지 않을 경우
x[j+1] = x[j]
j -= 1
x[j+1] = key
return x
if __name__ == "__main__":
x = [5,4,2,1,3]
insertionSort(x)
삽입 정렬 특징
- 시간 복잡도
- 반복을 두번 실행하므로 $$ O(n^2) $$
- 이미 정렬이 된 상태라면 $$ O(n) $$
728x90
'Algorithm > 이론' 카테고리의 다른 글
[알고리즘] 선택 정렬 (0) | 2021.12.24 |
---|---|
[알고리즘] 버블 정렬 (0) | 2021.12.24 |