#### 버블 정렬이란?
처음부터 끝까지 숫자 2개씩 비교하는거 반복하다보면 정렬되는 알고리즘
#### 버블 정렬 구현 (기본)
```python
for i in range(n-1):
for j in range(n-1, i, -1):
if a[j-1] > a[j]:
a[j-1], a[j] = a[j], a[j-1]
```
{ 원소 수가 n인 배열에서 n-1번 비교, 정렬해주면 가장 작은 원소가 맨 앞으로 이동한다. } <= 이걸 패스라고 한다
완벽하게 전부 정렬되려면 패스를 n-1번 해야 한다.
#### 버블 정렬 구현 (최적화 1)
```python
for i in range(n-1):
exchng = False
for j in range(n-1, i, -1):
if a[j-1] > a[j]:
a[j-1], a[j] = a[j], a[j-1]
exchng = True
if not exchng:
break
```
무조건 n-1번 정렬하면 이미 정렬됐는데도 계속 순회하는 상황이 발생하므로
정렬 한 번도 안 했으면 순회 끝내기
#### 버블 정렬 구현 (최적화 2)
```python
k = 0
while k < n - 1:
last = n - 1
for j in range(n-1, k, -1):
if a[j-1] > a[j]:
a[j-1], a[j] = a[j], a[j-1]
last = j
k = last
```
최적화 1 버전은 처음부터 끝까지의 패스 1번이 끝나야 exchng가 일어났는지 안 일어났는지 검사하니까
이번엔 가장 마지막 교환이 어디서 이루어졌는지 확인
#### 셰이커 정렬
```python
left = 0
right = len(a) - 1
last = right
while left < right:
for j in range(right, left, -1):
if a[j-1] > a[j]:
a[j-1], a[j] = a[j], a[j-1]
last = j
left = last
for j in range(left, right):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
last = j
right = last
```
최솟값이랑 최댓값 기억해놨다가 각 끝으로 보내버리는 정렬
각 끝의 범위는 점점 줄어든다
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined/undefined-9.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.