[알고리즘-2] 버블정렬

안녕하세요 기린입니다 :)

오늘은 지난 시간에 이어서 버블 정렬에 대해 알아볼텐데요

자 버블정렬이란 일련의 숫자들을 오름차순으로 정렬하는것 인데요

 

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.
1 10 5 8 7 6 4 3 2 9

 

버블정렬 또한 선택정렬과 같이 몹시 직관적인 해결 방법입니다

바로 가까이에 있는 두 숫자끼리 비교해서 더 작은 숫자를 앞으로 보내주는 것을 반복 하는 겁니다

다시 말해 버블정렬이란 옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법인데요

정렬 알고리즘 중에서 구현은 가장 쉽지만 가장 비효율적인 알고리즘입니다

 

#include <stdio.h>

int main(void) {
  int i, j, temp;
  int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; 
  for(i = 0; i < 10; i++) { 
    for(j = 0; j < 9 - i; j++) { 
      if(array[j] > array[j + 1]) { 
       	  temp = array[j]; 
          array[j] = array[j + 1];
          array[j + 1] = temp;
      } 
    } 
  } 
  for(i = 0; i < 10; i++) { 
    printf("%d ", array[i]); 
  } 
  return 0;
}

소스 코드를 보시면 단순히 반복적으로 두 숫자를 비교하여 앞으로 보냅니다. 이 과정에서 각 싸이클마다 가장 큰 값이 맨 뒤로 보내지게 됩니다. 컴퓨터 내부적인 연산이 가장 비효율적으로 일어나게 되어 실제 수행시간이 가장 느린 안 좋은 알고리즘이라고 할 수 있습니다. 시간 복잡도는 선택 정렬과 동일합니다.

버블 정렬의 시간 복잡도는 O(N^2) 입니다.

이해가 되시나요 ?? 

다음 시간에는 삽입 정렬에 대해 알아보겠습니다

자 그럼 즐거운 코딩하세요 !

 

문의: ralla0405@gmail.com