이 버블 정렬을 어떻게 다르게 구현합니까?

Question

버블 정렬을 구현하려고합니다. 다음 코드는 for 루프를 사용하여 do 루프를 사용하는 코드입니다. 두 개의 for 루프를 사용하는 거품 형으로 만들려면 어떻게해야합니까? 여기

내 코드입니다 :

do { 
    switched = false; 
    for (int i = 1; i < size; i++) { 
     if (a[i] < a[i-1]) { 
      int temp = a[i]; 
      a[i] = a[i-1]; 
      a[i-1] = temp; 
      switched = true; 
     } 
    } 
} while (switched); 

(.이 숙제를 태그가 있지만, 최종 시험, 실제적인 숙제 공부)

Answer 1

목록의 마지막 요소가 항상 정렬되므로 (위에서 위로 버블 링되었으므로) 거기에서 멈출 수 있습니다.

for(int x = size; x >= 0; x--) { 
    bool switched = false; 
    for(int i = 1; i < x; i++) { 
     if(blah) { 
      // swap code here 
      switched = true; 
     } 

    } 
    if(!switched) break; // not the biggest fan of this but it gets the job done 
} 

Answer 2

비트 가지 의무적하지만, 이봐, 당신은 그것을 요구 :

루프에 대한

for(bool switched=true; switched;) 
{ 
    switched = false; 
    for (int i = 1; i < size; i++) { 
     if (a[i] < a[i-1]) { 
      int temp = a[i]; 
      a[i] = a[i-1]; 
      a[i-1] = temp; 
      switched = true; 
     } 
    } 
} 

두 ...

Answer 3

당신은 내부 루프를 실행할 수 있습니다switched을 확인하는 대신 외부 루프 for(int j=0; j<size; ++j)을 사용하여번 반복하십시오. 비효율적 인 방법을 약간 덜 나쁘게 만들려면 매번 내부 루프를 1 단계 더 짧게 만들 수 있습니다.

Answer 4

루프를 통과 한 첫 번째 전체 패스 (즉, 바깥 쪽 do 루프의 첫 번째 반복)는 a[size - 1]에 가장 큰 요소를 넣을 수 있습니다. (이유는 무엇입니까?) 다음 전체 패스는 및을 변경하지 않으며 두 번째로 큰 요소를 위치 a[size - 2]에 배치합니다. (다시, 당신은 왜 볼 수 있습니까?) 등등. 그래서 첫 번째 패스 1에서 size - 1로 이동 i을 필요로하지만, 두 번째는 1에서 size - 2로 이동 i을 필요로, 세 번째는 등등 1에서 size - 3로 이동하고 i이 필요합니다. 전반적으로 최대 size - 1 패스가 필요합니다 (마지막 패스는 위치 이며, 가장 작은 요소가 있는지 확인하기 위해 a[1] ~ a[0]).

그래서, 필요 -loop max_i, 처음 size - 1로 설정 1에서 결말을 변화 할 필요가 -loop 당신의 외부 for 및 for 당신의 내면은 max_i에 1에서 i를 변경합니다.

Answer 5

do 루프가 실행할 수있는 최대 횟수를 생각해보십시오.

Answer 6

내부 루프가 실행되는 최대 횟수는 size 번이므로 바깥 쪽 루프 만 size으로 바인딩 할 수 있습니다. 다음과 같이

for (int x = 0; x < size; x++) 
{ 
    switched = false; 
    for (int i = 1; i < size; i++) 
    { 
     if (a[i] < a[i - 1]) 
     { 
      int temp = a[i]; 
      a[i] = a[i - 1]; 
      a[i - 1] = temp; 
      switched = true; 
     } 
    } 

    if(switched) 
    { 
     break; 
    } 
} 

Answer 7

정말 바보 방법이 될 것이다 루프이 사용하는 :

는

for(bool switched=true;switched;) 
{ 
    switched=false; 
    for(int i=1; i<size; ++i) 
    { 
     if (a[i] < a[i-1]) 
     { 
      int temp = a[i]; 
      a[i] = a[i-1]; 
      a[i-1] = temp; 
      switched = true; 
     } 
    } 
} 

더 심각한 대답은 다음과 같이 수 있습니다 ...

for(int i=0; i<(size-1); ++i) 
{ 
    for(int j=(i+1); j<(size-1); ++j) 
    { 
     if(a[i]>a[j]) 
     { 
      temp=a[i]; 
      a[i]=a[j]; 
      a[j]=temp; 
     } 
    } 
} 

Answer 8

버블 정렬에 대한 간단한 개선 스왑가 발생한 마지막 위치를 기억하는 것입니다하지만 지금은 그것에 대해 생각이 아마 거품 정렬되지 않습니다. 각 패스 후에 해당 점을 초과하는 요소가 정렬됩니다. 다음 번에는 루프를 통해 이전 최고 수위 표시까지만 반복합니다.

void bubble_sort(int *arr, int size) 
{ 
    for (int hwm; size > 1; size = hwm) 
    { 
     hwm = 0; 
     for (int i = 1; i < size; ++i) 
     { 
      if (arr[i] < arr[i-1]) 
      { 
       std::swap(arr[i], arr[i-1]); 
       hwm = i; 
      } 
     } 
    } 
}