-
[알고리즘/Algorithm] 파이썬으로 버블 정렬(Bubble Sort) 알아보기Algorithm/Sort 2021. 7. 1. 22:37
Bubble Sort (버블 정렬)
: 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
버블 정렬 흐름
버블 정렬은 위 그림과 같이 리스트에서 한 칸씩 전진해가며 바로 앞에 있는 값과 비교해서 크면 스왑하고 아니면 지나간다.
그렇기 때문에 만약 리스트의 첫 번째 공간에있는 데이터가 리스트내에 제일 큰 값이라면 계속 그 값을 스왑해가면서 한 번의 루프에
그 값이 제일 마지막으로 이동해 있을 것이다.
만약 위 그림에서 리스트의 첫번째 공간의 데이터 5가 만약 11이었다고 한다면 첫 번째 루프에 11이 뒤에 있는 모든 값과 비교하면서
스왑해서 제일 마지막 공간에 위치하게 됐을 것이다.
아이디어 1. : 그렇다면 루프가 한 번씩 지날 때마다 비교하는 횟수를 한 번씩 줄여도 된다는 얘기가 된다.
아이디어 2. : 또 루프의 위치가 마지막 값에 도달했을 때는 뒤에 비교할 값도 있지 않고 이미 정렬된 상태일 것이다.
그렇다면 루프의 반복 횟수는 리스트의 데이터의 갯수 -1 만큼 반복하면 된다.
이 아이디어를 바탕으로 알고리즘을 작성해보면 아래와 같다.
def bubble_sort(data): for i in range(len(data) - 1): swap = False for j in range(len(data) - i - 1): if data[j] > data[j+1]: data[j+1], data[j] = data[j], data[j+1] swap = True # 안쪽 for 문을 한 바퀴 돌면서 바뀐게 없으면 이미 정렬된 것이므로 탈출 if not swap: break
위 아이디어 1 바탕으로 바깥의 루프인 for문은 len(data) - 1 만큼 반복해줬고,
아이디어 2를 바탕으로 안쪽 for문은 len(data) - i - 1 만큼 반복해줬다.
추가로 이미 정렬된 상태인데 for문을 통해 데이터를 순회하면서 리소스를 낭비하는 것을 방지하기 위해
swap이라는 변수로 데이터의 변경 여부를 파악하여 안쪽 루프를 돌면서 데이터의 순서가 변경되지 않았다면
바깥 for문을 탈출할 수 있게 했다.
시간 복잡도
- 최악 : 이중 for문을 최대로 반복하게 되면 시간 복잡도는 O(n^2)이 된다.
- 최선 : 전부 정렬이 돼있으면 안쪽 for문을 통해 정렬이 돼있는지 한 번만 확인하면 되기 때문에 O(n)이 된다.
'Algorithm > Sort' 카테고리의 다른 글
[알고리즘/Algorithm] 파이썬으로 퀵 정렬(Quick Sort) 알아보기 (0) 2021.07.13 [알고리즘/Algorithm] 파이썬으로 병합/합병 정렬(Merge Sort) 알아보기 (0) 2021.07.13 [알고리즘/Algorithm] 파이썬으로 선택 정렬(Selection Sort) 알아보기 (0) 2021.07.06 [알고리즘/Algorithm] 파이썬으로 삽입 정렬(Insertion Sort) 알아보기 (0) 2021.07.05