알고리즘 레포트 - 정렬 알고리즘의 효율이 주어진 데이터의 상태에 따라 어떻게 달라지는지 토론하시오.

I. 서론

알고리즘 수업에서 정렬 시간을 비교하는 실습을 할 때 이상한 장면을 본 적이 있다. 작은 배열에서는 어떤 방법을 써도 눈으로 차이점을 느끼기 어려웠는데 원소 수를 늘리자 순위가 크게 달라졌다. 더 재미있었던 것은 같은 크기의 배열이라도 이미 거의 정렬되어 있는지, 역순인지에 따라 실행 시간이 달라졌다는 점이다. 정렬 알고리즘의 효율을 빅오 표기 하나로 외우면 이런 차이가 잘 설명되지 않는다. 데이터 크기만큼이나 입력의 현재 상태와 알고리즘이 그 상태를 다루는 방식이 중요하다. 나는 좋은 정렬 알고리즘이 늘 하나로 정해져 있는 것이 아니라, 데이터가 얼마나 흐트러져 있고 같은 값이 얼마나 많으며 추가 메모리를 쓸 수 있는지까지 보고 고르는 문제라고 생각한다.

II. 본론

1) 거의 정렬된 배열에서 삽입 정렬이 빨라지는 이유

삽입 정렬은 배열의 앞부분을 정렬된 영역으로 유지하면서 새 원소가 들어갈 자리를 찾고 필요한 만큼 원소를 밀어내는 방식이다. 최악의 시간복잡도는 O(n^2)라서 원소가 많을 때 느린 알고리즘으로 분류된다. 그런데 이미 오름차순으로 정렬된 데이터라면 새 원소가 들어올 때마다 거의 움직일 필요가 없다. 앞 원소와 한 번 정도 비교하고 현재 자리에 두면 된다. 이때 수행량은 원소 수에 비례하는 수준까지 내려간다. 거의 정렬된 배열에서도 이동 거리가 짧기 때문에 실제 수행 시간이 크게 줄어든다. 삽입 정렬을 입력 상태에 적응하는 정렬이라고 부르는 이유가 여기에 있다.

수업 실습에서 출석번호 목록을 예로 들었을 때 이 특징이 바로 이해됐다. 이미 번호순으로 정리된 100명의 목록에 늦게 등록한 학생 몇 명을 끼워 넣는 상황이라면 전체 목록을 처음부터 다시 뒤섞어 정렬할 필요가 없다. 새 번호가 들어갈 위치 주변만 움직이면 된다. 데이터가 계속 조금씩 추가되고 기존 순서가 대체로 유지되는 시스템에서는 삽입 정렬의 약점으로 외웠던 O(n^2)가 실제 상황을 충분히 설명하지 못한다. 최악의 경우를 아는 것은 필요하지만 입력이 어떤 모습으로 들어오는지 모르면 계산량에 관한 판단이 반쪽이 된다.

반대로 내림차순으로 정리된 배열을 오름차순으로 바꾸려 하면 삽입 정렬은 매우 힘들어진다. 작은 원소가 들어올 때마다 앞에 있는 원소 대부분을 오른쪽으로 밀어야 하기 때문이다. 길이가 n인 배열에서 이런 이동이 계속 겹치면 비교와 이동 횟수가 대략 n의 제곱에 비례하게 된다. 같은 10만 개의 정수라도 거의 정렬된 배열과 역순 배열은 삽입 정렬에게 전혀 다른 문제다. 데이터 상태가 알고리즘 내부의 실제 작업량을 바꾸는 대표 사례다.

선택 정렬은 분위기가 다르다. 선택 정렬은 아직 정렬되지 않은 구간을 끝까지 훑어 최솟값을 찾고 그 값을 앞자리로 옮긴다. 배열이 이미 정렬되어 있어도 최솟값이 현재 자리에 있다는 사실을 확인하려면 남은 구간을 계속 조사해야 한다. 비교 횟수는 입력 순서와 크게 달라지지 않고 O(n^2)에 머문다. 이미 정돈된 데이터가 주는 이득을 거의 쓰지 못한다. 삽입 정렬과 선택 정렬이 같은 최악 시간복잡도를 가진다고 해서 실제 성질도 같다고 말하기 어려운 이유다.