양방향 버블 정렬

Question

나는 다음과 같은 문제를 해결해야합니다. 그래서 처음에는 버블 정렬이 있었고 이제는 양방향으로 만들도록 수정했습니다. 다음은 내 솔루션입니다.

public void bubbleSort() { 
    int temp; 
    int out; 
    int outNew = 0; 
    int in; 

    for (out = nElems - 1; out > outNew; out--) { 

     for (in = 0; in < out; in++) { 

      if (a[in] > a[in + 1]) { 
       temp = a[in + 1]; 
       a[in + 1] = a[in]; 
       a[in] = temp; 
      } 
     } 

     for (int j = in - 1; j > outNew; j--) { 

      if (a[j] < a[j - 1]) { 
       temp = a[j]; 
       a[j] = a[j - 1]; 
       a[j - 1] = temp; 
      } 

     } 

     outNew++; 

    } 

} 

내 버블 정렬을 배열에서 몇 개의 난수를 정렬하도록 정렬하면 정렬이 잘된 것 같습니다. 내 질문은 오히려 모든 개발자에게 내 솔루션이 위에 게시 된 질문을 만족시키는 지 여부와이 솔루션을보다 효과적으로 만들 수있는 방법 (가능한 경우)을 다르게 수행 할 수 있는지 여부입니다. 이것이 조금 열려있는 질문이라면 유감스럽게 생각합니다. 코드를 배우기보다는 힌트와 제안을 찾고 있습니다. 나는 모든 대답에 감사 드리며 어떤 제안이든지 열려 있습니다.

Answer 1

첫 번째 내부 루프는 배열이 양 끝에서 부분적으로 정렬되므로 약간 비효율적으로 보입니다. 첫 번째 라운드 (인덱스를 한 번 감소시키면서 한 번씩 증가 시키면)는 첫 번째 요소와 마지막 요소가 이미 정확하므로 인덱스 0에서 시작하지 않아도됩니다 (그리고 작업/연습에는 btw가 필요합니다).

: ( | 간의 모든 지표가 고려되어야 in+1 및 j-1에 도달 인덱스 포함)

다음 ASCII 아트 알고리즘 9 개 요소와 배열의 예에서의 동작해야와 indices되는, 증명

position: 0 1 2 3 4 5 6 7 8 
------------------------------------------------------------ 
      |     ->      | 
      |     <-     | 
       |    ->     | 
       |    <-    | 
        |   ->    | 
        |   <-  | 
         | ->  | 
         | <- | 

그러나 알고리즘이하는 것은 :

position: 0 1 2 3 4 5 6 7 8 
------------------------------------------------------------ 
      |      ->      | 
      |      <-      | 
      |      ->    | 
       |    <-    | 
      |      ->   | 
        |   <-   | 
      |      ->  | 
         |  <-  | 

당신은 루프 제 1 내부의 초기 인덱스를 수정해야합니다.

Answer 2

간단히 말해서, 나는 당신이 나에게 더 효과적 일 수 있고 동시에 질문에 대답 할 수 있다고 생각하지 않는다. 꽤 작은 아이템을 찾을 때까지 아이템을 오른쪽으로 가져 가야하고 마지막으로 가져간 아이템보다 약간 작은 아이템을 가져 가야합니다. 나는 일반적인 단방향 버블 정렬에서 어떤 성능 향상도 없다고 생각하지만, 만약 당신이 그것을 양방향으로 만들 것이라면, 이것은 그것을하는 방법이다.

어떻게 알 수 있습니까? 성능 향상/저하가 없기 때문에 왼쪽에서 오른쪽 코드와 오른쪽에서 왼쪽으로 나온 코드는 완벽하게 대칭이어야합니다 (성능 측면에서 동일하므로). 당신의 경우에, 나는 그것이 좋다고 말하고 싶습니다.

조금 더 깊이 생각하면 양방향성이 아닌 약간의 최적화가 있습니다. 방금 보았던 항목을 얻고 있기 때문에 초기 위치에서 왼쪽으로 가져올 수 있다는 것을 알기 때문에 오른쪽을 건너 뜁니다. 배열의. 그러나 결국에는 무시할 만하 며 슬라이스에 관계없이 여전히 O (n²) 성능입니다.