버블 정렬 알고리즘에서 n-1 반복을 수행하는 이유

Question

버블 정렬 알고리즘의 가장 일반적인 방법은 두 개의 for 루프를 갖는 것입니다. 내부는 j = 0에서 jn-i-1까지 행해진 다. 나는 우리가 마지막 요소에 도달 할 때 우리가 그 요소를 가지고 있지 않기 때문에 그것을 비교하지 않기 때문에 빼기 i를 빼는 것으로 가정합니다. 하지만 왜 우리는 n-1을 사용해야합니까? 우리는 왜 i = 0에서 i가 0이 될 때까지 외부 루프를 실행하지 않고 j = 0에서 n-i까지 내부를 < n? 누군가 나에게 설명해 줄 수 있었는지, 인터넷상의 튜토리얼은 이것을 강조하지 않았다.

for (int i = 0; i < n - 1; i++) // Why do we have n-1 here? 
    { 
     swapped = false; 
     for (int j = 0; j < n - i - 1; j++) 
     { 
      countComparisons++; 
      if (arr[j] > arr[j + 1]) 
      { 
       countSwaps++; 
       swap(&arr[j], &arr[j + 1]); 
       swapped = true; 
      } 

     } 
    } 

예를 들어 6 개의 요소가있는 배열이있는 경우 왜 5 회만 반복하면됩니까?

Answer 1

스왑에는 적어도 두 개의 요소가 필요하기 때문입니다.

6 개의 요소가있는 경우 5 개의 연속 쌍만 고려하면됩니다.