DataScience
[정렬] 단순 정렬 (버블, 선택, 삽입) 알고리즘 본문
정렬 : 이름, 암호, 회사 등의 키를 항목값의 정해진 기준에 따라 데이터 집합을 일정한 순서로 바꾸어 재설정하는 것을 말한다. 일반적으로 작은 데이터부터 시작하는 것을 오름차순(ascending) 정렬이라 하고, 큰 데이터부터 시작하는 것을 내림차순(descending) 정렬이라고 합니다. 정렬 알고리즘의 경우 아래 그림과 같이 여러가지 있으며 각기 다른 방법과 효율성을 보여준다.
단순 정렬 (버블, 선택, 삽입)
● 버블[Bublle] 정렬 : 두 인접한 데이터의 크기를 비교해 정렬 = 단순 교환 정렬
1. 버블 정렬의 특징
1. 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 느린편이다.
2. 인접한 데이터의 크기만을 비교하므로 간단하게 구현이 가능하다.
2. 버블 정렬 과정
1. 비교 연산이 필요한 패스 범위를 설정한다.
2. 인접한 데이터 값을 비교한다 (A[i] > A[i+1]과 같이 크기 비교)
3. swap 조건에 부합하면 swap 연산을 수행한다.
4. 패스 범위가 끝날때까지 2-3을 반복한다.
5. 정렬 영역[데이터의 끝 == 제일 큰 값]을 설정한다.
- 다음 패스를 실행할때 마지막 원소는 이미 끝에 있기때문에 n-1번이 된다.
6. 비교 대상이 없을 때까지 1~5를 반복한다.
3. 버블 정렬 구현
3.1.1(기본 정렬)
# (오름차순) 버블 정렬
data = [1,2,3,6,4,5]
n = len(data)
check_cnt += 1 # 비교 횟수
for i in range(n-1):
for j in range(n-i-1): # i : 패스를 돌때마다 -1을 해주며 마지막 비교의 경우 비교할 필요가 없기 때문에 -1
if data[j] >= data[j+1] :
data[j], data[j+1] = data[j+1], data[j]
print(data, check_cnt)
>>> [1, 2, 3, 5, 9, 13] 15# (내림차순) 버블 정렬
data = [1,5,3,2,13,9]
n = len(data)
for i in range(n-1):
for j in range(n-1, i, -1): # 끝에서부터 한칸식 확인 (끝, 시작, -1)
if data[j-1] < data[j] :
data[j-1], data[j] = data[j], data[j-1]
print(data)
>>> [13, 9, 5, 3, 2, 1]다음과 같은 방법으로 버블 정렬을 할경우 서로 이웃한 원소만 교환하므로 안정적으로 작동되는것을 볼수 있다. 하지만 원소를 비교하는 횟수가 2번으로 시간복잡도가 O(n^2)으로 다른 알고리즘보다 느린다고 볼수 있다.
3.1.2. (이미 정렬이 완료된 경우)
data = [1,2,3,6,4,5] # 1,2,3은 이미 정렬이 되어 잇고, 6,4,5만 정렬이 필요
n = len(data)
check_cnt = 0
for i in range(n-1):
cnt = 0 # 새로운 패스를 시작하기 전 0으로 초기화
for j in range(n-i-1):
if data[j] >= data[j+1] :
data[j], data[j+1] = data[j+1], data[j]
cnt += 1
check_cnt += 1
# cnt가 0인경우 1번도 교체를 하지 않은 경우
if cnt == 0:
break
print(data, check_cnt)중간에 더이상 비교를 하지 않은경우 break 문을 사용하여 함수를 종료 시켰으며, 비교 횟수를 비교해보면 15번에서 9번으로 줄어든것을 볼수 있다.
3.1.3. (앞의 패스 과정에서 정렬이 같이 된 경우)
data = [1,2,3,6,4,5]
check_cnt = 0
n = len(data)
a = 1
while a > 0:
first = 0
for i in range(n-a-1):
if data[i] >= data[i+1]:
data[i], data[i+1] = data[i+1], data[i]
first = i
check_cnt +=1
a = first
print(data, check_cnt)반복문을 사용하여 이미 정렬된 원소를 제외한 나머지만 비교하도록 범위를 제한하는 방법이다.
● 선택[Selection] 정렬 : 최소/최대 데이터를 조건에 맞게 선택하여 정렬
가장 작은 원소부터 선택해 제일 앞의 위치부터 한칸씩 옮기는 작업을 반복하며 정렬하는 알고리즘을 말한다.
1. 선택 정렬의 특징
1. 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 느린편이다.
2. 구현 방법이 복잡하면서 효율도 좋지 않기 때문에 사용하지 않는 편이다.
3. 서로 이웃하지 않는 떨어져 있는 원소끼리 교대하므로 안정적이지 않다.
4. 가장 작은 데이터를 찾는 문제에서 비슷한 형태를 사용한다.
2. 선택 정렬의 한계
1. 아직 정렬하지 않은 부분에서 최솟값이나 최대값을 찾는다
2. 찾은 값을 아직 정렬하지 않은 가장 앞에 있는 데이터와 swap 한다.
3. 1-2번 과정을 반복하면서 남은 정렬부분의 범위를 축소한다.
4. 더 이상 남은 정렬 부분이 없어질때까지 반복한다.
3. 선택 정렬 구현
data = [3,4,9,1,8,2]
n = len(data)
for i in range(n - 1):
min = i
for j in range(1 + i, n):
if data[j] < data[min]:
min = j
data[i], data[min] = data[min], data[i]
print(data)
>>> [1, 2, 3, 4, 8, 9]● 삽입[Insertion] 정렬 : 특정 데이터를 적절한 위치에 삽입하는 정렬
삽입 정렬은 특정 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다 가정하며, 적절한 위치를 탐색하는 부분에서 이진탐색 등의 탐색을 사용하면 시간 복잡도를 줄일수도 있다.
1. 삽입 정렬의 특징
1. 필요할 때만 위치를 바꾸므로 “데이터가 거의 정렬 되어 있을 때” 효율적이다.
2. 삽입 정렬 성능분석
- 배열이 이미 정렬된 경우 시간 복잡도가 O(n)
- 배열이 완전히 반대순서로 정렬되있는 경우 시간 복잡도가 O(n^2)
3. 처음 값은 key값이 되지 않는다. 적어도 하나는 비교해야 되기 때문이다.
4. 정렬된 원소는 항상 오름차순을 유지하고 있다.
2. 삽입 정렬의 한계
1. 현재 index에 있는 데이터 값을 key 값으로 지정한다.
2. key값이 정렬된 데이터 범위에 삽입될 위치를 탐색한다.
3. 삽입 위치부터 왼쪽 끝 위치까지 종료조건을 만족 할때까지 연산을 수행한다.
- 종료 조건 1 : key값이 정렬된 배열의 왼쪽 끝에 도달한 경우
- 종료 조건 2 : key값보다 작거나 같은 원소를 발견한 경우
4. 선택할 데이터가 없을 때까지 위의 과정을 반복한다.
3. 삽입 정렬 구현
3.1. while 사용
data = [3,4,5,23,13,2,42,1,10]
n = len(data)
for i in range(1, n):
key = data[i]
j = i
while j > 0 and data[j-1] > key:
data[j] = data[j-1]
j -= 1
data[j] = key
print(data)3.2. for 사용
data = [3,4,5,23,13,2,42,1,10]
n = len(data)
for i in range(1, n):
for j in range(i, 0, -1):
if data[j] < data[j-1]:
data[j], data[j-1] = data[j-1], data[j]
else :
break
print(data)
4. 삽입 정렬 모듈 (import bisect from insort)
bisect.insort(a, x, lo, hi) : a가 이미 정렬된 상태를 유지하면서 a[lo] ~ a[hi] 사이에 x를 삽입한다. 만약 a안에 x 값이 여러개인 경우 가장 오른쪽 위치에 삽입된다.
import bisect
data = [3,4,9,1,8,2]
n = len(data)
for i in range(1, n):
bisect.insort(data, data.pop(i), 0, i)
print(data)
>>> [1, 2, 3, 4, 8, 9]
참고서적
Do it! 알고리즘 코딩 테스트: 파이썬 편 (코딩 테스트를 처음 준비하는 취준생의 필독서!)
'Data science > algorithm' 카테고리의 다른 글
| [그래프] 그래프의 표현 (1) | 2022.10.23 |
|---|---|
| [정렬] 빠른 정렬 (병합, 퀵) 알고리즘 (0) | 2022.10.17 |
| [그래프 탐색] 깊이 우선 탐색[DFS]와 너비 우선 탐색[BFS] 알고리즘 (0) | 2022.10.16 |
| [자료구조] 스택(Stack)과 큐(Queue) (0) | 2022.10.10 |
| [자료구조] 배열(Array)과 리스트(List) (0) | 2022.10.09 |
