본문으로 건너뛰기

버블 정렬 자세히 알아보기

버블 정렬 자세히 알아보기

1. 2중 for문 활용

버블 정렬은 두 개의 중첩된 반복문을 사용합니다. 외부 반복문은 배열을 통과하는 횟수를 결정하고, 내부 반복문은 배열의 각 요소를 비교합니다.

2중 for문 활용
for i in range(n):
for j in range(0, n-i-1):

2. 원소 비교 및 교환

내부 반복문에서, 인접한 원소들을 비교하고, 필요한 경우 위치를 서로 바꿉니다.

원소 비교 및 교환 예시
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]

버블 정렬 시간 복잡도

  1. 최악의 경우 시간 복잡도: O(n^2)

    • 기존 배열이 정렬하려는 방식이 역순으로 정렬되어 있는 경우입니다. 이 경우 모든 요소를 배열의 다른 요소와 비교해야 합니다. 배열의 크기가 n일 때, (nxn)번의 비교가 필요합니다.
  2. 평균 시간 복잡도: O(n^2)

    • 배열의 요소들이 무작위로 배치된 일반적인 경우에도 대략 (nxn)번의 비교가 필요합니다.