알고리즘 - 정렬 기초 - 버블정렬(Bubble sort)

 정렬 알고리즘의 가장 기본

순차적으로 들어가 있는 데이터들을 담는 다양한 자료구조에서 담겨 있는 데이터들을 사용자에 의도에 따라 정렬을 하는 것은 어떻게 보면 효율적으로 데이터를 운영하는 데에 있어 필수적입니다. 본 포스트에서는 정렬을 구현하기 위한 가장 기본적인 개념인 버블 정렬 또는 거품 정렬이라 부르는 알고리즘을 공부해 보도록 하겠습니다.

 

Swap을 조건을 걸어 연속적으로 한다면 그것이 버블정렬 

알고리즘 - Swap

컴퓨터에서 어떠한 데이터 구조에 정렬을 구현한다는 것은 마냥 단순하지는 않습니다. 

본 포스트에서 설명하는 버블정렬은 가장 기초적이면서 단순한 개념으로 정렬을 하는 구조입니다.  그리고 그 기초가 되는 개념에는 Swap 알고리즘이 담겨 있다고 생각해도 됩니다. 

 

 

버블 정렬의 개념을 알아보자

그렇다면 무작위로 작성된 다음과 같은 데이터의 집합이 있다고 가정해 봅시다.

버블 정렬을 하는 순서는 다음과 같습니다.

• 데이터 집합의 첫 번째 요소와 두 번째 요소를 비교한다
• 대소 관계에 따라 위치를 바꾼다
• 데이터 집합의 마지막까지 반복한다
• 마지막까지 반복했으면 가장 마지막 요소를 제외하고 다시 위의 내용을 반복한다.

내용만을 보면 단순하지만 간단한 반복이 이루어집니다. 실제 개념을 하나씩 한번 해보도록 하겠습니다.

가장 작은 순으로 숫자를 정렬하는 버블정렬의 개념을 서술해 보도록 하겠습니다.

 

• 첫 번째와 두 번째 요소의 비교
  • 5와 2를 비교하여 대소 관계에 따라 위치를 변환

• 데이터의 마지막까지 반복

• 가장 마지막 요소를 제외하고 다시 반복

결국 최종적으로 반복하다 하여 모두 순환하게 되면 최종적으로 정렬된 결과 값을 얻을 수 있습니다.

버블 정렬의 단점 / 한계

위의 개념을 다양한 프로그래밍 언어로 구현을 하려면 난이도가 엄청나게 높지는 않습니다. 비교적 간단하게 구현이 가능하기도 합니다. 하지만 위의 과정을 보면 느낄 수 있듯이 상당히 비 효율적인 연산과정이 많이 포함된다는 것을 느낄 수 있을 것입니다. 만약 데이터의 집합의 규모가 많으면 많을수록 비효율적인 연산과정이 많을 것으로 예상할 수 있을 것입니다. 이런 불필요한 계산과정이 늘어난다는 의미는, 기능은 수행이 가능하나 성능면에서는 좋지 않다 또는 정렬 시간이 오래걸린다 라는 말이 될 수도 있습니다. 만약 정렬 알고리즘의 개념을 처음 접했다면, 와닿지 않을 수 있습니다. 앞으로 다양한 정렬 기법들을 알아보며 비교해보도록 하겠습니다.