버블 정렬

출처 : https://www.youtube.com/watch?v=EZN0Irp2aPs&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=3

 

#include <iostream>

using namespace std;

int main(void)
{
  int i, j, tmp;
  int arr[10]={1,5,10,2,4,3,6,8,9,7};
  
  for(i=0; i<10; i++)
  {
    for(j=0; j<9-i; j++)
    {
      if(arr[j]>arr[j+1])
      {
        tmp=arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=tmp;  
      }
    }
  }

  for(int i=0; i<10; i++)
  {
    cout<<arr[i]<<' ';
  }
}

버블정렬은 옆의 원소와 비교하며 자리를 바꾼다. 

 

핵심은 천천히 뒤에서부터 비교하는 집합의 크기가 감소한다는 것이다.

 

■■■■■□

■■■■□

■■■□

■■□

■□

 

흰색은 큰 값을 밀어내고 밀어내어 가장 마지막에 디폴트 된 것이다.

 

그래서 선택정렬과는 다르게 시작점은 고정이고 마지막점이 하나씩 줄어든다.

for(i=0; i<10; i++)
    {
      for(j=0; j<9-i; j++)
      {
        if(arr[j]>arr[j+1])
        {
          tmp=arr[j];
          arr[j]=arr[j+1];
          arr[j+1]=tmp;  
        }
      }
    }

선택정렬과 마찬가지로 시간복잡도는 O(n^2) 이다.

 

그러나 버블정렬은 비교연산 후 스와핑을 2중for문 안에서 다 해야하기 때문에 더 비효율적이다.