[C, C++] Bubble Sort 버블 정렬 코드, 정의

Bubble Sort 버블 정렬이란?

 

Bubble Sort는 대표적인 정렬 알고리즘 중 하나입니다.

그것은 가장 쉬운 정렬 중 하나입니다.

속도 면에서 우월하지는 않지만, 코드가 간편해 널리 쓰이고 있습니다.

Bubble Sort의 알고리즘

버블 정렬에 n개의 자료가 있을 때,

1번째와 2번째를 비교하고

(n-1)번째와 n번째를 비교하고...

그리고 처음으로 돌아가 비교하기 시작하는 방식으로 정렬합니다.

단순 비교 방식이기에 최악의 경우에는 n(n-1)/2 번 연산하게 됩니다.

그래서 위와 같은 식으로 정렬되는데,

이것이 거품이 떠오르는 것과 비슷하다 하여 Bubble Sort라고 합니다.

▲헝가리 포크 댄스를 통해 Bubble-Sort를 설명한 영상

이 영상은 Bubble Sort를 잘 설명하는 예입니다.

Bubble Sort의 C/C++ 코드

C++ 코드

#include <iostream>
using namespace std;
 
int main()
{
  int n,a,b,swap;
    
  int array[1005], i;
 
  cin>>n;
  
  for(i=0; i<n; i++)
    cin>>array[i];
  
  for (a=0 ; a<n-1 ;a++)
  {
    for (b=0 ;b<n-a-1; b++)
    {
      if (array[b] > array[b+1])
      {
        swap = array[b]; array[b] = array[b+1];
        array[b+1] = swap;
      }
    }
  }
    for(i=0;i<n;i++)
    cout<<array[i]<<" ";
}