버블 정렬
리스트를 처음부터 여러 번 훑으며, 순서가 틀린 이웃 값을 교환합니다. 한 바퀴를 돌 때마다 남은 값 중 최댓값이 끝으로 갑니다.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- 예
- 예
최선: 이 알고리즘에 가장 쉬운 입력일 때, 리스트 크기 n에 따라 시간이 늘어나는 정도.
평균: n에 따라 시간이 늘어나는 보통의 정도. n²이면 값의 개수가 두 배일 때 시간은 약 네 배이고, n log n은 훨씬 천천히 늘어납니다.
최악: 가장 어려운 입력에서 늘어나는 정도. 속도가 절대 떨어지면 안 될 때 중요합니다.
메모리: 리스트 외에 필요한 추가 메모리 양. 1은 변수 몇 개, n은 리스트 복사본 하나를 뜻합니다.
안정: 같은 값 두 개가 원래 순서를 유지합니다. 레코드의 한 필드로 정렬할 때 중요합니다.
추가 메모리 없음: 두 번째 리스트 없이 리스트 안에서 바로 정렬합니다.
- 비교 중
- 이동 중
- 제자리
해 보세요: 거의 정렬된 리스트를 골라 보세요. 교환이 없는 바퀴가 한 번 나오면 알고리즘이 일찍 멈춥니다.
작동 방식
이웃한 두 값을 비교해서 왼쪽 값이 더 크면 교환합니다. 그래서 한 바퀴마다 최댓값이 거품이 떠오르듯 오른쪽 끝까지 갑니다. 한 바퀴 동안 교환이 한 번도 없으면 리스트는 이미 정렬된 것입니다.
언제 쓰면 좋을까
긴 리스트에서는 느려서 실제 프로그램에서는 거의 쓰지 않습니다. 하지만 배우기에는 아주 좋습니다. 비교하고 교환하는 정렬의 기본 아이디어가 잘 보이기 때문입니다. 빠른 경우는 리스트가 이미 정렬되어 있을 때뿐입니다.