[알고리즘] 버블 정렬(Bubble Sort) 알고리즘 쉽게 구현해보기 (C++)

 

 

 

이 글은 프로그래밍에 능숙하지 않으신 분들도 어렵지 않게 이해할 수 있도록 최대한 쉽게 풀어 설명한 글입니다.

 

왜냐하면 저도 초보자거든요.

 

 

 

 

 

<1> 버블 정렬이란 무엇인가?

 

 

버블 정렬은 대표적인 정렬 알고리즘 중 하나로

 

원소를 정렬하는 모습이 마침 거품이 올라오는 모습같다고 해서 붙여진 이름이다.

 

 버블 정렬은 아래와 같은 알고리즘으로 동작한다.

 

 

 『 데이터의 수를 N이라고 하자. 아래의 과정을 N번 반복한다.

배열의 0번 칸의 숫자가 1번 칸의 숫자 보다 크다면 두 값의 위치를 교환한다

배열의 1번 칸의 숫자가 2번 칸의 숫자 보다 크다면 두 값의 위치를 교환한다

...

배열의 N-2번 칸의 숫자가 N-1번 칸의 숫자 보다 크다면 두 값의 위치를 교환한다. 』

 

 

즉, 한 번의 순환이 끝나면 조사한 모든 원소 중 가장 큰 숫자가 맨 끝자리에 놓이게 되는 것이다.

 

이 끝자리 원소만 제외하고 2번째 순환을 진행하면, 2번째 끝자리에 2번째로 큰 수가 놓이게 된다.

 

이걸 계속 반복하면 결국 모든 원소가 오름차순으로 배열되게 되어있다.

 

고마워요! 구글

 

버블 정렬 gif

 

 

 

 

 

<2> 버블 정렬 구현

 

(1) 메인 함수

 

먼저, 메인 함수에는 정수형 배열에 원소값을 입력 받고

 

함수로 구현한 알고리즘을 통해 배열 원소를 오름차순으로 재배열 한 후

 

반복문으로 각 원소 값을 출력하는 과정이 있어야 할 것이다.

#include <stdio.h>
#include <iostream>
using namespace std;

void bubbleSort (int* data, int n);

int main(void)
{
  int n = 0;
  int *data = NULL;

  scanf("%d", &n);
  data = new int[n];

  for (int i = 0; i < n; i++)
  {
    scanf("%d",&data[i]);
  }

  bubbleSort(data, n);

  for (int i = 0; i < n; i++)
  {
    if (i > 0)
    {
      printf(" ");
    }
    printf("%d", data[i]);
  }

  delete[] data;

  return 0;
}

 

 

 

(2) 버블 소트 (Bubble Sort) 구현 함수

 

 

이제 위에서 설명한 알고리즘의 과정대로 버블 정렬 알고리즘을 함수로 구현해보자.

 

 

 『배열의 N-2번 칸의 숫자가 N-1번 칸의 숫자 보다 크다면 두 값의 위치를 교환한다. 』

 

먼저, 인덱스 0부터 n-1까지 인접한 두 원소를 서로 비교하며 자리를 바꿔주는 과정이 필요하다.

 

인덱스 0부터 n-1까지 원소를 조사할 반복문과, 그 안에 두 원소를 비교할 조건문이 필요하겠구나.

 

원소를 바꾸는 과정은 temp 임시 변수를 이용하자.

 

 

그리고, 이 과정이 한 번 끝나면 맨 끝자리를 제외하고 다시 이 과정을 반복한다.

 

반복문의 변수를 잘 조절해서 이중 반복문으로 구현을 하면 될 것이다.

 

void bubbleSort (int* data, int n)
{
  int temp = 0;

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

 

 

 

완성된 코드는 다음과 같다.

 

#include <stdio.h>
#include <iostream>
using namespace std;

void bubbleSort (int* data, int n)
{
  int temp = 0;

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

int main(void)
{
  int n = 0;
  int *data = NULL;

  scanf("%d", &n);
  data = new int[n];

  for (int i = 0; i < n; i++)
  {
    scanf("%d",&data[i]);
  }

  bubbleSort(data, n);

  for (int i = 0; i < n; i++)
  {
    if (i > 0)
    {
      printf(" ");
    }
    printf("%d", data[i]);
  }

  delete[] data;

  return 0;
}

 

 

 

<3>  마무리

 

필자는 버블 정렬이 선택 정렬보다 로직이 조금 더 간단하게 느껴져서 그런지

 

생각만큼 어렵지 않게 알고리즘을 구현할 수 있었다.

 

혹시 알고리즘 공부가 어려운 분들도 의지를 갖고 조금만 더 생각해 본다면 어렵지 않게 이 알고리즘을 이해하고 구현할 수 있을 것이다.

 

 

버블정렬은 이렇듯 구현이 간단하나 잘 쓰이지는 않는다고 한다.

 

그냥 공부용으로..