알고리즘 - bubble sort(버블 정렬)

정렬의 필요성

정렬의 필요성은 간단하다.

원하는 자료를 더욱 빨리 찾을 수 있게 도와주기 때문이다.

어떤 수를 찾을 때 정렬이 되있지 않다면 장기적으로 보면 시간과 자원의 낭비가 적체되는 현상을 겪는다.

정렬이 되지 않으면 탐색 또한 효율적으로 진행될 수 없다.

 

버블 정렬(bubble sort)

두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법.

첫번째 데이터부터 마지막 데이터까지 훑으면서 작은 값은 작은 값대로 큰 값은 큰 값대로 단 두개의 요소를 1대1로 교체해가면서 정렬하는 방식을 말한다.

 

즉 리스트 안에 있는 두 개의 인접한 수를 비교해서 순서에 맞지 않는다면 교환해주고 이를 계속 반복하는 방식.

 

예를 든다면 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 5

int main(void){ //해당 함수는 주어진 값을 최소값부터 차례대로 정렬하는 버블정렬방식이다.
  int temp = 0; //임시로 다른 변수의 값을 담을 변수
  int i = 0;
  int j = 0;

  int num[SIZE]={3,1,4,3,2}; // 총 5개의 숫자가 담긴 배열 num

  for (i=0; i < SIZE; i++){
  // 최대 5번의 정렬이 이뤄진다.
    for (j = 0; j < SIZE-1; j++){
    // j의 경우 1번 정렬이 이뤄질때마다 인덱스 넘버 0~3까지만 대입하게 된다.
    // 왜냐하면 아래 있는 if문에서 j+1이란 항목이 있어서 1~4까지 대입하게 되면
    // 존재하지 않은 num[5]라는 부분때문에 n-1을 해서 인덱스 넘버 1~3까지만 대입해주면 된다.
    if (num[j] > num[j+1]){ //만약 j번째 항이 j+1번째 항보다 클 경우
      temp = num[j+1]; // 임시 변수에 j보다 작은 j+1의 값을 저장한다.
      num[j+1] = num[j]; // j+1값에는 j+1보다 컸던 j의 값을 대입한다.
      num[j] = temp; // j에는 원래 j의 값보다 작았던 j+1의 값을 가진 temp를 대입해준다.
    }
    }
  }
  printf("%3d", num[0]);
  printf("%3d", num[1]);
  printf("%3d", num[2]);
  printf("%3d", num[3]);
  printf("%3d", num[4]);
  }

 

즉 n번째 항이 n+1항보다 작으면 그대로, n+1항이 n번째 항보다 작으면 둘의 위치를 바꾸는 작업을 계속해서 숫자를 순서대로 정렬하는 방식이다.

 

버블 정렬은 수행 한번에 모든 원소가 정렬되진 않는다.

그래서 여러번 정렬을 해줘야 한다.

 

버블 정렬은 비효율적인 경우가 많아서 버블 정렬을 한 후 탐색을 할 경우 오히려 손해가 나는 경우가 있다.

그래서 정렬은 보통 장기적인 관점에서 탐색을 여러번 해야할 때 이득이 된다.