🏷️JavaScript
퀵 정렬
분할 정복 알고리즘의 하나
- 분할 정복이란 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
- 피벗이라는 기준 값을 잡아서 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합쳐서 전체가 정렬하게 되는 방법.
방법
퀵 정렬은 다음의 단계들로 이루어진다.
- 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출(재귀)을 이용하여 다시 분할 정복 방법을 적용한다.
- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다. 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
특정한 값을 기준(피벗)으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 둘로 나눈다.
- 배열의 가장 첫 번째 값을 키(피벗) 값으로 잡는다.
- 키 보다 큰 숫자를 왼쪽부터 찾고, 작은 숫자를 오른쪽부터 찾는다.
- 값을 바꾼다.
- 작은 값의 인덱스가 큰 값의 인덱스보다 크다면 즉, 엇갈리지 않았다면 작은 값과 큰 값의 위치를 바꾼다. 다시 2,3번을 반복한다.
- 작은 값의 인덱스가 큰 값의 인덱스보다 작아졌다면 즉, 엇갈렸다면 키값과 작은 값의 위치를 바꾼다. 키 값은 정렬이 완료되었으므로 다음으로 넘어간다. 이때 작은 값을 찾지 못해서 키값까지 도달했다면 자기 자신과 바뀐다.
- 키가 정렬되었다면 키를 기준으로 앞의 배열과 뒤의 배열로 나누고, 각 배열을 1번부터 반복한다.
- 모든 값이 한 번씩 키가 되어 위치가 정해졌다면 정렬이 완료된다.
시간 복잡도
O(N*logN)
여기서 중요한 것은 이미 정렬이 되어 있는 경우에, 시간복잡도가 O(N^2)가 된다.
왜냐? 하나씩 피벗값이 되면서 절반을 나누지 않고 하나씩 정렬하게 되기 때문
병합 정렬
마찬가지로 분할 정복을 사용한다.
다만, 피벗 값에 따라 편향되게 분할할 가능성이 없다. 정확히 반씩 나눈다.
반으로 나눠서 정렬한 다음 나중에 합친다.
때문에 최악의 경우에도 항상 O(N*logN)을 보장한다.
4번의 비교만으로 정렬이 된다 즉, N만큼만 씀
힙정렬
힙 트리구조를 이용한다.
힙 정렬은 힙 생성 알고리즘을 사용한다.
방법 (최대 힙)
- 힙 생성 알고리즘
: 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾼다. 자식이 존재하면 계속 반복 O(logN) ⇒ 자식하고만 비교하기 때문에 트리의 깊이(logN) 만큼만 반복- 자식 노드가 없는 노드를 제외하고 가장 끝의 부모 노드부터 자식 노드들과 비교한다.
- 이때 부모 노드는 (자식 노드)/2 인덱스에 있으므로 모든 부모 노드는 힙 크기의 절반 인덱스까지만 존재한다. 따라서 원소의 길이/2 인덱스부터 앞으로 이동하면 부모 노드만 선택된다.
- 자식 노드가 부모 노드보다 크면 서로 교환한다.
- 한 칸씩 올라가며 진행한다.
- 자식 노드가 없는 노드를 제외하고 가장 끝의 부모 노드부터 자식 노드들과 비교한다.
- 힙 정렬 알고리즘
: 힙 생성 알고리즘으로 힙 구조를 생성하고, 루트 노드(최댓값)를 맨 뒤로 보내는 (정렬 완료)과정을 노드 수(N) 만큼 반복한다.- 루트 노드부터 시작하여 부모 노드를 자식 노드들과 비교하여 더 큰 값과 교환한다.
- 교환한 위치에서 다시 자식 노드들과 비교하여 더 큰 값과 교환한다.
- 자식노드 중 더 큰 값이 없을 때까지 반복한다.
시간복잡도
O(N*logN) ⇒ O(N) ⇒ logN은 N에 비해 매우 작기 때문에 생략
계수 정렬
범위 조건이 있는 경우 배우 빠른 알고리즘.
배열과 인덱스를 사용하여 크기를 세주면 된다.
→ 위치를 바꿀 필요도 없고 모든 데이터를 앞에서부터 한 번씩만 접근하면 되기 때문에 매우 빠르고 효율적
시간복잡도
O(N)
