선택정렬 | 삽입정렬 | 버블정렬 | 병합정렬 | 힙정렬 | 퀵정렬 | 트리정렬 | 팀정렬 |
n^2 | n^2 | n^2 | nlogn | nlogn | nlogn | nlogn | nlogn |
특정 정렬알고리즘이 무조건 좋다는 개념은 없다. 원소의 개수, 메모리의 크기 등등을 전부 고려하여 버블정렬이라도 최고의 효율을 낼 때가 있다.
선택정렬
1 번쨰부터 끝날 떄까지 모든 원소들을 순회한후 가장 작은걸 1번째로 교환
그다음에는 2번째 위아같은 방법을 반복한다.
•
시간 복잡도
◦
Avg: O(n^2)
◦
Worst: O(n^2)
◦
Best: O(n^2)
void selecSort(std::vector<int>& arr)
{
int n = arr.size();
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
if (min != i)
{
std::swap(arr[i], arr[min]);
}
}
}
Python
복사
삽입정렬
k 번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한칸 씩 뒤로 밀어내는 형식이다.
•
시간 복잡도
◦
Avg: O(n^2)
◦
Worst: O(n^2)
◦
Best: O(n)
void insertSort(std::vector<int>& arr)
{
for (int i = 1; i < arr.size(); i++)
{
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
Python
복사
버블 정렬
시간복잡도가 안좋긴 하지만 코드가 단순하다. 원소의 이동이 서로 앞뒤로 뒤바뀌면서 거품처럼 정렬되는 듯한 모습을 보여주어서 버블정렬이라고 한다.
시간 복잡도
•
Avg: O(n^2)
•
Worst: O(n^2)
•
Best: O(n)
void bubleSort(std::vector<int>& arr)
{
for (int i = 0; i < arr.size(); i++)
{
for (int j = 0; j < arr.size() - 1; j++)
{
if (arr[j] > arr[j + 1])
{
std::swap(arr[j], arr[j + 1]);
}
}
}
}
Python
복사
Merge Sort(머지소트)
배열의 길이가 1이 될때까지 2개의 부분 배열로 분할한다. 그후 2개의 배열에서 값을 비교한후에 합병을 진행한다. 이와 같은 과정을 모든 부분의 배열이 합병될때까지 반족해준다.
기존에 있는 배열을 여러개로 나누어서 사용하기 떄문에 추가적인 메모리 공간이 필요하다.
•
시간 복잡도
◦
Avg: O(nlogn)
◦
Worst: O(nlogn)
◦
Best: O(nlogn)
void run(int start, int end)
{
int mid = (start + end) / 2;
if (start == end)
{
return;
}
run(start, mid);
run(mid + 1, end);
int a = start; // a의 영역은 start ~ mid
int b = mid + 1; // b의 영역은 mid+1 ~ end
int idx = 0;
while (true)
{
if (a > mid && b > end)
break;
if (a > mid) result[idx++] = vect[b++];
else if (b > end) result[idx++] = vect[a++];
else if (vect[a] < vect[b]) result[idx++] = vect[a++];
else result[idx++] = vect[b++];
}
for (int i = 0; i < idx; i++)
{
vect[start + i] = result[i];
}
}
int main()
{
run(0, 4);
return 0;
}
Python
복사
힙정렬
선택정렬과 비슷하지만, 힙(자료구조)를 사용해서 가장 큰 원소를 찾는다는 차이점이 있다.
트리 기반으로 최대힙트리, 최소힙 트리를 구성하여 데이터를 정렬한다.
항상 nlogN의 성능을 발휘해 안정적인 속도를 보여준다.
여기서 힙이란?
완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 여러값중 최소, 최대값을 빠르게 찾기 위해서 데이터를 삽입할때 이미 정렬을 같이 진행해준다.
(이진 탐색 트리와 다르게 중복값을 허용한다)
•
시간 복잡도
◦
Avg: O(nlogn)
◦
Worst: O(nlogn)
◦
Best: O(nlogn)
void heapSort(std::vector<int>& arr)
{
std::priority_queue<int> pq;
for (int i = 0; i < arr.size(); i++)
{
pq.push(arr[i]);
}
for (int i = 0; i < arr.size(); i++)
{
arr[i] = pq.top();
pq.pop();
}
}
Python
복사
퀵정렬
데이터 집합에서 임의 기준 피벗을 정하고 ,집합을 해당하는 피벗을 기준으로 두개의 집합으로 나눈다. 한쪽 집합에서는 피벗보다 작은 값을, 나머지 한쪽은 큰값을 모아서 넣는다.
더이상 쪼갤 부분이 없을떄까지 위 과정을 반복한다.
void quickSort(std::vector<int>& arr)
{
if (arr.size() <= 1)
return;
std::stack<int> s;
s.push(0);
s.push(arr.size() - 1);
while (!s.empty())
{
int end = s.top();
s.pop();
int start = s.top();
s.pop();
int pivot = arr[end];
int i = start - 1;
for (int j = start; j < end; j++)
{
if (arr[j] < pivot)
{
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[end]);
int p = i + 1;
if (p - 1 > start)
{
s.push(start);
s.push(p - 1);
}
if (p + 1 < end)
{
s.push(p + 1);
s.push(end);
}
}
}
Python
복사
트리(2진) 정렬
이진 탐색 트리를 만들어서 정렬하는 방식이다. 추가될 값이 기존 노드보다 작으면 왼쪽
크면은 오른쪽 자식으로 삽입한다. 모든값이 노드로 추가 되었으면 해당트리를 순회하는 방식으로 값을 정렬한다.
하지만 위와같은 방식은 모든 트리를 순회하는데 있어서 시간이 효율이 떨어질수 있기 때문에
AVL(자가 균형 이진)트리를 이용하여 사용하는 경우가 많다. 가장 최근에는 std::map은 RED/BLACK 트리를 사용한다.
이 부분들은 추후에 따로 하나의 챕터로 준비할 예정입니다.
AVL 예시
RED/BLACK
