버블정렬은 아이디어 자체는 매우 쉬운 알고리즘이다. 바로 옆에 있는 것과 비교해서 정렬하는 것이다. 아이디어가 쉬운 만큼 코드도 어렵지 않게 작성할 수 있지만, 효율성은 매우 낮다고 알려져 있어 앞으로 이런 코드를 쓸 일이 있을지는 잘 모르겠다. 그래도 알고리즘을 공부하는 입장에서 하나씩 접하면서 생각하는 습관이 필요할 것이다.
구현해보고자 하는 코드는 작은 값부터 큰 값까지 정렬하는 것으로, 우선 코드부터 살펴보면 다음과 같다.
# 옆에 있는 값과 비교해 더 작은 값을 앞으로 보내기
# 하지만, 효율성이 가장 낮은 알고리즘
def bubble_sort(array):
for i in range(len(array)):
for j in range(len(array)-i-1):
if (array[j] > array[j+1]):
temp = array[j]
array[j] =array[j+1]
array[j+1] = temp
print(array)
array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
bubble_sort(array)
선택정렬을 위한 알고리즘의 순서는 다음과 같다. 사실은 더 간단하게 나타낼 수도 있지만, 설명을 위해 비교적 길게 풀어쓴다.
1. 이전 비교 리스트에서 비교할 집단을 하나 줄여 선택한다. (첫번째 ~ 마지막 하나 전)
2. 비교할 집단 내에서 원소를 순차적으로 선택한다
3. 선택한 원소가 옆의 원소와 비교해 앞의 값이 큰 경우, 데이터를 교환한다
3. 2~3를 반복하다가, 비교 집단의 원소를 모두 선택한 경우 1로 돌아간다
여기서 헛갈릴 수 있는 부분이 몇 가지가 보이는데, 우선 첫번째부터 마지막까지 원소가 가는 것이 아닌 마지막 하나 전까지만 가야한다는 점이다. 왜냐하면, 내가 선택한 원소(j)와 그 바로 다음 원소(j+1)를 비교할 것이기 때문이다.
다른 하나는 비교해야할 집단을 하나씩 줄여준다는 점이다. 이는 비교집단의 모든 원소를 비교하면, 집단의 맨 마지막에 가장 큰 원소가 위치하게 된다. (이는 직접 해보는 것만큼 이해가 빠른 것은 없는 듯하다) 생각해보면 앞서 위에서 얘기한 것과 비슷한 원리라고 느껴지기도 하는데, 이건 사람마다 다르게 생각할 수 있어 따로 설명은 하지 않으려고 한다.
아무튼, 위 코드를 구현해보면 아래와 같이 잘 정렬하는 것을 볼 수 있다.
출처 및 참고:
- 안경잡이개발자, "3. 버블 정렬(Bubble Sort)", https://blog.naver.com/ndb796/221226803544
3. 버블 정렬(Bubble Sort)
지난 시간에는 가장 작은 값을 선택해서 앞으로 보내는 선택 정렬(Selection Sort) 알고리즘에 대해 알아...
blog.naver.com
'Python > CS' 카테고리의 다른 글
[알고리즘] 파이썬으로 병합정렬/합병정렬 (Merge Sort) 구현하기 (0) | 2021.10.10 |
---|---|
[알고리즘] 파이썬으로 퀵정렬(Quick Sort) 구현하기 (0) | 2021.09.19 |
[알고리즘] 파이썬으로 삽입 정렬(Insertion Sort) 구현하기 (0) | 2021.09.04 |
[알고리즘] 파이썬으로 선택정렬 (Selection Sort) 구현하기 (0) | 2021.08.29 |
주어진 값을 넣은 이중리스트(2d-array) 생성하기 (feat. list에서 append와 extend 차이) (0) | 2020.07.27 |