[반도체 인명사전] 세계 최고의 정렬 알고리즘, 퀵 정렬의 개발자, 찰스 앤터니 리처드 호어

컴퓨터 상에서는 무수히 많은 데이터들을 빠르게 취합하고 필요에 맞게 정렬하여 좀 더 신속하게 원하는 작업을 수행할 수 있도록 하는 것이 관건일 텐데요. 정렬이란 컴퓨터의 기억공간 내 순서 없이 배열된 자료들 중에서 레코드의 특정 항목을 순서화하려는 기준에 따라 오름차순 내지는 내림차순으로 자료들을 재배치하는 것을 말합니다. 이러한 정렬 과정에서 정확도 못지않게 중요한 것이 바로 ‘속도’인데요. 오늘 만나볼 찰스 앤터니 리처드 호어는 정렬에 ‘퀵’을 붙여 데이터를 분류하는 데 가장 빠른 속도를 부여한 업적으로 튜링상을 수상하기도 했답니다. 과연 그는 어떠한 인물이고 그가 개발해낸 ‘퀵 정렬’이란 어떠한 것인지 함께 알아보도록 해요!

찰스 앤터니 리처드 호어는 1934년 1월 11일 스리랑카의 콜롬보에서 영국인 부모 사이에 태어난 컴퓨터 과학자입니다. 애칭인 토니 호어로도 많이 불리는데요. 현재 가장 널리 쓰이는 정렬 알고리즘의 하나인 퀵 정렬을 고안해낸 것으로 유명합니다.

토니 호어는 일찍부터 컴퓨팅에 관심을 갖기 시작했다고 알려져 있습니다. 15세 때 옥스포드 대학에서 존 루카스의 지도 아래 철학을 공부했을 때(라틴어와 그리스어와 함께)부터 그는 뚜렷한 확실성에 의한 해설과 같은 수학적 논리에 매력을 느꼈는데요. 1956년 옥스포드 대학에서 고전문학 학사를 취득한 이후 군 복무 동안(1956~ 1958) 영국 해군에서 러시아어를 공부했습니다. 그 후 그는 통계학을 배워 러시아에서 자연언어의 기계번역에 관한 연구를 시작했죠. 이와 동시에 레슬리 폭스(영국의 수학자)로부터 프로그래밍 과정을 이수하기도 했습니다.

                                                                                       ▲ 찰스 앤터니 리처드 호어

1959년 모스크바 주립대학에서 기계 번역어를 공부하던 그는 사전에서 효과적으로 단어를 찾는 것을 돕기 위해 퀵 정렬 알고리즘을 개발해내기에 이릅니다. 다음해인 1960년 영국으로 돌아간 그는 1960년 ‘엘리엇 브러더즈’라는 작은 컴퓨터 회사에 취직하여 ALGOL60 프로그램 개발 및 각종 알고리즘 개발에 본격적으로 착수하게 되는데요. 알고 60 프로그래밍 언어를 위한 상업적 컴파일러 팀을 이끌었습니다. 이는 비록 10진법 기계 코드를 사용한 실행이었지만, 컴파일러에 대한 설계 언어인 알고 그 자체를 이용하는 데는 성공한 프로젝트였죠.

이러한 경험을 바탕으로 그는 1968년에는 퀸즈 대학 벨파스트 분교의 컴퓨터 과학 교수로 제직하며 컴퓨터 프로그래밍의 정확성을 증명한 연속 논문을 출간했고 교육 연구소를 설립하기도 했습니다. 그리고 1977년에는 옥스포드 대학으로 돌아와 프로그래밍 연구소를 맡아 컴퓨터 시스템 발전과 디자인, 정확한 명세를 위한 아이디어를 추구해나가기 시작했는데요. 덕분에 그 유명한 결과물인 명세언어와 CSP 병행 프로그래밍 모델을 만들게 됩니다.

다양한 컴퓨터 프로그래밍의 기초를 마련한 토니 호어. 그 중 가장 널리, 그리고 가장 효율적으로 쓰이고 있는 것이 바로 퀵 정렬인데요. 그렇다면 이 퀵 정렬이란 무엇인지, 그 개념과 원리를 함께 알아보도록 합시다!

찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘인 퀵 정렬(Quick Sort)은 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법입니다. 다른 데이터와의 비교만으로 정렬을 수행하는 비교 정렬에 속하는데요. 그 과정을 간단히 살펴보면 다음과 같습니다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있게 됩니다.

퀵 정렬은 이름에서도 알 수 있듯이 매우 빠른 수행속도를 가지는데요. 일반적으로 기준은 첫 번째 데이터로 선택하고 결과적으로 기준의 왼쪽에는 작은 데이터가, 오른쪽에는 큰 데이터가 위치하게 됩니다.

다음은 이러한 동작을 C언어 함수로 나타낸 것인데요. 24, 25행에서 재귀 호출(임의의 함수가 자신을 호출하는 것)이 수행되는 것을 확인할 수 있습니다.

                                                                 출처 : 네이버 지식백과 (http://terms.naver.com/)

여기에서 left와 right는 정렬해야 하는 데이터들의 위치를 나타내는 배열첨자로, left는 시작 위치를, right는 마지막 위치를 의미합니다. 그리고 key는 기준키를 나타냅니다. 이렇듯 기발한 발상에 간단한 원리까지 갖추고 있는 퀵 정렬은 현재 가장 유용하게 쓰이고 있는 알고리즘으로 자리잡고 있습니다.