목차
1. 이전 포스팅(선택정렬) 및 삽입 정렬 알고리즘이란?
우선 이전 포스팅에서는 선택정렬에 대해 알아보았습니다. 또한 예제가 있기때문에 삽입 정렬을 알아보기전에 선택정렬을 먼저 알아보는 것도 좋을 것 같습니다.
2023.08.07 - [Python] - [정보처리기사/Python] 선택 정렬 알고리즘과 활용 예제
[정보처리기사/Python] 선택 정렬 알고리즘과 활용 예제
목차 선택 정렬 알고리즘이란? 선택 정렬 동작 원리 선택 정렬의 장단점 선택 정렬 예제 코드 배열 정렬 예제 최솟값 찾기 예제 문자열 정렬 예제 1. 선택 정렬 알고리즘이란? 선택 정렬 알고리즘
salguworld.tistory.com
삽입 정렬 알고리즘은 각 요소를 이미 정렬된 부분과 비교하여 적절한 위치에 삽입하는 방식으로 정렬하는 알고리즘입니다. 작은 부분에서부터 정렬을 수행하며, 안정적인 정렬 방식입니다.
2. 삽입 정렬 동작 원리
삽입 정렬의 동작 원리는 다음과 같습니다:
- 첫 번째 요소는 이미 정렬되었다고 가정합니다.
- 두 번째 요소부터 시작하여 이미 정렬된 부분과 비교하며 적절한 위치에 삽입합니다.
- 이미 정렬된 부분은 오름차순이나 내림차순으로 유지됩니다.
- 모든 요소가 정렬될 때까지 위 과정을 반복합니다.
3. 삽입 정렬의 장단점
장점:
- 안정적인 정렬 방식입니다.
- 데이터가 거의 정렬된 경우 효율적으로 작동합니다.
단점:
- 최악의 경우 시간 복잡도가 O(n^2)으로 비효율적입니다.
- 데이터 양이 많을 경우 다른 정렬 알고리즘에 비해 느릴 수 있습니다.
4. 삽입 정렬 예제 코드
다음은 파이썬에서의 삽입 정렬 예제 코드입니다.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
5. 배열 정렬 예제
배열을 삽입 정렬로 정렬하는 예제입니다.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
array = [5, 2, 9, 1, 5, 6]
insertion_sort(array)
print("정렬된 배열:", array)
6. 문자열 정렬 예제
문자열을 삽입 정렬로 정렬하는 예제입니다.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
strings = ["apple", "banana", "grape", "pineapple", "orange"]
insertion_sort(strings)
print("정렬된 문자열:", strings)
반응형