niceghp12   6달 전

6 10 3 7 4 와 같은 수열이 주어졌을때
버블소트 돌리면 수들이 인접한 수들이랑 교환 되잖아요.
교환되는 횟수를 O(N^2) 이하로 구하는 알고리즘 혹시 있나요?
구글링을 해봤는데.. 영어를 못해서 쉽지 않네요
흥미로운 주제 같은데.

kipa00   6달 전

없습니다.

n n-1 n-2 ... 2 1인 경우 반드시 O(N^2)의 횟수로 스왑해야 합니다.

스왑 횟수를 세는 경우엔 인덱스 트리 자료구조를 이용하여 O(nlogn)에 계산 가능합니다.

버블 정렬의 스왑 횟수를 세는 문제가 BOJ에 있습니다.

1377번 문제이고, 해당 문제에 대한 제 O(nlogn) 솔루션은 아래와 같습니다.

자세한 설명은.. 너무 길어서.. 아랫분이 이어서 해주실거예요

baekjoon   6달 전

Merge Sort를 이용해서도 풀 수 있습니다.

koosaga   6달 전

http://www.geeksforgeeks.org/counting-inversions/

왜 inversion (i < j && a[i] > a[j] 를 만족하는 쌍의 수) 가 버블 소트의 스왑 횟수냐면, 버블 소트는 스왑 한번에 inversion을 정확히 1 감소 시키고, inversion이 0일 때 종료하기 때문입니다.

댓글을 작성하려면 로그인해야 합니다.