버블 정렬

• 정의
  • 다른 정렬에 비해 시간이 오래걸리지만 로직이 단순하고 구현이 간단하다
  • 데이터의 인접 요소끼리 비교, swap연산을 수행하며 정렬하는 방식
• 핵심
  • 인접한 데이터의 크기를 비교해 정렬하는 방식
  • 시간복잡도는 O(n^2)으로 다른 알고리즘에 비해 느리다
  • 인접한 데이터간에 Swap 연산으로 정렬한다
• 정렬 과정
  • 
  • 비교 연산이 필요한 루프 범위를 설정한다
  • 인접한 데이터 값을 비교한다
  • swap 조건에 부합하면 swap 연산을 수행한다
  • 루프 범위가 끝날 때 까지 2,3번 과정을 반복한다
  • 정렬 영역을 설정하여 다음 루프를 실행할 때 이 영역을 제외한다
  • 비교대상이 없을 때 까지 위의 과정을 반복한다
• 구현
  

  #include<iostream>
  #include <vector>
  using namespace std;
  
  void BubbleSort(vector<int>& v)
  {
      int size = (int)v.size()-1;
  
      bool changed = false;
      for (int i = 0; i < size; i++)
      {
          changed = false;
          for (int j = 0; j < size - i; j++)
          {
              if (v[j] > v[j + 1])
              {
                  changed = true;
                  swap(v[j], v[j + 1]);
              }
          }
          if (changed == false)
              break;
      }
  }
  
  int main()
  {
  	vector<int> v = { 42,32,15,24,60 };
  
  	BubbleSort(v);
  
  }