얼마나 많은 시간을 지정 [버블 정렬 알고리즘]

Question

1. for i=1 to n-1 do 
2. for j=1 to n-i do 
3.  if a[j]>A[j+1] then 
4.   Change A[j] with A[j+1] 

은 3 선합니다 (if 문)에서 여러 번 명령이 수행되는 방법을 알려주십시오.

이것이 수정되지 않은 첫 번째 기본 거품 정렬 알고리즘이라고 생각합니다.
우선 가장 좋은, 평균, 최악의 세 가지 사례를 고려해 보겠습니다.

가장 좋은 if 문은 n-1 번 수행됩니다. 배열의 데이터는 이미 분리되어 있습니다. 배열과 끝 알고리즘을 수행하는 것으로 충분합니다. 에서

최악의 경우는 문이 수행 될 경우 :

<a href="http://www.codecogs.com/eqnedit.php?latex=\sum_{i=1}^{n-1}\tfrac{n(n-1)}{2}" target="_blank"><img src="http://latex.codecogs.com/gif.latex?\sum_{i=1}^{n-1}\tfrac{n(n-1)}{2}" title="\sum_{i=1}^{n-1}\tfrac{n(n-1)}{2}" /></a>

번. 배열의 데이터는 분리되지 않으며 각 위치는 스왑됩니다. 평균 경우

은 문이 수행 될 경우 :

<a href="http://www.codecogs.com/eqnedit.php?latex=\sum_{i=1}^{n-1}\tfrac{n(n-1)}{4}" target="_blank"><img src="http://latex.codecogs.com/gif.latex?\sum_{i=1}^{n-1}\tfrac{n(n-1)}{4}" title="\sum_{i=1}^{n-1}\tfrac{n(n-1)}{4}" /></a>

번? 나는 그것이 최악의 경우를 2로 나눌 것이기 때문에 그렇게 생각한다.

나는 제대로 생각하는지 물어보고 싶다. 내가 틀렸다고 생각하면 저를 바로 잡으십시오.

인사말,

Answer 1

이 점검이 없습니다 - 배열이 이미 정렬되어있는 경우 - 코드에서, 그래서 항상

Q = 1 + 2 + 3 + ... + n-1 = n * (n-1)/2 

하지 않는 것이 Wiki code 검사의 경우 명령문의 수

....  
    until not swapped 

최상의 사례 (정렬 된 배열)에 if-statements (n-1)을 실행할 수 있습니다.

Answer 2

if 문은 항상 정확히 같은 횟수 n^2/2로 실행됩니다.

얼마나 자주 문 4가 실행되는지는 흥미로운 질문입니다. 특히 평균적인 숫자의 경우 수학은 흥미로울 것입니다.