삽입 정렬(Insertion Sort) 알고리듬
정의
정렬 안 된 부분 가장 왼쪽 원소를 정렬 된 부분에 ‘삽입’하는 정렬 알고리듬
- 정렬 후 정렬 된 부분 원소 수 1 증가
- 정렬 후 정렬 안 된 부분 원소 수 1 감소
메커니즘
정렬 안 된 부분 가장 왼쪽 원소. 정렬된 부분 원소와 비교한 뒤. 자기 자리 찾아 삽입.
- 정렬 안 된 부분 가장 왼쪽 원소에 대해. (비교 - 이동 - 삽입) 반복.
- 정렬 안 된 부분 원소 다 사라질 때 까지 반복
알고리듬 적용 예
삽입 정렬 성능
삽입 정렬 성능은 입력에 민감하게 반응한다(Input Sensitive)
입력: 이미 정렬된 배열
- 최선 경우
- 수행: 비교연산만 $N-1$ 번 수행
$\Rightarrow O(N)$ 시간복잡도
입력: 역으로 정렬된 배열
- 최악 경우
- 수행: 비교, 이동, 삽입
- 이동횟수 $= 1+2+…+(N-2)+(N-1) = \frac{N(N-1)}{2}$
$\Rightarrow O(N^{2})$ 시간복잡도
입력: 랜덤으로 배열된 데이터들
- 평균 경우
- 수행: 비교, 이동, 삽입
- 이동횟수 $= \frac{1}{2} \times \frac{N(N-1)}{2} = \frac{N(N-1)}{4}$
$\Rightarrow O(N^{2})$ 시간복잡도
$\Rightarrow$ 삽입 정렬은 일반적으로 $O(N^{2})$ 시간복잡도가 걸리고, 최선 경우에만 $O(N)$ 시간복잡도 걸린다.
- 효율성 떨어지는 정렬 알고리듬이다.
삽입 정렬 특징
아래 경우 삽입 정렬은 효율적이다.
- 이미 정렬된 배열에 소량의 데이터만 추가해서 다시 정렬할 때
- 애초에 입력 크기가 작을 때
높은 알고리듬 단순성, but 입력 크기 클 수록 비효율적
- 알고리듬 자체도 단순하고, 재귀호출도 사용 안 한다.
- 입력 크기 클 수록 많은 이동 발생한다. 따라서 비효율적이다.
합병 정렬, 퀵 정렬 성능 향상에 도움 준다.
- 합병, 퀵 정렬 알고리듬과 함께 사용되어서, 두 알고리듬의 실질적 성능 향상에 기여한다.
- 단, 이론적 성능보다 실제 성능이 더 잘 나오는 거다. 이론적 성능은 향상되지 않는다.
정렬 알고리듬 안정성이 보장된다.
- 정렬 후. 키 값 같은 원소들 사이 상대적 위치가 유지된다.
삽입 정렬 알고리듬 구현
삽입 정렬 알고리듬 정의
1
2
3
4
5
6
7
8
9
10
11
12
13
# 삽입정렬 알고리듬 정의
def insertion_sort(A) :
n = len(A)
for i in range(1, n) :
key = A[i] # 정렬 안 된 부분 가장 왼쪽 원소
j = i-1
# 비교 - 이동 조건 만족하는 한 반복
while j >= 0 and A[j] > key : # 비교
A[j+1] = A[j]
j = j-1
A[j+1] = key # 삽입
printStep(A, i)
정렬 결과 출력 정의
1
2
3
4
5
# i번째 루프. 정렬 결과 출력 정의
def printStep(arr, loop) :
print(f'{loop}번째 루프. 정렬 결과:', end=' ')
print(arr)
알고리듬 테스트
1
2
3
4
5
6
7
# 알고리듬 테스트
data = [5,3,8,4,9,1,6,2,7] # 정렬 전
print('정렬 전:', data)
insertion_sort(data)
print('삽입 정렬 종료 결과:', data)
정렬 전: [5, 3, 8, 4, 9, 1, 6, 2, 7]
1번째 루프. 정렬 결과: [3, 5, 8, 4, 9, 1, 6, 2, 7]
2번째 루프. 정렬 결과: [3, 5, 8, 4, 9, 1, 6, 2, 7]
3번째 루프. 정렬 결과: [3, 4, 5, 8, 9, 1, 6, 2, 7]
4번째 루프. 정렬 결과: [3, 4, 5, 8, 9, 1, 6, 2, 7]
5번째 루프. 정렬 결과: [1, 3, 4, 5, 8, 9, 6, 2, 7]
6번째 루프. 정렬 결과: [1, 3, 4, 5, 6, 8, 9, 2, 7]
7번째 루프. 정렬 결과: [1, 2, 3, 4, 5, 6, 8, 9, 7]
8번째 루프. 정렬 결과: [1, 2, 3, 4, 5, 6, 7, 8, 9]
삽입 정렬 종료 결과: [1, 2, 3, 4, 5, 6, 7, 8, 9]
버블 정렬(Bubble Sort) 알고리듬
정의
인접한 2개 원소 비교해서. 순서대로 되어있지 않으면 서로 교환하는 정렬 알고리듬.
- 비교 & 교환 과정을 리스트 왼쪽 끝에서 오른쪽 끝 까지 반복
- 리스트 전체가 정렬 될 때 까지 정렬 루프 반복한다.
- 루프 1회 끝날 때 마다. 최댓값 원소가 리스트 오른쪽 끝에 배치되고. 비교 대상에서 제외된다.
- 루프 최대 횟수는 $n-1$
버블 정렬 예시
버블 정렬 성능
비교횟수
항상 $\frac{n(n-1)}{2}$.
따라서 비교연산 시간복잡도도 항상 $O(n^{2})$
이동횟수
- 최악 경우(입력이 역순으로 정렬된 경우): 3 $\times$ 비교횟수 $\Rightarrow O(n^{2})$
- 최선 경우(입력이 이미 정렬된 경우): 이동 없다. 비교연산만 한다.
- 평균 경우: $O(n^{2})$
$\Rightarrow$ 버블정렬은 일반적 경우. 비교, 이동 모두 각각 $O(n^{2})$ 시간복잡도 걸린다.
비효율적이다.
버블 정렬 특징
- 알고리듬 단순하다. 구현도 쉽다.
- 최악 경우(가장 큰 값이 왼쪽 끝에 있을 때), 원소가 왼쪽 끝에서 오른쪽 끝으로 이동하기 위해 모든 원소와 교환 일어나야 한다.
- 특정 요소가 이미 최종 정렬 위치에 놓여 있더라도 교환 발생한다.
단순한 알고리듬에도 불구하고, 거의 사용하지 않는다.
버블 정렬 구현
버블 정렬 정의
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 버블 정렬 알고리듬 정의
def bubble_sort(A) :
n = len(A) # 정렬 안 된거 개수
# 버블정렬 반복 루프(최대 n-1 번 반복)
for i in range(n-1, 0, -1) :
change_happened = False
for j in range(i) :
if A[j] > A[j+1] : # 비교
A[j], A[j+1] = A[j+1], A[j] # 교환
change_happened = True
if not change_happened :
break # 버블정렬 루프에서 유의미한 정렬 발생 안 했으면 루프 종료 (이미 정렬 완료됨)
printStep(A, n-i) # 이번 루프 정렬 결과 출력
루프 정렬 결과 출력 정의
1
2
3
4
5
# 루프 정렬 결과 출력 정의
def printStep(arr, loop) :
print(f'{loop}번째 루프:', end='')
print(arr)
알고리듬 테스트 -1
1
2
3
4
5
6
7
# 알고리듬 테스트 #1
data = [5,3,8,1,2,7]
print('정렬 전:', data)
bubble_sort(data)
print('정렬 후:', data)
정렬 전: [5, 3, 8, 1, 2, 7]
1번째 루프:[3, 5, 1, 2, 7, 8]
2번째 루프:[3, 1, 2, 5, 7, 8]
3번째 루프:[1, 2, 3, 5, 7, 8]
정렬 후: [1, 2, 3, 5, 7, 8]
알고리듬 테스트 -2
1
2
3
4
5
6
7
# 알고리듬 테스트 # 2
data = [5,3,8,4,9,1,6,2,7]
print('정렬 전:', data)
bubble_sort(data)
print('정렬 후:', data)
정렬 전: [5, 3, 8, 4, 9, 1, 6, 2, 7]
1번째 루프:[3, 5, 4, 8, 1, 6, 2, 7, 9]
2번째 루프:[3, 4, 5, 1, 6, 2, 7, 8, 9]
3번째 루프:[3, 4, 1, 5, 2, 6, 7, 8, 9]
4번째 루프:[3, 1, 4, 2, 5, 6, 7, 8, 9]
5번째 루프:[1, 3, 2, 4, 5, 6, 7, 8, 9]
6번째 루프:[1, 2, 3, 4, 5, 6, 7, 8, 9]
정렬 후: [1, 2, 3, 4, 5, 6, 7, 8, 9]
쉘 정렬(Shell Sort) 알고리듬
정의
효율 높인 삽입 정렬.
메커니즘
- h만큼 간격 떨어진 원소들 모아 여러 개 부분 리스트 만든다.
- 각 부분리스트 내에서 삽입정렬 수행
- 부분리스트 합친다.
- 1~3 과정을 h 줄여가며 반복한다. h가 1일때가 마지막이다.
- 일반적으로 각 루프마다 h를 절반씩 줄인다. h를 줄일 때 마다 각 부분리스트 원소 수는 증가한다.
예시
쉘 정렬 성능
초기 간격(h) 어떻게 설정하느냐에 성능 영향 받는다.
- 초기 간격 크다: h가 작아질 수록 성능 올라간다.
- 초기 간격 작다: 쉘 정렬이 삽입정렬보다 나은 이점 제대로 활용 못한다. 성능 낮다.
평균 경우 시간 복잡도: $O(N^{1.5})$
최악 경우 시간 복잡도: $O(N^{2})$
- 예컨대 역으로 정렬된 배열에 h = 1 에서 쉘 정렬 적용한다고 가정하자. 이는 삽입 정렬 최악 경우와 같다. 이때 시간복잡도는 $O(N^{2})$ 걸린다.
일반적으로 입력 크기가 그리 크지 않을 때. 쉘 정렬 높은 성능 보인다.
- 전체 입력 크기가 크지 않다면. 여러 개 부분 리스트로 나누었을 때. 삽입 정렬 속도가 더 빨라질 것이다.
쉘 정렬 특징
자료와 자료가 원거리 이동하면서, 전체 이동 횟수는 단순히 삽입 정렬 적용했을 때 보다 줄어들 수 있다.
각 부분 리스트는 다소 정렬된 상태다.
h가 감소할 수록. 각 부분 리스트는 점차 정렬된 상태가 되어간다. 따라서 h가 감소할 수록 부분 리스트 내 삽입 정렬 속도도 빨라진다.
알고리듬이 단순하다.
임베디드 시스템에 주로 사용된다. (효율적)
쉘 정렬 구현
쉘 정렬 정의
1
2
3
4
5
6
7
8
9
10
11
12
13
# 쉘 정렬 정의
def shell_sort(A):
h = 3 # 간격
while h >= 1 :
for i in range(h, len(A)) : # 부분리스트 정렬
j = i # 부분리스트에서 정렬 안 된 부분 가장 왼쪽 원소
while (j-h >= 0) and (A[j]<A[j-h]) : # 비교-이동-삽입 반복
# j 앞에 어떤 값 있고 and 그 값이 오름차순 만족 안 하면
A[j], A[j-h] = A[j-h], A[j]
j = j-h
printStep(A,h) # h에서 정렬 결과 출력
h = h//2 # 간격 조정
쉘 정렬 결과 출력 정의
1
2
3
4
# 결과 출력 정의
def printStep(arr, h):
print(f'간격 {h} 일 때 쉘 정렬 결과: {arr}')
쉘 정렬 알고리듬 테스트
1
2
3
4
5
6
7
# 알고리듬 테스트
data = [5,3,8,4,9,1,6,2,7]
print(f'쉘 정렬 전: {data}')
shell_sort(data)
print(f'쉘 정렬 후: {data}')
쉘 정렬 전: [5, 3, 8, 4, 9, 1, 6, 2, 7]
간격 3 일 때 쉘 정렬 결과: [4, 2, 1, 5, 3, 7, 6, 9, 8]
간격 1 일 때 쉘 정렬 결과: [1, 2, 3, 4, 5, 6, 7, 8, 9]
쉘 정렬 후: [1, 2, 3, 4, 5, 6, 7, 8, 9]