[정렬 알고리즘] - 버블정렬 O(n²)

버블정렬

데이터의 인접 요소 끼리 비교하고 Swap 연산을 수행하여 정렬한다.

 

장점

다른 정렬 알고리즘에 비해 정렬 시간은 다소 오래걸리지만, 상대적으로 로직이 단순하고 구현이 쉽다.

 

핵심이론

• 인접한 데이터 크기를 비교하여 정렬
• 간단하게 구현 가능
• n²의 시간복잡도를 갖음 ( 다른 정렬 알고리즘 보다 느림)
  
  

n² 시간복잡도 원리

loop 1회 도는데 n의 시간복잡도를 가진다

예를들어 n = 5 일때 5개의 데이터를 5회 동안 loop를 돌면서 비교하므로 5 * 5 는 5² 이 된다.

(loop 1회당 정렬된 데이터 1개씩 추가 = 정렬할 데이터가 1개씩 감소)

 

<그림 설명>

 

 

 

 

 

 

버블정렬 과정

1. 비교 연산이 필요한 루프 범위를 설정한다. (데이터의 갯수만큼 반복해야한다.)
2. 인접한 데이터끼리 비교한다.
3. Swap 조건에 부합할 경우 Swap연산을 수행한다
   (오름차순: 큰수가 우측으로 / 내림차순: 범위 역순, 큰수가 좌측으로)
4. loop 범위 종료까지 2. ~ 3. 순서를 반복한다.
5. 정렬된 영역 설정 (다음 loop 실행 시 해당 영역의 데이터는 제외한다.)
6. 비교 대상이 없을 때 까지 1. ~ 5. 순서를 반복한다.

특정 LOOP의 전체 영역에서 Swap이 한번도 발생하지 않았다면 전체 정렬이 완료되었기 때문에 정렬 프로세스를 종료

∴ 사실상 정렬 종료시점의 마지막 LOOP는 전체정렬 여부를 확인하는 셈