정렬 알고리즘

정렬 알고리즘이란

정렬 알고리즘은 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘을 뜻한다. 정렬 알고리즘에는 다양한 종류가 있지만 시간 복잡도와 공간 복잡도를 고려하여 올바른 알고리즘을 선택하는 것이 중요하다.

선택 정렬

시간복잡도(최악/최선/평균) : $O(n^2)$

선택 정렬은 아직 처리되지 않은 데이터들 중 가장 작은 데이터를 골라 맨 앞의 데이터와 변경하는 방식으로 다음과 같은 순서로 이루어진다.

1. 주어진 리스트에서 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺸 나머지 리스트를 같은 방법으로 교체한다.

삽입 정렬

시간복잡도(최악/평균) : $O(n^2)$
시간복잡도(최선) : $O(n)$

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식으로 다음과 같은 순서로 이루어진다.

1. 주어진 리스트에서 2번째 요소와 앞의 요소를 비교한다.
2. 해당 요소를 적절한 위치에 삽입한다.
3. 앞의 리스트를 제외한 나머리 리스트를 같은 방법으로 삽입한다.

버블 정렬

시간복잡도(최악/평균) : $O(n^2)$
시간복잡도(최선) : $O(n)$

버블정렬은 기본적으로 배열의 두 수 $(a, b)$를 선택하여 만약 그 두 수가 정렬되었다면 놔두고 아니라면 두 수를 바꾸는 방식으로 다음과 같은 순서로 이루어진다.

1. 배열의 첫 두 요소를 비교한다.
2. 만약 정렬되어 있다면 그대로 두고 아니라면 위치를 바꾸어 정렬한다.
3. 이를 배열의 처음부터 끝까지 여러 번 반복한다.
4. 만약 배여르이 변화가 없으면 정렬된 것으로 정의한다.

병합 정렬

시간복잡도(최악/최선/평균) : $O(nlogn)$

병합정렬은 다음과 같은 순서로 이루어진다.

1. 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n 개의 부분리스트로 분할한다.
2. 부분리스트가 하나만 남을 때까지 반복해서 병합하며 저렬된 부분리스트를 생성한다.
3. 마지막으로 남은 부분리스트가 정렬된 리스트이다.

퀵 정렬보다는 느리고 공간을 많이 잡아먹지만 안정 정렬에 속하여 동일 값일 때 기존의 순서가 보장된다는 장점이 있다.

퀵 정렬

시간복잡도(최악) : $O(n^2)$
시간복잡도(최선/평균) : $O(nlogn)$

퀵 정렬은 다음과 같은 순서로 이루어진다.

1. 리스트 가운데서 하나의 원고를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 분할한다.
3. 분할된 두 리스트에 대해 위 과정을 반복한다.