버블 정렬

정의

• 가장 간단한 정렬 알고리즘 중 하나로, 이름에서 알 수 있듯이 "버블"처럼 큰 값이 배열의 끝으로, 작은 값이 배열의 시작으로 이동하게 다.
• 이 알고리즘의 기본 아이디어는 인접한 두 원소를 비교하여 필요한 경우 위치를 교환하는 것

 

과정

1. 첫 번째 원소부터 마지막 원소까지 반복하면서 인접한 두 원소를 비교한다.
2. 두 원소의 순서가 잘못되어 있다면(즉, 오름차순 정렬에서 첫 번째 원소가 두 번째 원소보다 크다면) 위치를 교환한다.
3. 1~2의 과정을 배열의 끝까지 반복한다. 이렇게 하면 가장 큰 원소가 배열의 마지막 위치로 이동한다.
4. 배열의 길이를 1 줄이고 위의 과정을 반복한다.
5. 배열의 길이가 1이 될 때까지 위의 과정을 반복한다.

 

시간 복잡도

• 최선의 경우: O(n) (이미 정렬된 배열)
• 평균적인 경우: O(n**2)
• 최악의 경우: O(n**2)

장점

• 코드가 단순하고 이해하기 쉽다. 추가적인 메모리가 필요하지 않다.

단점

• 다른 정렬 알고리즘들에 비해 비효율적이다. 큰 데이터셋에서는 다른 알고리즘을 사용하는 것이 좋다.