어느 것이 실제 버블 정렬이고 어느 것이 더 낫습니까?

다음 두 알고리즘의 실제 버블 정렬에 대해 친구와 논쟁을 벌였습니다. 어느 쪽이 더 낫지 만 내 것이 어떤 언급이 아니라면 두 알고리즘에 대한이 두 질문에 대한 답변을 듣고 싶습니다 (C++로 작성)어느 것이 실제 버블 정렬이고 어느 것이 더 낫습니까?

1 - 어느 것이 진짜 버블 정렬입니까?
2 - 어느 것이 더 낫습니까? 여기

는이 알고리즘은 다음과 같습니다

// Number one : 
void BubbleSort(int Arr[], int size) 
{ for (int i=0;i<size-1;i++) 
     for (int j=i+1;j<size;j++) 
      if (Arr[i]>Arr[j]) 
      { int temp = Arr[i]; 
       Arr[i] = Arr[j]; 
       Arr[j] = temp; 
}   } 

// Number two : 
void BubbleSort(int Arr[], int size) 
{ for (int i=0;i<size-1;i++) 
     for (int j=0;j<size-1;j++) 
      if (Arr[j]>Arr[j+1]) 
      { int temp = Arr[j]; 
       Arr[j] = Arr[j+1]; 
       Arr[j+1] = temp; 
}   }

출처

2010-12-03 Tamer Shlash

버블 정렬은 어떤 종류의 프로덕션 코드에서도 사용해서는 안된다는 점에 유의해야합니다. 삽입 정렬과 같은 다른 비교 기반 정렬과 비교해도 쉽지만 구현하기가 쉽지만 거의 버블 정렬보다 우수합니다 (if 모든 경우). 나는 멀리까지 가서 버블 종류를 더 이상 가르쳐서는 안된다고 말한다. – helpermethod

파이썬은 오른쪽으로 2 번째 홀의 홀 아래에 있습니다. 진지하게 : C 들여 쓰기를 사용하십시오. 그것을 위장하지 마십시오. – pmg

넘버 투는 진짜에 더 가깝다. 모든 비교는 인접 요소 사이에 있어야합니다.

하지만 진짜 버블 정렬은 외부 for 루프 대신 while 루프를 취할 것, 그리고 while 루프 요소는 다음과 같이 마지막 패스를 교환해야했다 경우에만 다시 실행합니다 :

void BubbleSort(int Arr[], int size) 
{ 
    bool swapped; 
    do { 
     swapped = false; 
     for (int j=0;j<size-1;j++) 
      if (Arr[j]>Arr[j+1]) { 
       int temp = Arr[j]; 
       Arr[j] = Arr[j+1]; 
       Arr[j+1] = temp; 
       swapped = true; 
      } 
    } while (swapped); 
}

출처

2010-12-03 17:06:41

각 패스 후에 다시 false로 바꿔서 초기화해야한다고 생각하십니까? –

그래, 그리워. 결정된. –

@userunknown 네 말이 맞아. 결정된. –

중첩 루프 거품 정렬에 대한 의사 코드이다 :

procedure bubbleSort(A : list of sortable items) 
    n := length(A)-1 
    for(i=0; i<= n; i++) 
    for(j=n; j>i; j--) 
     if A[j-1] > A[j] then 
      swap (A[j-1], A[j]) 
     end if 
    end for 
    end for 
end procedure

이 제 난 후의 요소의 내부 루프 만 반복 때문에 가장 가까운 것을 의미한다. 두 번째 방법은 모든 요소를 반복하는 inner 루프를 사용합니다. 이미 정렬하기 전에 요소를 정렬했기 때문에 시간을 낭비 할 필요가 없습니다.

즉 첫 번째 방법이 더 좋습니다.

출처

2010-12-03 17:10:26 Alain

그러나 그의 첫 번째 방법에서는 Arr [j-1] 및 Arr [j] –

+1이 아닌 Arr [i]와 Arr [j]를 실제로 비교하여 버블 정렬을 게시합니다. –

2 번 질문에 대한 답변 : "더 좋음"도 아닙니다. 둘 다 O (n^2) 개의 정렬 알고리즘 (끔찍한)입니다. 정렬 알고리즘에 대한 소개 이외에 Bubble Sort는 쓸모가 없습니다.

출처

2010-12-03 19:46:38

어느 것이 실제 버블 정렬이고 어느 것이 더 낫습니까?

답변

관련 문제