버블정렬
버블정렬
서로 인접한 두 원소의 대소를 비교하여, 조건에 따라 자리를 교환하여 정렬하는 알고리즘
방법
그림 기준으로 데이터가 6개 있을 때, 5번 순회를 진행한다. 3번 순회때 오름차순 정렬이 끝났지만 계속 진행한다. 인덱스 0번부터 인덱스 5번까지 서로 인접한 두 원소의 대소를 비교한 후 1차 정렬을 마친다면, 이후 2차 순회 및 정렬을 시작하는 것이다. 이때도 인덱스 0부터 시작한다.
사진에서 보면 1차 루프는 총 5번 비교를 한다.
2차 루프에서는 총 4번 비교를 한다. 버블 정렬 특성상 순회를 할 때마다 가장 큰 수가 맨 뒤로 가서 고정이 될 수 밖에 없다. 따라서 이때는 비교하지 않고 그대로 3차 루프로 넘어간다.
예시
1 10 2 3 4 5
1 2 10 3 4 5
1 2 3 10 4 5
1 2 3 4 10 5
1 2 3 4 5 10 ← 제일 큰 원소 10이 맨 마지막 인덱스로 고정.
3차 루프에서는 3번 비교, 4차 루프에서는 2번 비교, 5차 루프에서는 1번 비교하고 끝난다.
- 외부 루프 : 데이터 N개 있을 때 N-1번 순회를 진행한다.
- 내부 루프 : 1회 순회 및 비교할 때마다 제일 큰 원소가 마지막 인덱스가 되기 때문에, 해당 인덱스 요소는 비교 대상에서 제외시켜야 한다. 루프할 때마다 비교 횟수 1회씩 감소
시간복잡도
해당 비교 횟수를 계산하면 5+4+3+2+1 = 15. 즉, (N-1)+(N-2)+(N-3)+…+1의 등차수열의 합으로 된다.
이것은 등차수열의 합 Sn을 유도하는 방법이다.
다른 식도 있지만 여기서 말하는 등차수열의 합은 n(a+l)/2 이다. (a=a1, l=an, n항) 해당 식을 버블정렬 시간 복잡도를 계산한다면 다음과 같다.
즉, (n*n-1)/2 가 되는 것을 알 수 있다.
따라서 시간 복잡도는 O(n^2) 가 된다.
다르게 접근한다면 전체 인덱스를 접근해야 하기 때문에 기본적으로 O(N) 소모, 이후 한번 순회할 때마다 비교 및 교환 연산을 수행하기 때문에 O(N)의 시간이 필요하여 O(N^2)의 시간복잡도를 갖게 된다.
그러나 해당 정렬은 연산수가 많을 수 밖에 없기 때문에 최악, 최선, 평균 모두 O(n^2) 이라는 비효율적인 정렬이다.
메모
2차원 배열을 비교할 때는 arr[0][n-1]과 arr[1][0]을 비교하고 넘어가는 순간도 같이 구현해야 한다.