버블 정렬(Bubble Sort)이란
- 반복적으로 바로 옆에 있는 값 과 비교하여 더 작은 값을 앞쪽에 배치하는 정렬 알고리즘
- 정렬 알고리즘 중 구현이 가장 쉽지만 가장 비효율적인 알고리즘
- 반복문이 두번 중첩된 구조로 구현되므로 시간복잡도는 O(N^2)
코드로 표현하기
- 배열에 저장된 모든 원소를 인덱스 순서대로 모두 조회한다.
- 내부 for문에서는 현재 원소값(arr[j])보다 옆에 있는 원소값(arr[j+1])이 더 작다면 두 원소의 위치를 바꾼다.(temp)
- 내부 for문이 한번 종료될 때마다 배열 끝쪽에 정렬된 값들이 하나씩 쌓이게 된다.
#오름차순 정렬 예제
arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
for i in range(len(arr)):
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
#결과 출력
for a in arr:
print(a, end=' ')
위 코드에서 range(len(arr)-i-1)을 해 준 이유는 다음과 같다.
for-range()문에서 range()는 변수의 반복 범위를 지정하는 역할을 하며 다음 세가지 형태로 사용될 수 있다.
- range(종료값)
- range(시작값, 종료값)
- range(시작값, 종료값, 반복 규칙)
여기서 헷갈리는 점이 ‘for문은 종료값까지 실행되고 난 후에 종료되는가?’ 이다.
정답은 NO
예를 들어, for i in range(0,5)라는 문장이 있다면 이것은 i가 0, 1, 2, 3, 4 일때 for문 내부의 문장을 수행하며, i=5가 되면 for문은 종료된다.
따라서, range()의 종료값은 for문 내부에 반영이 되지 않는 값이다
그래서 j+1로 인덱스 위치 조정을 위해서는 range(len(arr)-i-1)코드에 -1이 필요했던 것이다.
아래는 똑같은 구조로 내림차순을 구현한 코드이다.
#내림차순 정렬 예제
arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] #임의의 원소 배열
for i in range(len(arr)):
for j in range(len(arr)-i-1):
if arr[j] < arr[j+1]:
temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
#결과 출력
for a in arr:
print(a, end=' ')