지난 포스팅에서 구현한 버블 정렬 코드로 데이터를 돌려본 결과, 일부 배열을 정렬할 때, 버블 정렬 Loop가 완전히 종료되지 않았음에도 이미 배열 정렬이 완료된 케이스에 대해 마지막에 소개를 잠깐 했었다.
버블 정렬을 위해 Loop를 도는 와중에 정렬이 완료되어버리면, 사실 그 이후에는 배열을 돌면서 비교를 하는 행위가 무의미해진다. 즉, 컴퓨터한테 쓸데없는 일을 시키는 것이다.
그럼, 어느정도 정렬이 된 배열을 조금 더 빠르게 수행하도록 만들 방법은 없을까? 이번 포스팅에서는 일반 버블 정렬의 개선 방안과 쉐이커 버블 정렬에 대해 알아보려 한다.
1. 일반 버블 정렬의 개선 방안
일반 버블 정렬의 코드를 보자.
잘 보면 while 조건문은 무조건 비교해야하는 배열의 크기가 2가 될 때까지 버블 정렬을 진행하도록 되어 있다. 그런데, 이 조건을 조금 변경해서, 모든 배열이 완전 정렬되었을 때 while문을 종료하는 방향으로 바꾸면 어떨까?
한 번 해보자. 우선 while 문 안에 있는 2를 제거한다고 하면, 저 위치에는 값을 비교한 뒤 마지막으로 자리를 교체한 Index가 오면 좋을 듯 하다. 이를 위해 코드를 아래와 같이 수정했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
def bubble_sort(arr: list, reverse=False) -> None:
arr_len = len(arr)
cmp_count = 0
# 마지막 변경 Index 저장을 위한 변수 추가
cursor = 0
# while arr_len >= 2:
while arr_len >= cursor:
for idx in range(arr_len - 1):
cmp_count += 1
if arr[idx] > arr[idx + 1]:
# 변경 시, cursor 업데이트
cursor = idx
arr[idx], arr[idx + 1] = arr[idx + 1], arr[idx]
arr_len -=1
print(f" * 비교 횟수: {cmp_count}")
return arr if not reverse else arr[-1::-1]
|
cs |
cursor라는 변수를 추가하고, 마지막 변경된 지점에 대한 index를 바라보게 한다. 그리고 while 조건문 내에서 순차 감소하는 arr_len이 최종적으로 업데이트 된 cursor까지만 비교를 진행하게 되므로, 버블 수행 횟수는 감소하게 된다.
개선된 코드를 적용하면, 12번 째 비교를 진행하는 순간에 배열 내 모든 원소가 오름차순으로 정렬되면서 함수가 마무리 됨을 확인할 수 있다.
2. Shaker 정렬
거의 정렬이 완료된 배열을 빠르게 정렬할 수 있는 또 다른 방법에 대해 알아보자.
지금까지 확인한 버블 정렬 코드들은 모두 배열의 오른쪽에서 왼쪽으로 단방향으로 비교를 수행했다. 그럼, 단방향으로 비교할 배열의 끝까지 도달했을 때, 바로 반대방향으로 비교를 수행하게 하면 조금 더 빠르지 않을까? 마치 위스키 만들 때 쉐이커를 흔드는 것처럼 말이다. 이러한 논리로 버블 정렬에서 파생된 정렬을 Shaker 정렬이라고 한다.
쉐이커 정렬도 한 번 구현해보자. 우선, 일반적인 버블 정렬과 달리, 양 끝 단에 비교를 중지할만한 마커가 있어야 한다. 그리고, 비교가 수행되면 마커를 이동하고, 두 마커가 동일한 값을 가지면 비교를 종료하면 될 것이다. 그리고 마커의 이동에 따라 배열 비교에 필요한 index의 증감도 결정해야하니, 이동방향을 알 만한 bool 변수도 하나 필요할 것이다.
완전히 빈 코드에서 작성을 시작해보자.
|
1
2
3
4
5
6
7
8
9
10
|
def bubble_sort(arr: list, reverse=False) -> None:
arr_len: int = len(arr)
low_limit: int = 0
high_limit: int = arr_len - 1
cursor: int = low_limit
is_moving_right: bool = True
return arr
|
cs |
low_limit과 high_limit은 비교할 배열의 한계를 설정하는 일종의 마커다. 그리고 cursor는 이 두 마커 사이를 오가며 배열 내 원소의 비교를 진행하는 키가 될 것이다. 마지막으로, cursor의 이동을 판별하는 is_moving_right이라는 bool 변수를 추가해주었다.
본격적으로 배열 내부를 흔들어보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
def bubble_sort(arr: list, reverse=False) -> None:
arr_len: int = len(arr)
low_limit: int = 0
high_limit: int = arr_len - 1
cursor: int = low_limit
is_moving_right: bool = True
while low_limit != high_limit:
if is_moving_right:
if cursor == high_limit - 1:
is_moving_right = not is_moving_right
cursor += 1
else:
if cursor == low_limit + 1:
is_moving_right = not is_moving_right
cursor -= 1
print(cursor)
return arr
|
cs |
위 코드를 실행하면 while 문을 빠져나오지 못하고 계속 cursor의 숫자만 출력할텐데, 이 숫자들은 현재 지정된 high_limit과 low_limit 사이 숫자다. 즉, 배열 내 index를 제대로 돌고 있다는 말이다. 그렇다면, 이 코드에서 원소 간 비교를 수행하는 코드를 넣고, cursor가 high_limit과 low_limit의 바로 옆에 도달하게 되면 high_limit과 low_limit의 증감과 동시에, cursor의 이동 방향을 변경해주면 Shaker 정렬 코드의 대략적인 윤곽이 잡힐 것이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
def bubble_sort(arr: list, reverse=False) -> None:
arr_len: int = len(arr)
low_limit: int = 0
high_limit: int = arr_len - 1
cursor: int = low_limit
is_moving_right: bool = True
while low_limit != high_limit:
print(low_limit, cursor, high_limit, is_moving_right)
if is_moving_right:
if cursor == high_limit - 1:
is_moving_right = not is_moving_right
high_limit -= 1
continue
cursor += 1
else:
if cursor == low_limit + 1:
is_moving_right = not is_moving_right
low_limit += 1
continue
cursor -= 1
return arr
|
cs |
위의 코드에서 print 문의 출력 결과는 아래와 같이 나타난다.
현재는 비교 연산이 없어 cursor가 지정되지 않아 최대 횟수인 15회의 비교를 진행하는 것을 알 수 있다. 이제 여기에 비교 연산 및 비교 연산이 일어난 Index에 cursor 지정을 진행하는 코드까지 완성해보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
def bubble_sort(arr: list, reverse=False) -> None:
arr_len: int = len(arr)
low_limit: int = 0
high_limit: int = arr_len - 1
cursor: int = low_limit
is_moving_right: bool = True
while low_limit != high_limit:
if is_moving_right:
if arr[cursor] > arr[cursor + 1]:
arr[cursor], arr[cursor + 1] = arr[cursor + 1], arr[cursor]
if cursor == high_limit - 1:
is_moving_right = not is_moving_right
high_limit -= 1
continue
cursor += 1
else:
if arr[cursor] < arr[cursor - 1]:
arr[cursor], arr[cursor - 1] = arr[cursor - 1], arr[cursor]
if cursor == low_limit + 1:
is_moving_right = not is_moving_right
low_limit += 1
continue
cursor -= 1
return arr
|
cs |
완성된 코드의 결과에 최대 비교 횟수를 출력하도록 코드를 추가해서 돌려보면 아래와 같이 나타난다.
주의해야 할 점이 있는데, 서두에 소개한 개선된 코드나 Shaker 정렬 모두, 배열 내 원소들이 어느정도 정렬되어 있는 상태에서나 수행 횟수가 감소하는 것이지, 모두 역순인 배열을 개선된 코드나 Shaker로 수행하는 경우 일반 버블 정렬과 수행 횟수가 동일하게 나타난다는 것이다.
마지막으로, 필자가 구현한 Shaker 코드도 너무 장황하니 조금 개선을 해보자(if문 맛집인듯) is_moving_right과 high_limit, low_limit 등 커서의 이동에 관여했던 변수들도 for 문 range()로 제어하고, 추가로 일반 버블 정렬의 개선사항에서 보았던 일종의 마커를 적용해보려한다. 참고로, index의 이동 방향을 for문에 맡겼기 때문에, While 문을 한 번 돌 때마다 high_limit과 low_limit 값이 동시에 증감을 진행하던지, cursor로 이 범위를 지정해주어야 한다. 따라서 whlie 조건문도 low_limit과 high_limit이 동일한 값이 되지 못하기 때문에 부등호 형태로 수정을 진행해야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
def bubble_sort(arr: list, reverse=False) -> None:
arr_len: int = len(arr)
low_limit: int = 0
high_limit: int = arr_len - 1
#cursor: int = low_limit
#is_moving_right: bool = True
while low_limit < high_limit:
print(low_limit, high_limit)
for idx in range(low_limit, high_limit):
pass
high_limit -= 1
print(low_limit, high_limit)
for idx in range(high_limit, low_limit, -1):
pass
low_limit += 1
return arr
|
cs |
cursor가 등록되지 않은 코드는 개선 전의 코드와 같이 low_limit과 high_limit을 왕복하는 코드다. 현재는 cursor가 없기 때문에 무한 루프에 빠지지 않도록 하기 위해 high_limit과 low_limit의 증감을 진행한다.
여기에 cursor 등록 및 원소 간 대소 비교를 진행하면 아래와 같이 코드가 완성된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
def bubble_sort(arr: list, reverse=False) -> None:
arr_len: int = len(arr)
low_limit: int = 0
high_limit: int = arr_len - 1
cursor = 0
while low_limit < high_limit:
for idx in range(low_limit, high_limit):
if arr[idx] > arr[idx + 1]:
cursor = idx
arr[idx], arr[idx + 1] = arr[idx + 1], arr[idx]
high_limit = cursor
for idx in range(high_limit, low_limit, -1):
if arr[idx] < arr[idx - 1]:
cursor = idx
arr[idx], arr[idx - 1] = arr[idx - 1], arr[idx]
low_limit = cursor
return arr
|
cs |
마찬가지로 비교 횟수와 함께 결과를 출력하면 아래와 같이 나타난다.
다음 포스팅에서는 필자가 코드 구현에 고생을 많이 했던 삽입 정렬에 대해 알아보려한다.
END.
'Python > Python Data Structure and Algorithm' 카테고리의 다른 글
| [자료구조 with Python] 11 - 정렬 알고리즘(4), 선택 정렬(Selection Sort) (0) | 2024.03.12 |
|---|---|
| [자료구조 with Python] 10 - 정렬 알고리즘(3), 삽입 정렬(Insertion Sort) (0) | 2024.03.11 |
| [자료구조 with Python] 8. 정렬 알고리즘(1) - 버블 정렬 개요 (0) | 2024.03.07 |
| [자료구조 with Python] 7. 선형 자료 구조 - 배열(6), Hash 충돌과 개방 주소법(Open Address) (0) | 2024.03.05 |
| [자료구조 with Python] 6. 선형 자료 구조 - 배열(5), Hash 충돌과 Chaining (0) | 2021.01.23 |
댓글