[실전 알고리즘 강좌] 버블 정렬 (Bubble Sort)
2020.08.05 오늘의 공부
실전 알고리즘 인강을 듣고 정리 중
Github 정리
https://github.com/MIN-04/TIL/blob/master/Algorithm/Sort/bubbleSort.java
동빈나 - 실전 알고리즘 강좌 3강. 버블 정렬
https://www.youtube.com/watch?v=EZN0Irp2aPs&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=3
버블 정렬 (Bubble Sort)
- 서로 인접한(옆에 있는) 값과 비교하여 작은 값을 앞으로 보낸다.
- 정렬 중에서 가장 효율성이 떨어지는 정렬이다.
첫 번째 값과 두 번째 값을 비교하여 작은 값을 앞으로 보낸다. 두 번째 값과 세 번째 값을 비교, ... 이런 순으로 맨 마지막까지 비교한다.
그렇다면 마지막에 남는 것은 가장 큰 수가 남을 것이다.
이게 1회전 끝.
예제
배열에 7,4,5,1,3 순으로 값이 담겨져 있을 때. 버블 정렬을 하면 아래의 그림과 같이 진행된다.
JAVA 코드
배열에 1~5까지의 값이 크기 상관없이 섞여있다. 버블 정렬을 해보자.
결과
버블 정렬의 시간복잡도
버블 정렬의 시간복잡도는?
(ex) 1~10의 값을 비교한다고 했을 때,
9번의 비교가 이루어진다.
따라서, 9+8+7+ ... + 1 번의 비교가 이루어진다.
이걸 등차수열로 표현하면,
10 * (10-1) / 2
10번이 아니라 N번 비교할 때,
N * (N-1) / 2
만약, N이 굉장히 크다고 가정하면 더하기 1과 나누기 2는 의미가 없다.
따라서 대략적으로 N * N으로 나타낼 수 있다.
즉, 버블 정렬은 N * N의 수행 시간을 갖고 있다.
이걸 빅오 표기법 (Big-O nation)으로 표기하면
O(N*N)으로 표기한다.
버블 정렬의 시간 복잡도는 O(N^2)이다.
선택 정렬과 버블 정렬의 시간 복잡도는 같다.
그런데 왜 버블 정렬이 가장 효율성이 떨어지는 정렬일까?
선택 정렬은 전체 중에서 가장 작은 값을 찾아 교환이 이루어진다면,
버블 정렬은 인접한 값과 비교하여 비교할 때마다 교환이 이루어져서 부하가 많이 걸린다.
따라서, 버블 정렬이 가장 효율성이 떨어지는 정렬이다.