2. 버블정렬(Bubble Sort)

버블 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다.

  - 오름차순으로 정렬을 한다면 처음 한바퀴 돌때 맨 뒤에는 가장 큰 값이 오게 된다.

  

[1, 2, 5, 4, 3] -> 1, 2 순서가 정렬되어 있으니 그대로 둡니다.

[1, 2, 5, 4, 3] -> 2, 5 순서가 정렬되어 있으니 그대로 둡니다.

[1, 2, 5, 4, 3] -> 5, 4를 바꿔줍니다.

[1, 2, 4, 5, 3] -> 5, 3을 바꿔줍니다.

[1, 2, 4, 3, 5] -> 한 사이클이 끝났습니다.

.....              -> 다시 처음부터 비교를 하여줍니다.

[1, 2, 4, 3, 5] -> 4, 3을 바꿔줍니다.

[1, 2, 3, 4, 5] -> 정렬

 

버블 정렬의 시간복잡도(위의 예제를 참고한다.)

1. 1, 2, 3, 4 , 5, 6, 7, 8, 9, 10 -> 데이터가 10개일때 총 몇번의 비교 연산을 해야할까.
2. 10 + 9 + 8 + 7 ...... + 1 -> 총 비교 연산을 55번해야한다. -> 10*(10 + 1) / 2
3. 데이터가 N개일때 -> N * (N + 1) / 2   (등차수열)
4. 반복문을 두번사용하여 속도가 느리다.
5. 인접한 원소를 비교하여야 하기 때문에 선택 정렬보다 비효율적이고 느리다.