[쉽게 배우는 알고리즘] 1.정렬 알고리즘
목차
1. 정렬이란 무엇인가?
2. 인접한 원소를 비교하는 방법
3. 인접하지 않은 원소를 비교하는 방법
4. 비교를 하지 않는 방법
1. 정렬이란 무엇인가?
당신은 (주)아무것도 아닌 회사(Nothing.Inc)에 인턴으로 지원하여 합격하여 오늘부터 근무하게 되었다.
당신에게 주어진 업무는 다음과 같다.
Nothing.Inc 의 회원 100명의 데이터가 주어졌을 때, 키가 가장 큰 회원을 골라내어 보고서에 작성하시오.
100명 중 키가 가장 큰 회원을 고르는 방법에 대해 생각해봅시다.
우선, 책상 위에 100명의 신상 정보를 담은 종이가 주어질 것이고, 100장을 모두 확인하여 키가 가장 큰 회원을 추려낼 수 있겠죠.
응? 그냥 한 눈에 보면 해결되잖아요!
그런가요? 그렇다면 회원의 데이터가 1만개가 주어진다면 어떤가요? 음.. 한눈에 해결하긴 어려워 보입니다.
추가로 2번째로 키가 큰 회원, 3번째로 키가 큰 회원 등 업무가 주어질 때마다 100명 분의 데이터를 모두 확인해야한다는 번거로움이 있습니다.
그 때, 정렬을 사용하면 효과적으로 일을 할 수 있을겁니다. 야호!
진행하기에 앞서 용어를 정리하고 갑시다.
- 원소: 주어진 데이터 중 한 개를 의미함.
- 탐색: 주어진 데이터에서 특정 원소를 찾는 행위, 그 기준은 위치가 될 수도 있고 값이 될 수도 있다.
- 정렬: 주어진 데이터를 특정한 기준에 맞춰 정렬하는 것. (오름차순 내림차순 등)
쉽게 말해 원소는 데이터 하나 하나를 가리키는 단어이고, 탐색은 데이터 중 원소를 찾는 행위이며, 정렬은 원소들을 기준에 맞춰 나열하는 행위라고 할 수 있습니다.
데이터에서 탐색을 여러번 하는 경우, 어쩌면 모든 값을 정렬하는것이 유리할 때가 많습니다.
위에서 예시를 든 것처럼 2번째로 키가 큰 회원, 3번째로 키가 큰 회원을 추가로 찾아야한다면 모든 값을 내림차순으로 정렬한 뒤, 첫 번째 회원, 두 번째 회원, 세 번째 회원을 보고서에 작성하면 되겠죠!
이렇듯, 정렬 알고리즘은 현실 속 문제를 풀어낼 때 아주 많이 사용되는 알고리즘으로 나올 수 있는 알고리즘이란 알고리즘은 다 나온 상황이라고 알려져 있습니다. 그러니 저희는 그것들을 배우고, 각각의 특징들을 익힌 뒤, 적재적소에 사용하면 됩니다.
그렇다면 정렬은 실질적으로 어떻게 진행될까요? 정렬을 하기 위해선 원소의 등수를 매겨야함이 불가피합니다. 그리고 등수를 매기려면 비교과정이 불가피합니다. 즉, 정렬을 진행할 때 비교를 어떻게 하는가에 따라 알고리즘이 결정된다고 생각하면 됩니다. 이해가 잘 되지 않는다면 바로 아래를 살펴봅시다.
2. 인접한 원소를 비교하는 방법
인접한 원소를 비교하는 방법은 일반적으로 쉽게 떠올릴 수 있는 아이디어입니다.
5명의 키(cm) 데이터는 다음과 같습니다. 이를 오름차순 정렬하시오.
190 180 160 170 200
우선, 위 문제를 풀기 위해 맨 앞 원소(190)와 그 뒤 원소(180)을 비교해야 합니다. 180이 더 작은 원소이기 때문에, 190과 180의 위치를 바꿉니다. 이후 190과 160을 다시 비교하여 위치를 재조정합니다. 이런식으로 정렬을 하는 것이 "인접한 원소끼리 비교하는 정렬"입니다. 대표적으로 2가지 알고리즘이 존재합니다.
- 버블 정렬(Bubble Sort)
- 삽입 정렬(Insertion Sort)
인접한 원소끼리 비교하는 정렬은 한계가 명확합니다. 바로, 시간 복잡도가 $ O(n^2) $이라는 점입니다.
구현은 매우 간단하나, 시간 복잡도가 $ O(n^2) $이라는 점 때문에 많이 사용하지 않는 알고리즘입니다.
3. 인접하지 않은 원소를 비교하는 방법
인접하지 않은 원소를 비교하는 알고리즘은 가까이 붙은 원소끼리만 비교하는 것이 아닌 멀리 있는 원소도 비교하는 알고리즘입니다. 그에 대한 대표적인 알고리즘은 다음과 같습니다.
- 퀵 정렬(Quick Sort)
- 힙 정렬(Heap Sort)
- 병합 정렬(Merge Sort)
인접하지 않은 원소를 비교하는 알고리즘은 인접한 원소를 비교하는 알고리즘보다 훨씬 빠르다는 장점이 있습니다.
시간 복잡도가 $ O(nlogn) $ 이기 때문에 가장 많이 사용되는 알고리즘들이며, 대다수의 프로그래밍 언어에 내장된 정렬 함수는 퀵 정렬(혹은 퀵 정렬을 변형한 알고리즘)로 구현되어 있다고 알려져있습니다.
4. 비교를 하지 않는 방법
정렬 알고리즘 중에는 비교를 하지 않는 방법이 존재합니다.
위에서는 분명 비교가 불가피하다고 했잖아요! 사기꾼!
맞습니다. 제가 사기꾼이라는 게 맞다는게 아닌, 무언가의 등수를 매기는 과정에서 비교는 불가피한게 맞습니다. 그러나, 특정 조건을 만족하는 데이터들이라면 비교를 하지 않고도 정렬을 하는 것이 가능합니다. 지금 장황하게 설명하면 머리가 지끈지끈해질 테니 어떤 알고리즘이 그에 해당하는지만 알아보겠습니다.
- 버킷 정렬(Bucket Sort)
- 기수 정렬(Radix Sort)
- 계수 정렬(Counting Sort)
비교를 하지 않는 정렬 알고리즘은 데이터가 특정 조건을 만족할 때 매우 빠른 속도로 정렬하는 알고리즘입니다.
데이터가 조건을 만족할 땐 $O(n)$ 시간 내에 해결하는 경우도 존재하기 때문에 알아두면 좋습니다. 비교를 하지 않는 알고리즘이 사용되는 대표적인 문제가 바로 "수능 점수 정렬하기" 입니다. 자세한 조건들과 시간 복잡도는 추후에 다루도록 하겠습니다.
이렇게 정렬 알고리즘에 대한 간략한 개요가 끝났습니다.
정렬 알고리즘을 공부하다 보면(사실 모든 컴퓨터 과학 공부를 하다보면), 이런 생각이 꾸준히 듭니다.(제가 그랬으니까요)
이런 기가막힌 알고리즘을 생각한 사람도 있는데, 나는 이해조차 못하는군, 뭐하는거지? 에잇! 때려쳐야겠다!
이런 비관적인 사고 방식을 갖기 시작하면, 그 어느 분야에서도 대성은 커녕 일반적인 활동이 불가능할 것입니다.
(이미 존재하는 무수히 많은 레시피를 보며) 에잇! 요리사는 때려쳐야겠다!
(아인슈타인의 특수 상대성 이론을 보며) 에잇! 물리학은 때려쳐야겠다!
(미국의 빅테크 기업을 보며) 에잇! 어차피 사업을 해도 내 기업보다 큰 기업이 많으니 때려쳐야겠다!
인간의 문명은 종이와 펜이 발명되고 나서부터 가파르게 성장했다고 합니다. 역사의 흐름 속에 살아가는 우리는 새로운 도구를 만드는 것도 좋지만, 선조가 만들어놓은 도구들과 이론들을 가지고 당장의 문제를 해결하는 것 또한 의미가 있다고 생각합니다.
다음 포스팅부터 정렬 알고리즘을 하나하나 뜯어볼 예정입니다. 공부를 하며 위와 같은 비관적인 사고를 갖지 않도록 "옛날에 어떤 천재들이 만든 알고리즘"을 구경한다고 생각하며 따라와주세요!