정렬
- 정렬이란 데이터를 순서대로 나열하는 방법을 의미한다.
버블 정렬
- 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, ... 이런 식으로 (마지막 -1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식이다.
- 작은 숫자, 큰 숫자 순서로 있으면 내버려두고 큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 바꾸면 된다.
설명하면 다음과 같다.
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6을 비교합니다!
4 < 6 이면 그대로 둡니다.
2단계 : [4, 6, 2, 9, 1]
6과 2를 비교합니다!
6 > 2 이므로 둘을 변경합니다!
[4, 2, 6, 9, 1] 이렇게요!
3단계 : [4, 2, 6, 9, 1]
6과 9를 비교합니다!
6 < 9 이면 그대로 둡니다.
4단계 : [4, 2, 6, 9, 1]
9와 1를 비교합니다!
9 > 1 이므로 둘을 변경합니다!
[4, 2, 6, 1, 9] 이렇게요!
자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 가장 큰 숫자인 9가 맨 뒤로 왔습니다.
큰 게 나오면 둘의 자리를 변경했으니 가장 맨 뒤에 갔다는 소리입니다!
그러면, 맨 뒷자리를 제외하고 다시 한 번 돌리면 됩니다!
5단계 : [4, 2, 6, 1, 9]
4와 2을 비교합니다!
4 > 2 이므로 둘을 변경합니다.
[2, 4, 6, 1, 9] 이렇게요!
6단계 : [2, 4, 6, 1, 9]
4와 6을 비교합니다!
4 < 6 이면 그대로 둡니다.
7단계 : [2, 4, 6, 1, 9]
6와 1을 비교합니다!
6 > 1 이므로 둘을 변경합니다!
[2, 4, 1, 6, 9] 이렇게요!
그러면 이제 두 번째로 큰 숫자인 6이 맨 뒤에서 두번쨰로 왔습니다!
여기까지만 비교하시면 됩니다. 6과 9을 비교할 필요는 없습니다.
다시 한 번 가볼게요!
8단계 : [2, 4, 1, 6, 9]
2와 4을 비교합니다!
2 < 4 이면 그대로 둡니다.
9단계 : [2, 4, 1, 6, 9]
4와 1을 비교합니다!
4 > 1 이므로 둘을 변경합니다!
[2, 1, 4, 6, 9] 이렇게요!
자, 이제 세 번쨰로 큰 숫자인 4가 맨 뒤에서 세번째로 왔습니다!
마지막 비교만 하면 됩니다!
10단계 : [2, 1, 4, 6, 9]
2와 1을 비교합니다!
2 > 1 이므로 둘을 변경합니다!
[1, 2, 4, 6, 9] 이렇게요!
버블정렬 구현
def bubblesort(lst):
# 최댓값을 구하는 알고리즘을 len(lst) - 1 만큼 반복한다.
iters = len(lst) - 1
for iter in range(iters):
# 이미 구한 최댓값은 범위에서 제외한다.
wall = iters - iter
for cur in range(wall):
if lst[cur] > lst[cur + 1]:
lst[cur], lst[cur + 1] = lst[cur + 1], lst[cur]
return lst
선택 정렬
- 선택해서 정렬한다
- 데이터 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬
설명하면 다음과 같다.
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6과 2와 9와 1을 차례차례 비교합니다.
그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다!
[1, 6, 2, 9, 4] 이렇게요!
자, 그러면 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다.
가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요!
그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다.
2단계 : [1, 6, 2, 9, 4]
6과 2와 9와 4를 차례차례 비교합니다.
그 중 가장 작은 2와 두번째 앞 자리인 6을 교체합니다!
[1, 2, 6, 9, 4] 이렇게요!
3단계 : [1, 2, 6, 9, 4]
6과 9와 4를 차례차례 비교합니다.
그 중 가장 작은 4와 세번째 앞 자리인 6을 교체합니다!
[1, 2, 4, 9, 6] 이렇게요!
4단계 : [1, 2, 4, 9, 6]
9와 6을 비교합니다!
그 중 가장 작은 6과 네번째 앞 자리인 9을 교체합니다!
[1, 2, 4, 6, 9] 이렇게요!
버블 정렬보다 훨씬 더 적은 비교를 하는 것 같지만,
실제로는 각 배열을 계속해서 탐색하는 방식이라 2중 반복문을 사용해야 합니다!
선택정렬 구현
def selectionsort(lst):
iters = len(lst) - 1
for iter in range(iters):
minimun = iter
for cur in range(iter + 1, len(lst)):
if lst[cur] < lst[minimun]:
minimun = cur
if minimun != iter:
lst[minimun], lst[iter] = lst[iter], lst[minimun]
return lst
삽입 정렬
- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
설명하면 다음과 같다.
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4는 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 6을 받습니다.
4, 6 이 되는데 4 < 6 이므로 그대로 냅둡니다.
[4, 6, 2, 9, 1] 이렇게요!
자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 새로운 부대원인 4, 6은 현재 정렬된 상태입니다!
이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다.
끝까지 한 번 반복해볼게요!
2단계 : [4, 6, 2, 9, 1]
4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 2를 받습니다.
4, 6, 2 가 되는데 6 > 2 이므로 둘을 변경합니다!
4, 2, 6 가 되는데 4 > 2 이므로 둘을 변경합니다!
[2, 4, 6, 9, 1] 이렇게요!
3단계 : [2, 4, 6, 9, 1]
2, 4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 9를 받습니다.
2, 4, 6, 9 가 되는데 6 < 9 이므로 그대로 냅둡니다.
[2, 4, 6, 9, 1] 이렇게요!
4단계 : [2, 4, 6, 9, 1]
2, 4, 6, 9 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 1을 받습니다.
2, 4, 6, 9, 1 가 되는데 9 > 1 이므로 둘을 변경합니다!
2, 4, 6, 1, 9 가 되는데 6 > 1 이므로 둘을 변경합니다!
2, 4, 1, 6, 9 가 되는데 4 > 1 이므로 둘을 변경합니다!
2, 1, 4, 6, 9 가 되는데 2 > 1 이므로 둘을 변경합니다!
[1, 2, 4, 6, 9] 이렇게요!
삽입정렬 구현
def insertionsort(lst):
# 0번째 요소는 이미 정렬되어있으니, 1번째 ~ lst(len)-1 번째를 정렬하면 된다.
for cur in range(1, len(lst)):
# 비교지점이 cur-1 ~ 0(=cur-cur)까지 내려간다.
for delta in range(1, cur + 1):
cmp = cur - delta
if lst[cmp] > lst[cmp + 1]:
lst[cmp], lst[cmp + 1] = lst[cmp + 1], lst[cmp]
else:
break
return lst
def insertionsort_2(lst):
for idx in range(1, len(lst)):
val = lst[idx]
cmp = idx - 1
while lst[cmp] > val and cmp >= 0:
lst[cmp + 1] = lst[cmp]
cmp -= 1
lst[cmp + 1] = val
return lst
'알고리즘 > 파이썬' 카테고리의 다른 글
[파이썬 알고리즘] Mergesort 기초. (0) | 2022.05.27 |
---|---|
[파이썬 알고리즘] Quicksort(퀵정렬) 기초. (0) | 2022.05.27 |
[파이썬 알고리즘] 1337. leetcode- The K Weakest Rows in a Matrix (0) | 2022.05.25 |
[파이썬 알고리즘]1464.leetcode - Maximum Product of Two Elements in an Array (0) | 2022.05.25 |
[파이썬 알고리즘]215.leetcode - 배열의 k번째 큰 요소 (0) | 2022.05.25 |