정렬

정렬 개념

정렬이란 원하는 순서로 데이터를 나열하는 것을 말합니다. 특정 값에 의거하여 오름차순이나 내림차순일 수도 있고, 임의의 조건이 될 수도 있습니다.

정렬이 필요한 이유

데이터를 정렬하면 원하는 데이터를 쉽게 찾을 수 있습니다. 앞에서 말했던 이진 탐색 트리가 그 예입니다.

const a = [1, 5, 7, 9, 3];
const b = [1, 3, 5, 7, 9];

가장 높은 수를 구해달라는 조건이 있습니다. 이때 위에 배열에서 어떤 배열이 접근이 편한지 바로 알 수 있습니다. 즉 정렬해서 데이터를 관리한다면 데이터의 값을 보거나 비교할 필요 없이 말 그대로 정렬된 데이터에서 마지막 값에 접근하면 해당 값이 가장 큰 값이 됩니다.

const max = b.at(-1);

삽입 정렬

삽입 정렬은 정렬된 영역과 정렬되지 않은 영역을 나누고 정렬 되지 않은 영역의 값을 적절한 위치로 놓으며 정렬하는 것을 의미합니다.

삽입 정렬을 하는 방법은 다음과 같습니다.

최초에 정렬된 영역을 왼쪽 1개라고 생각하고 나머지는 정렬되지 않은 영역이라고 합니다.
나머지 중 가장 위인 값을 키라 칭하고 해당 값이 정렬된 영역에서 바라보고있는 포인터보다 값이 크다면 멈추고 값이 작다면 기존에 있던 값을 오른쪽으로 한칸씩 밀어냅니다.
모든 요소가 정렬될 때까지 해당 정렬을 반복합니다.

삽입 정렬의 시간 복잡도

최악의 경우 입니다. 최악의 경우란 처음부터 의도한 순서과 완전히 반대로 정렬되어 있는 경우를 말합니다. 최선의 경우는 으로 이미 정렬되어있는 상태를 의미합니다.

병합 정렬

정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬합니다.

병합 정렬의 시간 복잡도

병합 정렬의 동작은 분할과 결합으로 나눠집니다. 계속 해서 반으로 나누는 과정을 반복한 더 이상 나눌 수 없을 때까지 만큼 반복합니다. 이후 다시 병합하며 정렬을 하니 N개면 N번 결합합니다.

따라서 아래지수는 생략이 되고 이라고 볼 수 있습니다.

힙 정렬

이는 힙이라는 자료구조를 사용해 결정합니다.

힙이란?

힙은 특정 규칙이 있는 이진 트리로 규칙에 따라 최대힙과 최소힙으로 나눠집니다. 최대 힙은 부모 노드가 자식 노드보다 크고, 최소힙은 부모 노드가 자식 노드보다 작습니다.

힙 구축 방법: 최대힙 편

최대힙과 최소힙은 힙을 구성하는 규칙만 다르고 나머지는 모두 동일합니다.

현재 노드와 자식 노드의 값을 비교합니다.
1. 현재 노드의 값이 가장 크지 않다면 자식 노드 중 가장 큰 값과 현재 노드의 값을 바꿉니다.
2. 자식 노드가 없거나 현재 노드의 값이 크다면 연산을 종료합니다.
맞바꾼 자식 노드의 위치를 현재 노드로 하여 과정 1을 반복합니다.

힙 정렬 과정: 최대힙 편

루트 노드가 가장 큰 값이므로 루트 노드의 값을 빼서 저장하면 됩니다. 하지만 루트 노드가 빠지더라도 최대힙이 유지되는 것이 중요합니다.

정렬되지 않은 데이터를 최대 힙으로 구축합니다.
현재 최대힙의 루트 노드와 마지막 루트를 맞바꿉니다. 맞바꾼 뒤 마지막 노드는 최대 힙에서 제외합니다.
마지막 노드가 최대힙이 되고난 이후 최대힙을 다시 구축해야합니다. 최대 힙의 크기가 1이 될 때까지 1 ~ 3의 순서를 반복합니다.

