정렬 알고리즘 (Sorting Algorithm)
쉽게 풀면
시험이 끝난 뒤 답안지 100장을 점수 순으로 쌓아야 한다고 해봅시다. 한 장씩 뽑아서 이미 쌓인 더미 어디쯤에 끼워 넣을지 비교해가며 정리할 수도 있고, 더미를 반으로 나눈 뒤 각각 정리하고 나중에 합칠 수도 있습니다. 이렇게 "무엇을, 어떤 순서로 비교하고 옮길 것인가"에 대한 구체적인 방법이 바로 정렬 알고리즘입니다. 대표적으로 이웃한 두 값을 계속 비교해 바꾸는 버블 정렬, 기준값을 잡아 나누어 정복하는 퀵 정렬, 정렬된 두 묶음을 합치는 병합 정렬 등이 있으며, 방법에 따라 처리 속도(시간복잡도)가 크게 달라집니다.
왜 중요한가
정렬은 탐색, 중복 제거, 최적화 문제 등 수많은 알고리즘의 전처리 단계로 쓰이기 때문에, 전체 시스템의 성능이 정렬 알고리즘의 효율에 크게 좌우됩니다. 데이터베이스 인덱싱, 대용량 로그 분석, 머신러닝 파이프라인의 데이터 전처리 등 실무 전반에서 반복적으로 등장하는 기본 연산이어서, 알고리즘 논문에서는 새로운 정렬 기법의 시간복잡도나 안정성을 개선하는 연구도 꾸준히 이루어집니다.
논문에서는 이렇게 쓰입니다
이 문장은 데이터를 다루기 쉬운 순서로 미리 정리해두는 전처리 과정에서, 여러 정렬 알고리즘 중 상황에 맞는 방식을 골라 사용했다는 뜻입니다. 컴퓨터교육이나 알고리즘 관련 논문에서는 이처럼 기본 개념을 배경지식으로 언급한 뒤 본 주제로 넘어가는 경우가 많습니다.
메모리가 제한된 환경에서는 속도뿐 아니라 추가 공간을 얼마나 쓰는지도 정렬 알고리즘 선택의 중요한 기준이 된다는 뜻입니다.
조금 더 깊게 보면
정렬 알고리즘을 평가할 때는 평균/최선/최악 시간복잡도뿐 아니라, 같은 값을 가진 원소들의 원래 순서를 유지하는지를 뜻하는 안정성(stability), 그리고 추가 메모리를 거의 쓰지 않는 제자리 정렬 여부도 함께 고려됩니다. 실제 시스템에서는 데이터 크기나 분포에 따라 여러 알고리즘을 섞어 쓰는 하이브리드 방식(예: 팀소트)이 표준 라이브러리에 채택되기도 합니다.
주의할 점
정렬 알고리즘은 종류에 따라 처리 속도가 크게 다르며, "정렬만 되면 다 똑같다"고 생각하면 안 됩니다. 또한 데이터가 이미 정렬되어 있어야만 효율적으로 값을 찾을 수 있는 탐색 알고리즘(이진 탐색 등)도 있으므로, 정렬과 탐색은 서로 짝을 이루는 개념으로 함께 이해하는 것이 좋습니다.