[알고리즘]버블정렬이란(Bubble Sort)

▷ 목표

• 버블정렬 알고리즘을 이해합니다.
• 버블정렬 알고리즘의 특징
• 버블정렬 알고리즘의 시간복잡도를 이해합니다.

▷ 제자리정렬

입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이며
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

대표적으로 선택정렬, 버블정렬, 삽입정렬 등이 있습니다.

▷ 버블정렬의 개념

서로 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다.

첫 번째 값와 두 번째 값을, 두 번째 값와 세 번째 값을 ... 마지막까지 값을 비교하여 교환하면서 자료를 정렬합니다.
1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 값은 정렬에서 제외되고

2회전을 수행하고 나면 마지막에서 두 번째 값 또한 정렬에서 제외됩니다.

이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어나는 구조입니다.

원소의 이동이 거품이 수면위로 올라오는 듯한 모습을 보인다고 하여 버블정렬이라고 불리게 되었다고 합니다.

 

<버블정렬을 통한 배열 오름차순 자바 코드>

public class Main {
    public static int[] bubbleSort(int[] arr){
      for(int i=0, n=arr.length; i<n; i++){
        // i회전이 늘어날수록 마지막에서 i번째 값은 제외하기 때문에 j<(n-1)-i입니다.
        for(int j=0; j<(n-1)-i; j++){
           if(arr[j] > arr[j+1]){
             // 인접한 두 원소를 비교하여 왼쪽 인덱스의 값이 더 클 경우 값을 교환해줍니다.
             int swapped = arr[j];
             arr[j] = arr[j+1];
             arr[j+1] = swapped;
           }
        }
      }

      return arr;
    }

    public static void main(String[] args){
      int[] arr = {8, 2, 5, 6, 9};
      bubbleSort(arr);
    }
  }

▷ 버블정렬의 특징

• 장점

    1. 구현이 쉬우며, 코드가 직관적입니다.

    2. 모든 원소를 비교하기 때문에 정밀합니다.

• 단점

    1. 배열의 모든 요소를 비교하므로 비효율적이며 구현이 느려 잘 쓰이지 않습니다.

▷ 버블정렬의 시간복잡도

데이터의 개수가 n개라고 했을 때
첫 번째 회전에서

첫번째 값과 두번째 값, 두번째 값과 세번째 값... n-1번째값과 n번째 값을 비교하여 총 n-1번 비교
두 번째 회전에서

첫번째 값과 두번째 값, 두번째 값과 세번째 값... n-2번째값과 n-1번째 값을 비교하여 총 n-2번 비교

... 
(n-1) + (n-2) + .... + 2 + 1 → n(n-1)/2
즉 주어진 n개의 배열을 정렬하는데 필요한 시간복잡도는 O(n²)입니다.
최선, 평균, 최악의 경우 모두 동일한 시간복잡도를 가집니다.

▷ 참고

• https://en.wikipedia.org/wiki/Bubble_sort