정렬 알고리즘1. 버블 정렬(Bubble Sort)

안녕하세요!

 

오늘 포스팅 할 내용은 정렬 알고리즘의 하나인 '버블 정렬(Bubble Sort)'입니다.

데이터들은 여러 가지 방법으로 정렬되어 오름차순 혹은 내림차순 등으로 순서가 정해지는데요.

 

사실 정렬하는 방법에도 여러가지가 있다는 것을 알고 계셨나요?

 

실제로 컴퓨터가 내부에서 데이터를 정렬할 때,

어떤 정렬 방식을 쓰느냐에 따라서 시간의 효율성이 좌우됩니다.

물론 사람도 금방 할 수 있는 작은 양의 데이터라면 큰 차이는 없겠지만요.

 

그러나 방대한 양의 데이터를 다룰 때는, 그 효율성이 어마어마하게 달라지겠죠?

 

그럼 총 5가지로 구분하는 정렬 알고리즘, 그 중에서도 버블 정렬에 대해 알아보겠습니다.

---

1. 시간 효율성

먼저 시간 효율성에 대해서 알고 가겠습니다.

 

시간 효율성이란 '알고리즘을 실행하여 종료하기까지 걸리는 시간의 효율성'을 의미합니다.

 

세부적으로는 알고리즘을 컴퓨터가 이해할 수 있는 기계 코드로 번역하는 '번역 시간',

몇 개의 기계어들이 필요한지를 계산하는 '실행 시간'으로 구분하는데요.

 

일반적으로 시간 효율성을 표시하는 방법으로 다음과 같이 '빅오(Big O) 표시법'을 사용합니다.

(표를 참고하세요!)

시간 효율성은 정렬 알고리즘을 어떤 것을 사용하는가에 따라, 혹은 정렬하고자 하는 데이터가 어떤 순서로 있느냐에 따라 당연히 차이가 날 수밖에 없겠죠.

 

아직 5가지의 정렬 방식을 세부적으로 언급하지는 않았지만, 각각의 시간 효율성을 비교하면 다음과 같습니다. 여기서 최선의 경우가 제일 빠른 시간 내에 끝나는 경우, 최악의 경우가 가장 늦게 끝나는 경우이며, 모든 경우의 평균치가 평균에 해당합니다.

결과적으로 최선의 경우, 평균, 최악의 경우를 모두 고려하면 병합 정렬이 가장 효율적이라고 볼 수 있겠네요.

 

2. 버블 정렬(Bubble Sort)의 정의와 예제

사족이 길었습니다. 본론으로 들어가서 '버블 정렬'에 대해 알아보겠습니다.

직역하면 거품 정렬인데, 시간 효율성은 기타 정렬 방식에 비해 높다고는 할 수 없습니다.

하지만 정렬하는 방식이 단순하여 직관적으로 이해하기 편합니다.

 

원리는 다음과 같습니다.

1. 인접한 두 값을 비교하여 대소 관계를 따지고, 보다 큰 값을 뒤로 보낸다.

2. (첫 번째, 두 번째), (두 번째, 세 번째), ...... 와 같이 인덱스를 1씩 뒤로 옮겨가며 값을 비교한다.

3. n번째 비교했을 때 가장 큰 값은 (요소의 길이 - n)의 자리로 밀려나게 된다.

 

예를 들어, 다음과 같은 인수를 요소로 갖는 배열이 있다고 가정하겠습니다.

그럼 1번 인덱스부터 차례차례 비교해보도록 하겠습니다.

98과 35중에 더 큰 값은 98이므로 자리를 바꾸도록 하겠습니다.

이제는 98과 46을 비교하겠습니다.

이번에도 98이 46보다 더 크므로 뒤로 옮기겠습니다.

이런 방식으로 가장 큰 값이 뒤로 밀려날 때까지 정렬합니다.

 

98과 53...

98과 24...

이렇게 1회전을 한 결과, 98이 가장 큰 값으로 선정되어 맨 뒷자리에 자리하게 되었습니다.

이제는 완전히 오름차순으로 정렬할 때까지 35부터 과정을 반복해 나가는 것이 바로 버블 정렬입니다.

한 번만 해도 힘들다구요?ㅎㅎ

그럼 굳이 우리가 하지 않아도 컴퓨터가 알아서 해줄 수 있도록, C++로 구현해보도록 하겠습니다.

3. C++로 버블정렬 구현하기

먼저 정렬할 배열을 하나 선언하여, 값을 넣어주겠습니다.

그리고 배열의 크기가 얼마인지 구해주는 size변수도 하나 선언하여, 크기를 넣어주겠습니다.

그 다음에는, 회전 결과에 따라 배열이 어떻게 정렬되어 가는지 보여주기 위한 변수 l도 선언합니다.

그리고 총 2개의 루프로 반복을 돌리겠습니다.

 

변수 i는 회전의 횟수를 나타내는 지역 변수가 되며,

버블 정렬의 경우 '배열 인수의 개수 - 1'회만큼 회전해야 합니다.

 

j는 배열 내 인수들의 비교 작업을 위한 변수입니다.

각 인수들은 j라는 인덱스를 갖고 비교하는데, 비교 대상은 인덱스가 j+1인 인수입니다.

 

만약, 인수 j가 j+1보다 값이 크게 되면 서로 자리를 바꿔줘야 하므로,

임의의 인수 temp를 선언하여 서로 값을 맞바꿔주는 알고리즘을 구현하면 되겠습니다.

회전 결과는 매회 회전이 끝날 때마다 출력해주며,

앞서 선언한 변수 l이 제 역할을 할 수 있도록 "l회전 결과'라고 출력해줍니다.

 

그리고 l을 사용한 즉시 다음 회전 결과를 출력하기 위해 l을 1 증가시켜줍니다.

그리고 배열의 각 인수들을 ','로 구분하여 출력해줍니다.

 

실행 결과, 버블 정렬 알고리즘에서 n 회전한 결과들이 줄 단위로 나타납니다.

 

---

지금까지 시간 효율성과 버블 정렬의 정의, 원리 및 구현에 대해 알아보았습니다.

 

감사합니다!! : )