bubbleSort.md

버블정렬

버블정렬 알고리즘의 개념

1. 서로 인접한 두 원소를 검사하여 정렬한다.
   1. 인접한 2개의 레코드르르 비교하여 크기가 순서대로(오름차순, 내림차순)대로 되어 있지 않으면 서로 교환한다.
2. 선택 정렬과 기본 개념이 유사하다.

버블정렬 알고리즘의 구체적 개념

• 1-2 2-3 3-4 이런식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환한다.
• 1회전을 마치고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 하고 나면 끝에서 두번째 자료까지는 제외된다. 결론적으로 1회전을 추가 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

버블정렬 알고리즘의 예

버블정렬 코드 및 설명

public String solution(int n, int[] arr){
    for (int i=n-1; i>0; i--){
        /**
            * 버블정렬 그 턴 마지막 index는 다음 턴 정렬 대상에 포함하지 않아야 한다.
            * - 이유는 그 턴의 가장 큰 숫자가 맨 마지막 index에 자리잡기 때문이다.
            * 그래서 순차적으로 j가 j<i(--) 까지만을 비교해야 한다.
            */
        for (int j=0; j<i; j++){
            // j와 j+1, 바로 옆 요소의 값을 비교한다.
            if (arr[j] > arr[j+1]){
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

버블정렬의 알고리즘 특징

• 장점
  • 구현이 매우 간단하다
• 단점
  • 순서에 맞지 않은 요소를 인접한 요소와 교환한다
  • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열의 모든 다른 요소들과 교환되어야 한다.
• 일반적으로 자료의 교환이 이동보다 더 복잡하기 때문에 버블정렬은 단순함에도 거의 쓰이지 않는다.