1. 버블 정렬 알고리즘의 개요
- 버블 정렬은 가장 간단하고 직관적인 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 순서에 맞지 않으면 서로 교환하는 과정을 반복하여 정렬하는 방법이다.
- 이름은 정렬 과정에서 값이 끝까지 "영향력을 전파"하여 위로 "버블"처럼 올라가는 것에서 유래되었다.
- 주로 배열에 저장된 데이터를 정렬하는데 사용되며, 데이터의 이동이 이웃한 위치에서만 일어나기 때문에 안정 정렬(stable sort)에 속한다.
- 시간 복잡도는 최악, 최선, 평균 모두 O(n^2)으로 비효율적이지만, 구현이 단순하고 작은 리스트에 대해서는 효율적일 수 있다는 장점이 있다.
2. 배열을 오름차순으로 정렬하는 버블 정렬 알고리즘의 원리
- 주어진 배열을 순차적으로 탐색하면서 인접한 두 원소를 비교한다.
- 현재 원소와 다음 원소를 비교하여 현재 원소가 더 크다면, 두 원소를 교환한다. 만약 오름차순으로 정렬한다면, 현재 원소가 다음 원소보다 클 경우 교환한다.
- 배열의 끝까지 탐색한 후, 가장 큰 원소가 끝으로 이동하게 된다.
- 이렇게 맨 끝에 있는 가장 큰 원소는 정렬이 완료된 상태라고 볼 수 있다.
- 정렬이 완료되지 않았을 경우, 정렬이 완료된 부분을 제외하고 나머지 부분으로 다시 돌아가 반복적으로 위 과정을 수행한다.
- 위 과정을 모든 원소가 정렬될 때까지 반복하면 오름차순으로 정렬된 배열을 얻을 수 있다.
예시:
원본 배열: [5, 2, 8, 6, 1]
1회전: [2, 5, 6, 1, 8]
2회전: [2, 5, 1, 6, 8]
3회전: [2, 1, 5, 6, 8]
4회전: [1, 2, 5, 6, 8]맨 처음 5와 2를 비교하여 2가 더 작으므로 교환한다. 그 다음 5와 8을 비교하여 정렬된 상태이므로 교환하지 않는다. 이렇게 정렬이 완료될 때까지 위 과정을 반복한다.
3. 효율적인 버블 정렬 알고리즘의 구현 방법
효율적인 버블 정렬 알고리즘은 기본적인 버블 정렬의 구현 방법과 동일하지만, 몇 가지 개선점을 추가하여 불필요한 반복을 줄여 실행 시간을 최적화하는 방법이다.
단축된 반복문 범위 설정
- 각 패스마다 마지막으로 교환된 위치를 기준으로 다음 패스에서는 해당 위치까지만 탐색하도록 반복문의 범위를 제한한다.
- 이전에 정렬이 완료된 가장 큰 원소의 위치를 기억하고 있다가, 그 이후부터는 정렬이 완료되었으므로 탐색하지 않아도 된다.
이미 정렬된 부분은 제외
- 각 패스마다 맨 마지막으로 교환된 위치를 기록한다.
- 이를 이용하여 다음 패스에서는 정렬된 부분을 제외하고 탐색하도록 범위를 제한한다.
- 마지막으로 교환된 위치 이후부터는 정렬이 완료되었으므로 탐색하지 않아도 된다.
정렬이 이미 완료되었는지 체크
- 패스마다 교환이 발생하지 않을 경우, 더 이상 정렬할 필요 없이 이미 정렬이 완료된 상태이므로 종료한다.
위의 개선 사항을 적용한 효율적인 버블 정렬 알고리즘의 구현은 다음과 같다:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
is_swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
is_swapped = True
if not is_swapped:
break
return arr이렇게 개선된 구현 방법을 사용하면, 정렬이 이미 완료되었더라도 불필요한 반복을 줄이고 실행 시간을 최적화할 수 있다.