1. 선택정렬
# 0번째 아이템이 가장 작다고 가정하고 시작한다.
# 만약 0번째 아이템보다 더 작은 아이템이 있다면 그중 가장 작은 놈과 0번째 아이템을 swap 한다.
arr = [20, 12, 10, 15, 2]
for i_step in range(len(arr)):
# 현재 이터레이션에서 가장 작은 값의 인덱스가 무엇인지 min_step에 기록한다.
# 앞으로 계속 갱신해 나간다.
min_step = i_step
for i in range(i_step+1, len(arr)):
if arr[i] < arr[min_step]:
min_step = i
else:
pass
arr[min_step], arr[i_step] = arr[i_step], arr[min_step]arr
>>> [2, 10, 12, 15, 20]내장함수 sorted()처럼 비파괴적 함수로 만들어보기
def my_sorted(arr) :
arr_dup = [i for i in arr]
for i_step in range(len(arr_dup)):
# 현재 이터레이션에서 가장 작은 값의 인덱스가 무엇인지 min_step에 기록한다.
# 앞으로 계속 갱신해 나간다.
min_step = i_step
for i in range(i_step+1, len(arr_dup)):
if arr_dup[i] < arr_dup[min_step]:
min_step = i
else:
pass
arr_dup[min_step], arr_dup[i_step] = arr_dup[i_step], arr_dup[min_step]
return arr_dupmy_sorted(arr)
>>> [2, 10, 12, 15, 20]
arr
>>> [20, 12, 10, 15, 2]
위 코드는 arr의 길이(len)가 길어질수록 효율성이 낮아질 위험이 있다.
따라서 반복문 속에 중첩을 최대한 제거해 주는 것이 좋다.
2. 삽입정렬
선택 정렬이 아닌 삽입정렬로 리스트를 정렬해보자.
arr = [9, 5, 1, 4, 3]
for step in range(1, len(arr)):
for i in range(step, 0, -1):
if arr[i-1] > arr[i]:
arr[i-1], arr[i] = arr[i], arr[i-1]
arr
>>> [1, 3, 4, 5, 9]삽입정렬은 누가 더 작은지 기록할 필요가 없기때문에
선택정렬과 비교해 보면 훨씬 더 간단하다.
위 알고리즘을 적용하여 비파괴적 함수로 만들어 보자.
arr = [9, 5, 1, 4, 3]
def my_sorted(arr):
arr_dup = [i for i in arr]
for step in range(1, len(arr_dup)):
for i in range(step, 0, -1):
if arr_dup[i-1] > arr_dup[i]:
arr_dup[i-1], arr_dup[i] = arr_dup[i], arr_dup[i-1]
return arr_dupmy_sorted(arr)
>>> [1, 3, 4, 5, 9]
arr
>>> [9, 5, 1, 4, 3]
삽입정렬 역시 선택정렬과 마찬가지로 arr의 길이가 커질수록 효율성이 낮아지고 시간의 복잡도가 늘어나는 단점이 있으므로 유의한다.
3. 버블정렬
앞뒤 원소를 비교해서 더 큰 값이 앞에 있으면 뒤로 보내준다.
arr의 길이만큼 이터레이션을 돌린다.
arr = [-2, 45, 0, 11, -9]
for i in range(len(arr)):
for k in range(len(arr)-i-1):
print(i, k)0 0
0 1
0 2
0 3
1 0
1 1
1 2
2 0
2 1
3 0
arr = [-2, 45, 0, 11, -9]
for i in range(len(arr)):
for k in range(len(arr)-i-1):
if arr[k] > arr[k+1]:
arr[k], arr[k+1] = arr[k+1], arr[k]
arr
>>> [-9, -2, 0, 11, 45]삽입정렬과 나름 비슷한 형태로, 역시 arr의 길이가 길어질수록 효율성이 낮아진다.
시각화해보기
for i in range(len(arr)):
for k in range(len(arr)-i-1):
if arr[k] > arr[k+1]:
print(i, k, 'swap!')
arr[k], arr[k+1] = arr[k+1], arr[k]
print(arr)
else:
print(i, k, 'pass!')
print(arr)모든 단계별로 i, k, 스왑여부, arr을 출력하여 과정을 시각화 해보았다.
0 0 pass!
[-2, 45, 0, 11, -9]
0 1 swap!
[-2, 0, 45, 11, -9]
0 2 swap!
[-2, 0, 11, 45, -9]
0 3 swap!
[-2, 0, 11, -9, 45] --> 45 확정
1 0 pass!
[-2, 0, 11, -9, 45]
1 1 pass!
[-2, 0, 11, -9, 45]
1 2 swap!
[-2, 0, -9, 11, 45] --> 11, 45 확정
2 0 pass!
[-2, 0, -9, 11, 45]
2 1 swap!
[-2, -9, 0, 11, 45] --> 0, 11, 45 확정
3 0 swap!
[-9, -2, 0, 11, 45]
'Code > algorithm' 카테고리의 다른 글
| 알고리즘 | BFS 활용하여 특정 도시 거리 계산 문제 풀기 (0) | 2024.04.01 |
|---|---|
| 알고리즘 | queue(FIFO) 속도이슈를 해결할 수 있는 deque (0) | 2024.04.01 |
| 알고리즘 | 탐색 기본 - Stack, Queue (0) | 2024.04.01 |
| 알고리즘 | 탐색 기본, 인접행렬과 인접리스트 (0) | 2024.04.01 |
| 알고리즘 | 탐색 기본, DFS / BFS (0) | 2024.04.01 |