선택 정렬 & 삽입 정렬

정렬 알고리즘을 처음 공부할 때 가장 자주 등장하는 두 가지 방식이 있다. 바로 선택 정렬과 삽입 정렬이다. 둘 다 구조가 단순하고 구현이 쉬워서 입문 단계에서 자주 사용되지만, 내부에서 어떻게 동작하는지 조금만 이해해두면 정렬 알고리즘의 기본적인 사고방식이 자연스럽게 잡힌다.

선택 정렬은 이름 그대로 “선택하는 정렬”이다. 매 단계마다 남아 있는 값 중 가장 작은 값을 선택해서 앞으로 가져오는 방식으로 작동한다. 예를 들어, 배열이 [7, 5, 3, 1]이라고 하면, 먼저 전체에서 가장 작은 값 1을 찾고, 이를 맨 앞과 교환한다. 그다음엔 두 번째 위치부터 끝까지 중에서 가장 작은 값을 선택해 자리를 바꾼다. 이런 식으로 각 위치마다 ‘제 자리에 올 값 하나’를 선택해 나가는 구조이기 때문에, 전체 비교 횟수는 항상 일정하게 많다. 첫 번째 위치를 채우기 위해 n개를 비교하고, 두 번째 위치를 채우기 위해 n-1개를 비교하며, 이런 과정이 끝까지 반복된다. 총 비교 횟수는 n(n-1)/2가 되고, 시간 복잡도는 O(n²)으로 표현한다. 배열의 상태와 상관없이 항상 전체를 훑어 최소값을 찾아야 하기 때문에, 최선·최악·평균 모두 O(n²)이다. 구조는 단순하지만 효율성은 떨어지는 정렬 방식이다.

삽입 정렬은 선택 정렬과는 사고방식이 다르다. 새로운 데이터를 받아들일 때 우리가 자연스럽게 정렬하는 방식과 매우 닮아 있다. 예를 들어 손에 든 카드를 정렬한다고 생각해보자. 새로운 카드를 뽑으면 기존에 들고 있는 카드들을 왼쪽부터 훑어가며 알맞은 위치에 끼워 넣는다. 삽입 정렬도 똑같다. 배열에서 두 번째 요소부터 시작해, 앞쪽 부분이 이미 정렬되어 있다고 가정한 상태에서 현재 요소를 알맞은 위치에 끼워 넣는 방식으로 진행된다. 값이 제자리를 찾을 때까지 앞 요소들과 비교하며 왼쪽으로 이동하고, 위치를 찾으면 삽입하고 다음 요소로 넘어간다. 배열이 이미 어느 정도 정렬되어 있다면 이동할 횟수가 적어 매우 빠르게 끝난다.

이 특성 때문에 삽입 정렬의 시간 복잡도는 상황에 따라 달라진다. 최악의 경우(배열이 완전히 역순일 때)는 매 번 왼쪽 끝까지 이동해야 하므로 O(n²)의 시간 복잡도를 가진다. 하지만 최선의 경우(이미 정렬된 배열)는 비교만 한 번 하고 바로 넘어가므로 O(n)에 가까운 성능이 나온다. 즉, 선택 정렬은 모든 경우가 O(n²)이지만, 삽입 정렬은 데이터 상태에 따라 성능이 크게 달라진다는 차이가 있다.

두 알고리즘 모두 안정 정렬 여부를 따져보는 것도 중요하다. 선택 정렬은 최소값을 선택해 뒤와 교환하는 구조라 같은 값을 가진 요소들의 상대적 순서가 깨질 수 있어 불안정 정렬이다. 반면 삽입 정렬은 왼쪽으로 이동하며 자신보다 큰 값만 밀어내는 방식이라 동일한 값을 유지한 채 위치를 찾기 때문에 안정 정렬이다.

정리하자면, 선택 정렬은 “남은 값 중 최소값을 찾아 앞으로 보내는 방식”이고, 삽입 정렬은 “앞부분을 정렬된 상태로 유지하며 새로운 값을 적절한 위치에 끼워 넣는 방식”이다. 선택 정렬은 정렬 상태와 상관없이 항상 O(n²)이라는 단순한 구조를 가지고 있고, 삽입 정렬은 데이터가 정렬되어 있을수록 빠르게 끝난다는 장점을 가진다. 두 알고리즘 모두 실무에서 직접 활용되는 경우는 거의 없지만, 정렬의 기본 사고를 배우고 알고리즘의 시간 복잡도를 이해하는 데 매우 중요한 기반이 된다.