드디어 알고리듬에 관심이 생긴 견우에게 정렬 알고리듬을 알려줄 수 있나 했더니 방해꾼이 나타났네요. 그럼 견우를 기다리는 동안 우리끼리 먼저 얘기하고 있을까요?
여러분, 오늘은 시험을 쳐야 해요. 다들 자리에 앉아주세요. 시험은 저 알디를 누가 가장 잘 아는지 알아보기 위한 거예요. 알디의 성장기, 알디가 좋아하는 것과 싫어하는 것… 등등 과목은 10개! 시험 쳐야 할 대상은 전국의 중학생이에요. 시험에서 좋은 성적을 거둔 친구들을 모아 팬사인회를 열 거예요! 그런데 이 많은 학생의 성적 데이터를 어떻게 한눈에 보고 우수한 성적을 찾아낼까요?
이처럼 엄청나게 많은 정보를 다룰 때, 데이터를 분석하기 쉽게 정리하는 것을 ‘정렬’이라고 해요. 정렬 알고리듬은 가장 오래 연구된 알고리듬 분야 중 하나로, 다른 알고리듬의 기본이 되므로 꼭 알아두는 게 좋아요. 폴더에서 파일을 정리할 때 최근에 저장한 파일순이나 이름순으로 나열하는 것도 정렬 알고리듬을 활용한 예랍니다. 평소에는 버튼 하나만 누르면 간단하게 되니 어떤 과정을 통해서 정렬되는 건지 생각해 본 적은 없을 거예요. 간단해 보여서 정렬만큼은 알고리듬의 도움 같은 건 필요 없겠다고 생각했을지도 모르겠고요.
하지만 ‘알디 알기 시험’처럼 전국 중학생의 성적이 모여 있는 상황이라면 폴더 속 사진처럼 쉽게 정렬할 수 없을 거예요. 수십만 개의 자료를 한눈에 보고 비교하긴 어려울 테니까요. 이때 정렬 알고리듬을 사용하면 체계적으로 정보를 정리할 수 있어요. 이 아이디어를 컴퓨터가 반복하게 하면 가만히 앉아서 결과를 얻을 수도 있고요.
역사가 깊은 분야인 만큼 정렬 알고리듬에는 매우 다양한 종류가 있어요. 오늘은 그중에서도 가장 쉽고 기본적인 ‘거품 정렬 알고리듬’을 소개할게요. 거품 정렬은 오른쪽에서부터 왼쪽으로 두 개씩 숫자를 비교해서 교환하는 알고리듬인데, 위아래로 나열한 데이터를 정렬할 때 작은 수가 마치 거품처럼 위로 올라온다고 해서 거품 정렬이라는 이름이 붙었답니다. 원래 교환해서 정렬하는 방법은 훨씬 오래전부터 쓰였지만, 거품이라는 재미난 이름이 처음으로 문헌에 등장한 건 1962년 캐나다 전산학자인 케네스 아이버슨의 논문에서였어요. 아이버슨은 컴퓨터과학 분야에 중요한 업적을 남긴 사람에게 수여하는 ‘튜링상’을 받은 학자이기도 해요. 논리력은 물론 이름 짓는 센스까지 남달랐던 것 같네요. 그럼 보글보글 거품 정렬, 시작해볼까요?
참고자료
Jwen Astrachan ‘Bubble Sort: An Archaeological Algorithmic Analysis’, 이시다 모리테루, 미야자키 쇼이치 ‘알고리즘 도감’
