정렬 알고리즘은 값들을 특정 조건에 따라 정렬하기 위해 사용되는 알고리즘이다. ex) 오름차순, 내림차순
대부분의 언어들에서는 원소들을 정렬하는 내장함수들이 존재하기 때문에 자연스럽게 그 함수들을 사용하지만,
당연히 이 과정은 자동으로 이루어지는 것이 아니라 내부적으로는 일련의 과정들을 거친다.
선택 정렬 알고리즘
선택 정렬 알고리즘은 수 많은 정렬 알고리즘 중 하나이다.
선택 정렬 알고리즘의 아이디어는 그림과 같이, 첫 번째 값부터 맨 마지막 값까지 쭉 돌면서 가장 작은 값들을 하나씩 배열의 맨 앞으로 가져오는 것이다.
파이썬을 통해 구현한 선택 정렬은 다음과 같다.
arr = [5, 10, 9, 33, 21, 7, 2, 3, 0] # 정렬되지 않은 array
for i in range(len(arr)):
min_index = i # 최솟값의 인덱스를 첫 값으로 임의지정해준다.
for j in range(i+1, len(arr)): # i의 다음 원소부터 끝까지 돌면서, i번째 값과 비교해준다.
if arr[min_index] > arr[j]: # i번째 값보다 작은 값이 등장하면
min_index = j # min_index의 값을 해당 값의 인덱스로 바꿔준다
# 도중에 min_index 값이 바뀌었더라도, 그 뒤의 값 중 더 작은 값이 존재할 수 있기 때문에 두 번째 for문을 끝까지 돌아줘야한다.
# 2번째 for문이 끝나면 i 번째 값과 min_index 번째 값을 스왑해준다.
arr[i], arr[min_index] = arr[min_index], arr[i]
print(arr)
물론, 두 번째 for문의 if 조건문의 조건을 반대로 주게되면 데이터들을 내림차순으로 정렬하는 것도 가능하다.
선택 정렬의 시간복잡도
선택 정렬은 진행과정 중 무슨 일이 일어나든 두 개의 반복문을 통해 모든 배열 값들을 돌아야한다.
첫 번째 반복문은 배열의 길이인 N만큼, 두 번째 반복문은 N-1부터 시작해서 N-2, N-3, ...., 2번까지 돌아야한다. (마지막 값은 비교해줄 필요 없으므로)
이 과정은 결국 O(n^2) 만큼의 시간복잡도를 필요로 한다.
삽입 정렬 알고리즘
삽입 정렬 알고리즘의 아이디어는 맨 앞(왼쪽) 값들이 정렬되어 있다는 가정하에, 특정 인덱스의 값들을 앞의 값들과 비교해가며 맞는 자리에 정렬시키는 것이다.
특정 인덱스의 값을 다음(오른쪽) 값이 아닌 이전(왼쪽) 값들과 비교한다는 점에서 선택 정렬과 차이를 보인다.
삽입 정렬을 파이썬으로 구현한 코드는 다음과 같다.
arr = [5, 10, 9, 33, 21, 7, 2, 3, 0] # 정렬되지 않은 array
for i in range(1, len(arr)): # 0번 인덱스는 이미 정렬되어 있다고 가정하기 때문에 1번 인덱스부터 시작
for j in range(i, 0, -1): #i번째부터 -1씩 내려감
if arr[j] < arr[j-1]: # 내려가는 도중에 자신보다 작은 값이 있으면 스왑
arr[j], arr[j-1] = arr[j-1], arr[j]
else: # 자신보다 작은 값이 없다면 그 앞의 모든 값들 또한 자신보다 작은 것이므로 두 번째 for문 돌 필요없음
break
print(arr)
삽입 정렬의 시간복잡도
값의 비교 대상이 이전 값들이 되고, 이전 값들과 비교하던 중 자신보다 작은 값이 나오면 곧바로 해당 반복문을 넘긴다는 측면에서 선택 정렬보다는 효율적이다.
특히, 값들이 이미 어느 정도 정렬되어 있는 상태에서 사용하는 삽입 정렬은 매우 효율적이기도 하다.
하지만, 최악의 경우 결국 배열의 모든 값 N개를 N-1, N-2, N-3, .... 2번씩 돌아야하므로 시간복잡도는 O(n^2)으로 표현한다.
'알고리즘 > 이론' 카테고리의 다른 글
| 투 포인터 알고리즘 (0) | 2021.02.01 |
|---|---|
| 소수판별 알고리즘 - 파이썬 (Python) (7) | 2021.01.31 |
| 퀵 정렬 알고리즘 with 파이썬 (Python) (0) | 2021.01.22 |
| 재귀함수 - 파이썬(Python) (0) | 2021.01.13 |
| 알고리즘과 알고리즘의 성능평가 (0) | 2021.01.07 |
