바깥 쪽 루프 버블 정렬의 N 값

Question

나는 정렬을 배우고 있습니다 (처음이 아님). 버블 정렬에서 우리는 다음과 같은 코드를가집니다. 모든 볼 수있는 바와 같이

int bubble_sort(int *arr, size_t n) { 

size_t i,j; 
    for(i=0;i<n;i++) { 
    for(j=0;j<n-1;j++) { 
      if(arr[j] > arr[j+1]) { 
        int temp = arr[j]; 
        arr[j] = arr[j+1]; 
        arr[j+1] = temp; 
      } 
    } 
} 

return 0; 
} 

는, 내부 루프는 [I-1]이 모두 하나의 반복 처리에 관여하는 (a [i]는, 이해할 수있는 (루프로) (N-1) 시간을 갖는다),하지만 외부 루프는 내가 < n을 가지고 있지만 그것은 또한 < n-1에서 작동합니다. 그러나 인터넷에서의 대부분의 구현에는 외부 루프 값으로 n이 있습니다. 외부 루프 n-1을 수행하면 최악의 경우에 문제가 없습니다. 5 4 3 2 1. n-1 번 외부 루프에서 작동하지 않는 입력 집합이 있으면 궁금합니다. 있다면 그것을 게시하고 설명하시기 바랍니다. 감사.

Answer 1

N-1도 괜찮습니다. 당신이 묘사 하듯이, 최악의 경우에는 N-1 스왑이 필요합니다 (마지막이 첫 번째가되고, 그 반대도 마찬가지입니다). if 문 내부에 i 변수의 인쇄물을 추가하면 마지막 반복에서 결코 호출되지 않는다는 것을 알 수 있습니다. 이것은 루프의 마지막 반복이 스와핑을 초래하지 않는다는 것을 의미합니다.

Bubblesort를 더욱 효율적으로 구현하면 for 루프가 외부 루프로 사용되지 않습니다. 아래 코드를 살펴보십시오. 실행 차이를 볼 수 있습니까? 실제 스와핑이 발생하는 경우에만 플래그를 설정하여

int bubble_sort(int *arr, size_t n) { 
    size_t i,j; 
    int flag = 1; 
    while (flag) { 
     flag = 0; 
     for(j=0;j<n-1;j++) { 
      if(arr[j] > arr[j+1]) { 
       int temp = arr[j]; 
       arr[j] = arr[j+1]; 
       arr[j+1] = temp; 
       flag = 1; 
      } 
     } 
    } 
    return 0; 
} 

, 당신은 평균의 경우에있어 훨씬 빨리 루프 밖으로 점프하게 될 겁니다.

Answer 2

아니요, 이러한 입력이 없습니다.

합리적인 것은 버블 정렬의 증거입니다. 버블 정렬에서 i 'th (outer) 반복 - 마지막 요소 인 ''이 제자리에 있고 정렬되었다는 것을 증명할 때 기억하십시오.

따라서 n-1 반복 이후에 마지막으로 n-1 요소가 제자리에 정렬되고 남은 첫 번째 요소 (올바른 위치에만있을 수 있음)가 배열의 첫 번째 위치에 남습니다. 고전적인 버블 정렬 때문에의 (내부 루프 만 n-i 반복이 필요합니다 :

또한주의

---

(그래서,이 방법을 사용하여 우리는 버블 정렬이 최대 n-1 외부 반복을 필요로을 증명할 수) 위의 합리적인), 아니 n-1.