없습니다.
n n-1 n-2 ... 2 1인 경우 반드시 O(N^2)의 횟수로 스왑해야 합니다.
스왑 횟수를 세는 경우엔 인덱스 트리 자료구조를 이용하여 O(nlogn)에 계산 가능합니다.
버블 정렬의 스왑 횟수를 세는 문제가 BOJ에 있습니다.
1377번 문제이고, 해당 문제에 대한 제 O(nlogn) 솔루션은 아래와 같습니다.
자세한 설명은.. 너무 길어서.. 아랫분이 이어서 해주실거예요
http://www.geeksforgeeks.org/counting-inversions/
왜 inversion (i < j && a[i] > a[j] 를 만족하는 쌍의 수) 가 버블 소트의 스왑 횟수냐면, 버블 소트는 스왑 한번에 inversion을 정확히 1 감소 시키고, inversion이 0일 때 종료하기 때문입니다.
댓글을 작성하려면 로그인해야 합니다.
niceghp12 7년 전
6 10 3 7 4 와 같은 수열이 주어졌을때
버블소트 돌리면 수들이 인접한 수들이랑 교환 되잖아요.
그 교환되는 횟수를 O(N^2) 이하로 구하는 알고리즘 혹시 있나요?
구글링을 해봤는데.. 영어를 못해서 쉽지 않네요
흥미로운 주제 같은데.