알고리즘의 가장 기본인 정렬에 대해 정리해보겠습니다.

위와 같은 정렬이 되지 않는 숫자가 있다고 가정해보겠습니다.

선택정렬

선택정렬은 모든 숫자를 보고, 첫번째로 올 숫자를 찾아 서로 바꾸는 과정을 반복합니다.

오름차순 정렬이라고 할 때, 7개의 숫자 중 1이 첫번째로 와야하므로 1번 인덱스에 있는 숫자 2와 위치를 바꿉니다.

이제 2번째 위치에 올 수를 찾습니다. 2이므로 4와 2의 위치를 바꾸게 됩니다.

그럼 아래와 같이 2번째 숫자까지는 정렬이 된 상태가 됩니다.

이렇게 반복하면 시간복잡도 $O(N^2)$의 시간으로 정렬을 할 수 있습니다.

정리: 선택정렬
각 인덱스에 올 가장 작은 번호를 찾는 방식
시간복잡도 : $O(N^2)$

삽입정렬

삽입정렬은 왼쪽의 값들은 정렬이 되어있다고 했을 때, 다음 데이터가 어느 위치로 들어갈지 판단하는 과정을 반복합니다.

초기값은 정렬되어 있다고 가정하므로 2는 넘어가고, 4부터 확인하면 됩니다.

4는 2보다 큰 위치에 놓이면 되기 때문에 순서를 바꿀 필요가 없습니다. 7도 마찬가지이므로 2번의 연산 끝에는 아래와 같은 상태로 1을 비교하면 됩니다.

1은 2보다 왼쪽에 위치해야 하므로 정렬을 진행하면 아래와 같을 것입니다.

3은 2와 4사이에 와야 합니다.

삽입정렬 역시 시간복잡도 $O(N^2)$의 시간으로 정렬을 할 수 있지만, 최선의 경우에는 $O(N)$으로 선택정렬보다는 빠릅니다.

정리: 삽입정렬
현재 인덱스의 값을 정렬된 배열 중 어디에 넣을지 결정
시간복잡도 : $O(N^2)$
=> 최선의 경우 $O(N)$

퀵 정렬

기준 값(pivot)을 기준으로 큰 데이터와 작은 데이터를 서로 바꾸는 과정을 진행합니다.

2를 Pivot으로 설정하고 왼쪽에서부터 2보다 큰 첫번째 수, 오른쪽에서부터 2보다 작은 첫번째 수를 찾습니다.

왼쪽에서 4를 찾고, 오른쪽에선 1을 찾았습니다.

이제 두 수의 위치를 바꾸어줍니다. 그리고 멈추었던 위치에서부터 다시 찾기를 시작합니다.

이번에는 왼쪽에선 7을, 오른쪽에선 1을 찾았습니다. 하지만 찾은 숫자의 위치가 서로 지나간 뒤이기 때문에, 작은 수와 Pivot값을 바꿉니다.

이제는 Pivot이었던 2의 위치를 기준으로 왼쪽은 2보다 작은 수, 오른쪽은 2보다 큰 수임을 보장할 수 있습니다.

왼쪽의 분할된 배열과 오른쪽의 배열을 각각 정렬을 진행합니다. 왼쪽에는 1개의 원소만 존재하므로 생략하고 오른쪽을 진행하겠습니다.

7보다 작은 숫자는 존재하지 않기 때문에 왼쪽에서부터 간 인덱스는 배열의 크기를 넘어가고, 오른쪽에서부터는 5를 찾게됩니다.

따라서 7과 5를 바꿉니다.

이 과정을 반복하는 것을 Divide and Conquer라고 합니다.

퀵 정렬은 C++이나 JAVA 등에서 가장 많이 채택되는 기본 정렬 알고리즘 중 하나입니다.
매번 절반씩 분할된다면 $log(N)$의 재귀가 진행되므로 시간복잡도는 $O(Nlog(N))$입니다. 하지만 최악의 경우, 이미 정렬된 배열을 정렬하고자 하면 시간복잡도는 $O(N^2)$입니다.

정리: 퀵 정렬
Pivot을 어느 위치에 넣을 지 결정
시간복잡도 : $O(Nlog(N))$
=> 최악의 경우 $O(N^2)$

계수정렬

데이터의 크기가 정해져있어 점수 형태로 표현이 가능할 때 사용하능한 정렬 방식입니다.

가장 간단한 방식은 데이터 중 가장 큰 데이터의 크기만큼 배열을 선언하고, 존재하는 값들의 인덱스만 늘리는 방식을 볼 수 있습니다.

다음과 같은 입력에 대해서는 크기가 7인 배열을 만들고, 넣을 수 있을 것입니다.

1	2	3	4	5	6	7
1	2	0	1	0	0	1

그럼 이제 처음 인덱스부터 count 수만큼 다시 넣으면 됩니다.

계수정렬은 시간복잡도가 $O(N+K)$으로 짧지만 공간복잡도가 그만큼 더 커지는 단점도 존재합니다. 또한 제한적인 상황에서만 사용할 수 있는 정렬알고리즘이라는 단점이 존재합니다. K만큼 더해지는 이유는 초기화에 사용되기 때문입니다.

정리: 계수 정렬
각 데이터가 몇번 나오는지 기록하여 이를 기반으로 정렬된 값을 내보내는 방법
시간복잡도 : $O(N+K)$
=> N은 개수, K는 가장 큰 데이터의 값
공간복잡도 : $O(N+K)$

위 내용은 나동빈님의 정렬 알고리즘 유튜브 강의를 듣고 정리한 내용입니다.