Java 거품 정렬 알고리즘 구현 및 간단한 최적화 예시

원리
거품 정렬은 아마도 모든 프로그래머가 사용할 수 있는 알고리즘이자 가장 익숙한 알고리즘 중의 하나일 것이다.
그것의 사고방식은 결코 복잡하지 않다.
현재 그룹arr[] 정렬을 설정합니다. n개의 요소가 있습니다.
1. 만약 n=1: 분명히 배열할 필요가 없다.(실제로 이 토론은 필요없을 것 같다)
2. n>1:
(1) 우리는 첫 번째 원소부터 각 두 개의 인접 원소를 비교한다. 만약에 앞의 원소가 뒤의 원소보다 크다면 마지막 결과에서 전자는 반드시 뒤에 있다.그래서 우리는 이 두 원소를 교환한다.그리고 다음 두 개의 인접한 원소를 비교한다.이렇게 해서 마지막 원소를 비교할 때까지 첫 번째 순서가 완성된다.마지막 원소는 틀림없이 수조에서 가장 큰 것이다. (매번 상대적으로 큰 것을 뒤에 놓았기 때문이다.)
(2) 상술한 과정을 반복하면 이번에는 마지막을 고려할 필요가 없다. 왜냐하면 그것은 이미 배열되어 있기 때문이다.
(3) 이렇게 하면 원소가 하나밖에 남지 않을 때까지 이 원소는 틀림없이 가장 작을 것이다. 그러면 우리의 정렬은 끝날 수 있다.분명히 n-1차 정렬이 진행되었다.
상술한 과정에서 매번 (또는'바퀴'라고 부른다) 정렬할 때마다 하나의 수가 특정한 위치에서 천천히'부동'하여 최종 위치까지 (설명도를 그려서 수조를 세로로 그리면 알 수 있다) 거품이 나는 것과 같아서 거품이 나는 정렬법이라고 부른다.
코드 구현:

public class BubbleSort{
   public static void main(String[] args){
     int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
     for (int i = 0; i < score.length -1; i++){  // n-1 
       for(int j = 0 ;j < score.length - i - 1; j++){  // score[0......length-i-1] (j ， )
         if(score[j] < score[j + 1]){  // 
           int temp = score[j];
           score[j] = score[j + 1];
           score[j + 1] = temp;
         }
       }      
       System.out.print(" " + (i + 1) + " ：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
       }
       System.out.println("");
     }
       System.out.print(" ：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
     }
   }
 }

 
알고리즘 성능/복잡도
우리는 순환 변수의 증가와 초기화 시간을 무시했다.먼저 알고리즘의 비교 횟수를 분석한다.위에서 보듯이 아무런 개선도 거치지 않은 거품 정렬은 입력 데이터가 어떻든 n-1륜 정렬을 하고 각 정렬은 비교가 필요한 횟수가 n-1에서 0으로 점차 줄어든다.그러면 총 비교 횟수는 (n-1)+(n-2)+...+2+1 = (n-1)n/2≈(n^2)/2.(여기서 어떻게 제곱을 칠지 모르기 때문에, 여기, 나는 n^2로 제곱을 대표하고, 아래와 같다)
다음 할당 횟수를 보십시오.이곳의 부치는 그 중의 교환 조작을 가리키는데 상술한 코드에 대해 1회 교환은 3회 부치와 같다.매번 교환해야 하는 것은 아니기 때문에, 값 부여 작업의 횟수는 입력 데이터와 관계가 있다.최적 상황(best case)에서 처음부터 질서정연한 상황에서 부여 횟수는 0이다.최악의 경우(worstcase)에서 부여 횟수는 (n-1)n/2이다.입력 데이터가 평균적으로 (또는'완전 랜덤') 분포된다고 가정하면 대략 교환 횟수는 비교 횟수의 절반이다.위의 결과에 의하면 평균 상황(averagecase)에서 부여 횟수는 3/2*(n^2)/2=3/4*(n^2)이다.
결론적으로 어떤 상황에서도 거품 정렬 공간의 복잡도(추가 공간)는 항상 O(1)이다.
개량하다
데이터가 완전히 질서정연할 때 가장 좋은 시간 복잡도를 보여줍니다. O(n)입니다.다른 상황에서는 거의 항상 O(n^2)이다.따라서 알고리즘은 데이터가 기본적으로 질서정연한 상황에서 성능이 가장 좋다.
그런데 위의 코드에 어떻게 O(n) 복잡도가 나타날 수 있습니까?실제로 위에서 중시하는 것은 기본적인 사고방식이기 때문에 가장 간단한 상황일 뿐이다. 알고리즘이 가장 좋은 상황에서 O(n) 복잡도를 가지려면 약간의 개선이 필요하다. 개선된 코드는 다음과 같다.

public static void bubbleSort(int[] arr) {
  int temp = 0;
  boolean swap;
  for (int i = arr.length - 1; i > 0; --i) { //  
    swap=false;
    for (int j = 0; j < i; ++j) { //  i 
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swap=true;
      }
    }//loop j
    if (swap==false){
      break;
    }
  }//loop i
}// method bubbleSort

실제로 대량의 데이터 상황에서 거품 정렬을 거의 사용하지 않기 때문에 작은 데이터를 사용할 때 증가하는 볼 변수는 오히려 추가 비용을 초래할 수 있다.그래서 개인적으로 상기에서 개선된 알고리즘은 순수한 이론일 뿐이라고 생각한다. 통상적으로 거품 정렬은 앞의 것을 쓰면 된다.
알고리즘 안정성
인접 원소가 같을 때 우리는 그들의 위치를 교환할 필요가 없기 때문에 거품 정렬은 안정적인 정렬이다.
알고리즘 적용 장면
거품이 생기는 정렬 사고방식은 간단하고 코드도 간단하며 특히 작은 데이터의 정렬에 적합하다.그러나 알고리즘의 복잡도가 높아 데이터량이 많을 때 사용하기에 적합하지 않다.만약 반드시 비교적 많은 데이터를 사용할 때 사용해야 한다면 알고리즘을 개선하는 것이 가장 좋다. 예를 들어 정렬법을 선택하는 것이다.