0. Introduction
가장 기본이 되는 4가지 정렬 기법인 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해서 정리해 보았다.
이 정렬 기법들이 가장 좋다고 볼 순 없지만, 구현이 간단하거나 경우에 따라 가장 효율적이기 때문에 많이 쓰이는 방법들이다.
각각의 정렬 기법들은 이름을 보면 어떻게 동작하는지 힌트를 얻을 수 있다. 하나씩 자세히 살펴보자.
참고로 아래 예시는 작은 값부터 점차 큰 값으로 정렬하는 오름차순 정렬을 기준으로 설명하고 있다.
1. 선택 정렬 (Selection Sort)
1-1. 선택 정렬의 특징
선택 정렬은 리스트를 돌면서 가장 작은 요소를 선택하여 맨 앞으로 가져온다.
1-2. 선택 정렬 동작 과정
따라서 위 이미지를 보았을 때, Step 1 에서는 5번 인덱스(여섯번째 값)의 1을 0번 인덱스의 4와 교환(swap)한다.
Step2 에서는 0번 인덱스를 제외한 나머지 배열에서 가장 작은 값인 2(6번 인덱스)를 가져와 1번 인덱스의 7과 교환(swap)한다.
이런 과정을 반복하며 맨 마지막 인덱스까지 채워나간다.
1-3. 선택 정렬의 시간 복잡도 및 활용 방법
이중 반복문을 통해 최소값을 찾아 교환해나가는 방식으로 시간 복잡도는 최선/최악의 경우 모두 O(n^2)이다.
로직이 직관적이고 구현 난이도가 어렵지 않기 때문에 데이터가 크지 않고 시간이 충분한 경우 간단하게 활용하기 좋다.
2. 삽입 정렬 (Insertion Sort)
2-1. 삽입 정렬의 특징
삽입 정렬은 적절한 위치에 새로운 요소를 삽입하는 과정을 반복하며 리스트 정렬 상태를 만들어나가는 방식이다.
기준 인덱스를 기준으로 좌측은 정렬된 리스트라고 가정하고, 기준 인덱스를 우측으로 한 칸씩 이동하며 값을 적절한 위치에 삽입해준다.
2-2. 삽입 정렬의 동작 과정
위 이미지를 살펴보자.
0번 인덱스에 위치한 4의 경우엔 기존 정렬된 리스트가 없으므로 위치를 유지한다.
1번 인덱스의 7은 4보다 크기 때문에 이동하지 않고 본인의 위치를 유지한다.
2번 인덱스의 5의 경우에는, 좌측 정렬된 리스트([4, 7])에서 4보다 크고 7보다 작으므로 그 사이에 삽입된다.
3번 인덱스의 3의 경우에는, 좌측 정렬된 리스트([4, 5, 7])에서 가장 작으므로 맨 앞에 삽입하고 다른 값들은 한 칸씩 뒤로 이동한다.
2-3. 삽입 정렬의 시간 복잡도 및 활용 방법
정렬된 리스트를 역으로 돌면서 본인이 삽입될 위치를 찾고, 값이 삽입되기 위해 다른 값들을 한 칸씩 이동 시켜야 한다.
최악의 경우(역순으로 정렬된 경우)에는 앞 쪽의 원소를 모두 탐색하는 작업을 수행해야 하므로 0 + 1 + 2+ 3 + ... + n = n(n-1)으로, O(n^2)의 시간 복잡도를 갖는다.
그러나 최선의 경우(순서대로 정렬된 경우)에는 앞 쪽의 원소를 전혀 탐색하지 않아도 되므로 배열을 순회하는 O(n)으로 가능하다.
따라서 배열이 거의 정렬되어 있는 상태에서 일부 값이 추가되는 상황이라면 삽입 정렬이 유리할 수 있다.
3. 퀵 정렬 (Quick Sort)
3-1. 퀵 정렬의 특징 및 시간 복잡도
퀵 정렬은 이름이 치명적이다. 원래 이렇게 도파민을 내뿜는 존재는 경계해야 한다. (ㅋㅋ)
퀵 정렬은 시간 복잡도가 중요한 특징이기에 다른 정렬 기법과 달리 동작 과정 설명에 앞서 특징과 함께 시간 복잡도를 설명하려고 한다.
퀵 정렬은 앞서 살펴본 두 정렬과 달리 비교 정렬이 아닌 분할 정렬이다.
분할 정렬은 배열이 분할되면서 길이가 짧아지기에 O(n log n)의 시간 복잡도로 정렬이 가능하다.
그러나 퀵 정렬은 피벗을 활용하여 비균등하게 정렬하는데, 최악의 경우 앞서 살펴보았던 선택 정렬이나 삽입 정렬처럼 O(n^2)으로 그다지 효율적이지 않다. 따라서 퀵 정렬은 '피벗'을 어떻게 정의해주는지가 굉장히 중요하다.
3-2. 퀵 정렬의 동작 과정
위 이미지를 통해 퀵 정렬의 정렬 과정을 구체적으로 살펴보자. 이 예시에서는 첫 번째 값을 피벗으로 정하였다.
퀵 정렬에서는 두 가지 지표(left, right)가 존재하는데, 하나(left)는 (피벗을 제외한) 좌측부터 피벗보다 큰 값을 탐색한다. 나머지 하나(right)는 우측부터 피벗보다 작은 값을 탐색한다. 그리고 각각의 지표가 기준에 충족되는 경우 서로의 값을 변경한다.
Step1-1에서 보면, left가 찾은 1번 인덱스의 7이 피벗 4보다 크고, right가 찾은 6번 인덱스의 7이 피벗 4보다 작기 때문에 두 값을 교환(swap)해 주었다.
Step1-2에서도 left가 찾은 2번 인덱스의 5가 피벗 4보다 크고, right가 찾은 5번 인덱스의 1이 피벗ㅅ 4보다 작기 때문에 두 값을 교환(swap)해 주었다.
step 1-3에서는 left와 right의 위치가 서로 역전되었으므로, right 위치로 피벗이 이동하고 피벗을 기준으로 좌측과 우측의 리스트를 나눈다.
이 때, 나누어진 리스트를 잘 살펴보자. 좌측 리스트는 피벗을 기준으로 "작은 값"들로만 구성되어 있고, 우측 리스트는 "큰 값"들로만 구성되어 있다. 이렇게 배열을 분할하면서 분할된 배열에 대해 정렬된 상태를 유지한다.
가장 작은 단위까지 분할하게 되면 전체 배열에 대해 정렬이 완료되며, 분할이 반복되며 배열의 크기가 작아질수록 정렬 속도가 빨라진다.
3-3. 퀵 정렬의 활용 방법
퀵 정렬은 피벗 설정 방식에 따라 최악의 시간 복잡도를 갖는 경우가 다르다.
이번 예시와 같이 첫 번째 값으로 설정해준 경우에는 리스트가 정렬되어 있는 경우이다.
퀵 정렬 특징을 고려해보면 피벗을 기준으로 왼쪽 서브 배열에 피벗보다 작은 값들, 오른쪽 서브 배열에 피벗보다 큰 값들이 배치된다.
오름차순으로 정렬된 경우 피벗의 왼쪽 서브 배열은 비어있고, 나머지 값은 모두 오른쪽 서브 배열로 들어가며 피벗이 한 칸씩 오른쪽으로 이동하게 된다. 역으로 내림차순으로 정렬된 경우는 반대로 값들이 모두 왼쪽 서브 배열로 들어가고, 오른쪽 서브 배열은 비어 있으며 피벗이 한 칸씩 왼쪽으로 이동하게 된다.
이를 방지하기 위해서는 무작위 값 혹은 중간값으로 결정하는 등 적절한 최적화 기법을 취해줄 수 있다.
4. 계수 정렬 (Count Sort)
4-1. 계수 정렬의 특징
계수 정렬은 한국어로는 이름이 조금 어렵다. 그래서 영어 이름을 보면 단박에 의미를 파악할 수 있다.
개수(Count)를 세어 정렬을 하는 정렬 기법이다.
매우 빠르지만, 배열을 활용하므로 정렬 범위가 한정되어 있을 때 가능하다는 특징이 있다.
4-2. 계수 정렬의 동작 과정
빈도수를 세는 배열을 하나 정의한다.
그리고 입력을 받으면 배열의 해당 위치에 개수를 카운팅한다. 예를 들어 1을 하나 입력 받으면 arr[1] 값에 1을 증가시키는 것이다.
모두 입력을 받은 후에, 빈도 값을 저장한 배열을 순차적으로 돌면서 입력 받은 개수만큼 출력해준다.
4-3. 계수 정렬의 시간 복잡도 및 활용 방법
계수 정렬은 데이터의 입력 개수 n에 입력 범위 k를 더한 O(n+k)의 시간 복잡도로 가능하다.
입력 받으면서 개수를 카운팅하고 배열을 돌면서 개수만큼 인덱스를 출력해주는 것이 끝이기 때문에 구현도 간단하고 효율성도 아주 좋다.
특수한 상황에서만 사용 가능하다는 한계점이 있지만, 메모리와 시간이 아주 제한적인 상황에 잘 활용할 수 있을 것이다.
5. Conclusion
정렬은 학부 시절 알고리즘의 가장 처음으로 배우는 내용이었다. 그만큼 많이 쓰이고 중요하다는 의미이다.
어떤 알고리즘을 사용하느냐에 따라 시간・메모리의 효율성이 크게 좌우된다.
절대적인 정답이 없고, 상황에 따라 적절한 알고리즘을 채택하는 것이 필요하므로, 경험과 안목을 키우는 것이 중요하다.
파이썬의 경우 많은 함수들이 최적화되어 함수 형태로 제공되고 있지만, 이런 개념들을 잘 이해하고 필요 시에 직접 구현할 수 있어야 한다.
여러 프로그래밍 문제들을 풀면서 느꼈지만, 알고리즘을 통째로 적용하는 경우는 많지 않았다.
원리와 동작 과정을 온전히 이해하고, 자유자재로 활용할 수 있도록 여러 번 구현하고 설명해보아야겠다.
'All-round developer > Computer Science' 카테고리의 다른 글
[알고리즘] 동적 계획법 (Dynamic Programming) + 메모이제이션(Memoization) (0) | 2025.04.15 |
---|---|
[응용] DFS와 2차원 배열 내 영역의 최대 개수 구하기 (0) | 2025.04.10 |
[알고리즘] DFS(Depth-First Search)와 BFS(Breadth-First Search) (0) | 2025.04.03 |
[자료구조] 그래프(Graph)와 탐색(Search) (0) | 2025.04.02 |
[자료구조] 스택(stack)과 큐(queue) (0) | 2025.04.01 |