우선순위 큐

우선순위 큐는 우선순위가 높은 데이터부터 먼저 처리하는 큐입니다. 예를 들어 값이 낮은 수가 우선 순위가 높다고 했을 때 4, 3, 9 순으로 들어간다고 했을 때 pop을 하면 3 -> 4 -> 9 순서대로 나오게 됩니다. 큐의 내부 동작은 힙과 유사하므로 큐를 구현할 때는 힙을 활용하는 것이 효율적입니다.

우선순위 큐가 동작하는 방식

빈 우선순위 큐를 하나 선언합니다. 형태는 큐와 같습니다.
4를 삽입합니다.
3을 삽입합니다. 3은 4보다 우선순위가 높기 때문에 4 앞에다가 삽입 합니다.
9를 삽입합니다. 9는 우선순위가 가장 낮기 때문에 맨 뒤에 삽입합니다.

이후 앞에있는 순서대로 pop을 하면서 나오게 되는 것입니다.

힙으로 우선순위 큐를 구현해야하는 이유

최소 힙이나 최대 힙은 특정 값을 루트 노드에 유지하는 특징이 있고 이는 우선순위 큐와 딱 맞아 떠어지므로 우선순위 큐를 이용하여 구현해야하는 것을 알 수 있습니다.

위상 정렬

위상 정렬은 일의 순서가 있는 작업을 순서에 맞춰 정렬하는 알고리즘입니다.

위상 정렬과 진입 차수

위상 정렬은 자신을 향한 화살표 개수를 진입 차수로 정의하여 진행합니다. 만약 진입 차수가 0이라면 이는 바로 할 수 있는 일입니다.

위상 정렬 과정

진입 차수가 0인 일을 해결하고 관련된 진입 차수를 1씩 낮추면서 새롭게 진입 차수가 0이 된 작업들을 해결하는 식으로 진행합니다. 이 해결이라는 행위를 큐를 사용하여 구현합니다.

위상 정렬의 시간 복잡도

위상 정렬은 모든 정점과 간선을 딱 한 번씩만 지나므로 시간 복잡도는 가 됩니다.

계수 정렬

계수 정렬은 데이터에 의존하는 정렬 방식입니다. 지금까지는 사용자가 정한 기준에 따라 정렬 했습니다. 반면 계수 정렬은 데이터의 빈도수를 통해 정렬하는 것을 말합니다.

const array = [1, 2, 3, 4, 1, 2];

위와 같은 배열이 있다고 하였을 때 이를 다음과 같이 기록할 수 있습니다.

const ea = [2, 2, 1, 1]

이후 이를 반복문과 같이 빈도수만큼 출력하듯이 배열을 채울 수 있습니다.

[1, 1, 2, 2, 3, 4]

계수 정렬의 한계

계수 정렬은 빈도수를 세어 빈도수 배열에 저장하는 것을 말합니다. 하지만 저장할 값의 범위가 듬성듬성 하거나 음수가 있을 경우 계수 정렬을 하기 곤란해집니다. 따라서 만약 범위가 크거나 음수가 있다면 다른 정렬을 고민해보는 것이 좋습니다.

값이 N개이고 최솟값 ~ 최댓값의 범위 크기가 K라면 빈도수 배열에서 K + 1 만큼 탐색을 해야하기에 시간 복잡도는 입니다.

정렬 알고리즘의 시간 복잡도

정렬 방법	최악의 경우	최선의 경우	특이점
삽입 정렬			데이터가 정렬되어 있다면 최고의 성능을 발휘합니다.
병합 정렬			안정적인 성능으로 정렬할 수 있습니다. 병합 과정에서 추가 메모리가 발생가능합니다.
힙 정렬			안정적인 성능으로 정렬할 수 있습니다. 삽입과 동시에 정렬할 수 있습니다.
계수 정렬			데이터에 의존적이므로 항상 사용 가능한 것은 아닙니다.
위상 정렬			작업의 순서가 존재할 때 사용되는 방법입니다.

Last modified: 14 August 2024