[자료구조] Bubble Sort (버블 정렬)

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

개념

서로 인접한 두 원소를 비교해서 일정한 기준을 만족하면 서로의 값을 교환하여 정렬하는 방식

코드가 단순해서 구현이 쉬움
비교 작업이 많아서 연산 시간이 오래 걸림

첫번째와 두번째를 비교 후 변경, 두번째와 세번째를 비교 후 변경, ... n번째와 n + 1번째를 비교 후 변경
위의 작업을 한번 수행시 마지막 위치에 가장 큰 값이 위치함 (오름차순 정렬의 경우)
그러므로 n번 수행을 하면 n개가 정렬이 됨

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

시간 복잡도

(Best Case = Average Case = Worst Case)
T(n) = O(n^2)

 

예제 코드

void buubleSort(int array[], int len)
{
  int temp;

  for (int i = len - 1; i > 0; --i)
  {
    for (int j = 0; j < i; ++j)
    {
      if (array[j] > array[j + 1])
      {
        temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}