섹션2. 정렬(Sorting). 버블정렬(Bubble Sort)

< 버블정렬 >

  º   다른 정렬 알고리즘에 비해 정렬 시간은 오래 걸리지만 로직이 단순하다

  º    버블정렬이란?
  ->    데이터의 인접요소끼리 비교하고, swap연산을 수행하며 정렬하는 방식

  º   핵심 이론
  ->   두 인접한 데이터의 크기를 비교해 정렬하는 방식입니다. 시간 복잡도는 o(n^2)

  º   수행방식
  ->  인접한 두개의 값을 비교하고 큰 값을 오른쪽, 작은 값을 왼쪽으로 바꿔줌
  ->  두번째 루프에선 정렬된 영역을 제외한 나머지 영역을 정렬해준다

  º    시간복잡도(O(n^2)
  ->   루프 한번을 도는데 모든 데이터를 거쳐서 접근해서 끝까지 가야함. 또한 루프를 도는 횟수만큼 정렬이 됨.
  ->   루프 한번을 도는데 n의 시간복잡도를 가짐
  º    즉, n개의 데이터를 정렬시키려면 n번의 루프가 필요함 -> O(n^2)

  º    만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면, 데이터가 모두 정렬되었다는 뜻.

 

 

<출처>

https://inf.run/xkbj

[무료] Do it! 알고리즘 코딩테스트 with C++ - 인프런 | 강의