정렬 알고리즘-버블 정렬

 정렬알고리즘(Sorting Algorithm)의 사용빈도는 상당히 높습니다. 컴퓨터는 사용자로부터 데이터를 받아오지만 받아온 데이터는 정렬이되지 않는 상태입니다. 입력받은 데이터를 정렬한다는 것은 작업의 활용도를 높일 수 있고, 원하는 데이터를 찾기위한 효율을 높입니다. 따라서 프로그래머는 프로그램을 만들때 사용자로 입력받은 데이러를 처리하여 '오름 차순' 또는 '내림 차순'으로 정리할 필요가 있습니다.

 데이터를 정렬하는 방법은 여러가지가 있습니다. 대표적인 정렬방법으로 버블정렬, 퀵정렬, 삽입 정렬, 선택정렬이 있는데 오늘은 그중에서 가장 활용빈도가 높은 '버블 정렬(Bubble Sort)'에 대해서 소개하려고 합니다.

◇ 정렬알고리즘 - 버블 정렬(Bubble Sort)

---

○ 정렬

- 정렬의 사전적 의미는 '데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배렬하는 일'을 의미합니다. 여기서 말하는 일정한 순서란 오름차순이 될수도 있고, 내림 차순이 될 수도 있습니다. 예를들어 학교에서 학생들을 키 순으로 세우는 것, 도서관에서 책을 제목 순서대로 정리하는 것등이 정렬이 될 수 있습니다.

---

○ 버블 정렬

- 버블 정렬(Bubble Sort)의 활용도는 매우 높습니다. 버블 정렬, 선택 정렬, 퀵 정렬등의 궁극적인 목표는 데이터를 일정한 순서로 정렬하는 것이고, 버블, 선택, 퀵등은 데이터를 정렬하기 위한 특정한 조건에 해당하는 것입니다. 버블 정렬의 활용도가 높은 이유중 하나는 바로 알고리즘을 구현하기가 쉽고, 많은 프로그래머들이 즐겨 쓰는 알고리즘이기 때문입니다.

- 버블정렬의 이름은 데이터를 일정한 순서로 정리하는 과정이  수중 거품의 움직임과 유사하여 붙혀진 이름으로 '거품 정렬'이라고도 부릅니다.

- 버블 정렬은 자신과 인접한 데이터와 비교하여 정렬하는 방식입니다. 위의 예를 보시면 우선적으로 사용자로부터 무작위로 84, 69, 76, 86, 94, 91의 데이터를 받아오게 됩니다. 이 후 루프를 이용하여 첫번째로 84와 69를 비교하여 84가 더 크다는 것을 확인하고 데이터의 위치를 바꾸었습니다. 또다시 84와 76을 비교하여 84가 더 큰것을 확인하고 위치를 바꾸고, 84와 86을 다시 비교하여 84가 작으므로 데이터의 위치를 바꾸지 않고 다음으로 넘어갑니다.

 이렇게 정렬을 하다가 더이상 위치 교환이 일어나지 않게 되면 루프를 빠져나오게 됩니다. 버블 정렬은 데이터 정렬의 정확도와 속도가 높습니다. 한번 반복을 할때마다 교환이 일어나는 범위가 하나씩 줄어들게되고, 만약 n개의 데이터를 받아온다면 n-1만큼 반복을 해야 정렬이 끝나게 됩니다.

---

 만약 버블정렬를 이용하여 1000개의 데이터를 정렬한다고면 총 999번의 반복이 이루어지며, 데이터간의 위치교환은 49,995,000번의 데이터 교환이 일어납니다. 따라서 버블정렬의 처리 속도는 많은 데이터가 입력될 수록 그 처리속도 또한 증가하게 되는 것입니다. 실제로 프로그램을 짜다보면 버블정렬의 사용빈도는 상당히 높기때문에 현재 배우는 언어와 상관없이 루프를 공부하고 있다면 반드시 정렬 알고리즘을 구현해보는 것이 옳다고 생각합니다.

[읽어볼만한 글]

2014/04/12 - C언어 정렬알고리즘-버블정렬(코드)

※공감은 블로거에게 큰힘이 됩니다.