Bubble Sort [MarkDown Test]

Bubble Sort

• 배열의 연속된 두 원소의 크기를 비교하여 정렬하는 정렬 알고리즘
• 반복될 때 마다 가장 큰 원소부터 자신의 위치를 찾는다.
  • $i$번째 반복에서는 뒤에서 $i$개의 (이미 정렬된) 원소를 제외해도 상관없다.

    알고리즘

1. 주어진 배열의 제일 앞의 두 원소 $x_1$, $x_2$를 선택한다.
2. 두 원소가 정렬된 상태라면 그대로 두고, 그렇지 않다면 두 원소의 위치를 서로 바꾼다.
3. (1), (2)를 배열의 처음부터 끝까지 반복한다.
4. (1), (2), (3)을 배열에 아무 변화가 없을 때 까지 반복한다.

시간 복잡도

	Compare	Change
Best	$O(n)$	$O(1)$
Average	$O(n^2)$	$O(n^2)$
Worst	$O(n^2)$	$O(n^2)$
## 공간 복잡도
Support	$O(1)$
:---	:---
## 예제
### Phase 1 : [3, 4, 2, 5, 1]
- [3, 4, 2, 5, 1]
- 3 < 4 이므로 변동 X
- [3, 4, 2, 5, 1]
- 4 > 2 이므로 두 수를 바꿈
- [3, 2, 4, 5, 1]
- 4 < 5 이므로 변동 X
- [3, 2, 4, 5, 1]
- 5 > 1 이므로 두 수를 바꿈
- [3, 4, 2, 1, 5]
### Phase 2 : [3, 2, 4, 1, 5]
- [3, 2, 4, 1, 5]
- 2 < 3 이므로 변동 X
- [2, 3, 4, 1, 5]
- 3 < 4 이므로 변동 X
- [2, 3, 4, 1, 5]
- 4 > 1 이므로 두 수를 바꿈
- [2, 3, 1, 4, 5]
- 4 < 5 이므로 변동 X
- [2, 3, 1, 4, 5]

Phase 3 : [2, 3, 1, 4, 5]

• [2, 3, 1, 4, 5]
  • 2 < 3 이므로 변동 X
• [2, 3, 1, 4, 5]
  • 3 > 1 이므로 두 수를 바꿈
• [2, 1, 3, 4, 5]
  • 3 < 4 이므로 변동 X
• [2, 1, 3, 4, 5]
  • 4 < 5 이므로 변동 X
• [2, 1, 3, 4, 5]

Phase 4 : [2, 1, 3, 4, 5]

• [2, 1, 3, 4, 5]
  • 2 > 1 이므로 두 수를 바꿈
• [1, 2, 3, 4, 5]
  • 2 < 3 이므로 변동 X
• [1, 2, 3, 4, 5]
  • 3 < 4 이므로 변동 X
• [1, 2, 3, 4, 5]
  • 4 < 5 이므로 변동 X
• [1, 2, 3, 4, 5]

Phase 5 : [1, 2, 3, 4, 5]

• [1, 2, 3, 4, 5]
  • 1 < 2 이므로 변동 X
• [1, 2, 3, 4, 5]
  • 2 < 3 이므로 변동 X
• [1, 2, 3, 4, 5]
  • 3 < 4 이므로 변동 X
• [1, 2, 3, 4, 5]
  • 4 < 5 이므로 변동 X
• [1, 2, 3, 4, 5]

Phase 6 : [1, 2, 3, 4, 5]

• Phase 5에서 변동이 없었으므로 정렬 완료

  코드

  def bubble_Sort(x):
    is_changed = False
    for i in range(len(x) - 1):
        is_changed = False
        for j in range(len(x) - 1):
            if x[j] > x[j+1]:
                is_changed = True
                temp = x[j+1]
                x[j+1] = x[j]
                x[j] = temp
        if is_changed == False:
            break
    return x