버블 정렬 자세히 알아보기
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]
버블 정렬 시간 복잡도
-
최악의 경우 시간 복잡도: O(n^2)- 기존 배열이 정렬하려는 방식이 역순으로 정렬되어 있는 경우입니다. 이 경우 모든 요소를 배열의 다른 요소와 비교해야 합니다. 배열의 크기가 n일 때, (nxn)번의 비교가 필요합니다.
-
평균 시간 복잡도: O(n^2)- 배열의 요소들이 무작위로 배치된 일반적인 경우에도 대략 (nxn)번의 비교가 필요합니다.
다음 내용이 궁금하다면?
코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!