lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

pythonIntroAlgorithms1Chapter2Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

lesson18Title

lesson19Title

pythonIntroAlgorithms1Chapter1Title

pythonIntroAlgorithms1Chapter3Title

pythonIntroAlgorithms1Chapter4Title

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 배열의 끝에서 이미 정렬된 부분을 제외하고 반복
        for j in range(0, n-i-1):
            # 인접한 두 요소를 비교하여 필요에 따라 위치 교환
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr


example_list = [64, 34, 25, 12, 22, 11, 90]

sorted_list = bubble_sort(example_list)

print('정렬된 배열', sorted_list) # [11, 12, 22, 25, 34, 64, 90]

# 버블 정렬 자세히 알아보기

## 1. 2중 for문 활용

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

```python title="2중 for문 활용"
for i in range(n):
  for j in range(0, n-i-1):
```

<br />

## 2. 원소 비교 및 교환

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

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

<br />

## 버블 정렬 시간 복잡도

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

   - 기존 배열이 정렬하려는 방식이 역순으로 정렬되어 있는 경우입니다. 이 경우 모든 요소를 배열의 다른 요소와 비교해야 합니다. 배열의 크기가 n일 때, (nxn)번의 비교가 필요합니다.

2. `평균 시간 복잡도`: O(n^2)

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