알고리즘 - 정렬 (선택정렬, 삽입정렬, 퀵정렬, 계수정렬)

요즘 몇몇 사람들과 [이것이 코딩 테스트다] 책을 함께 읽으며 알고리즘 스터디를 하고 있다.

이번에 정렬 파트를 맡았어서 정렬에 관한 내용을 간단하게 정리했다. 

 

(영상은 전부 아래 사이트에서 가져와서 사용했습니다)

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

---

정렬

정렬이란 ?

데이터를 특정한 기준에 따라서 순서대로 나열하는 것

 

정렬은 크게 두 가지로 나뉠 수 있다.

1. 비교 정렬 (Comparison Sort) : 두 수의 비교를 바탕으로 정렬하는 알고리즘. O(NlogN) 이상의 성능을 내는 것이 불가능하다.

2. 비교가 아닌 정렬 (Non-comparison Sort) : 두 수의 비교 없이 정렬하는 알고리즘. O(NlogN) 이상의 성능을 내는 것이 가능하다. 주로 특수한 조건이 걸려 있을 때 사용할 수 있다.

 

읽은 책에서는 대표적으로 아래 네 가지 정렬을 소개하고 있어서 그 내용 위주로 정리했다. 

 

1. 선택 정렬

전체 데이터 중 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸는 것을 반복한다. 매우 단순하고 쉬운 정렬법.

시간복잡도 : O(N^2)

 

visualalgo - selection sort

 

2. 삽입 정렬

앞에서부터 차례대로 값을 확인하며 적절한 위치에 현재 데이터를 삽입한다

데이터가 거의 정렬되어 있다면 효율적 (비교를 많이 안하고 다음 데이터로 넘어감)

시간복잡도 : O(N^2)

 

visualalgo - insertion sort

 

3. 퀵 정렬

기준 데이터(피벗)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 것을 반복하는 알고리즘

 

< 정렬의 순서 > 

1. 데이터 하나를 피벗으로 정한다 
2. 왼쪽부터 피벗보다 큰 데이터를 찾고, 오른쪽부터 피벗보다 더 작은 데이터를 찾는다
3. 큰 데이터와 작은 데이터 위치를 서로 교환한다
4. 위의 2, 3을 계속 반복한다
5. 찾는 값의 위치가 서로 어긋나면 작은데이터와 피벗의 위치를 변경한다
6. 피벗의 왼쪽 오른쪽 리스트로 나눠서(분할) 리스트 데이터 개수가 하나가 남을때까지 2~5를 반복한다

현재 내장 라이브러리로 제공되는 알고리즘은 대부분 퀵정렬과 병합정렬을 기반으로 한다. 평균적으로 O(NlogN)의 시간복잡도를 가지기 때문. 특히 병합정렬은 최악의 경우에도 O(NlogN)을 보장한다. 그러나 최악의 경우를 방어하는 대신 일반적으로 퀵정렬에 비해 느리다고 한다.

 

시간복잡도 : O(NlogN)

-> 최악의 경우(피벗이 매번 제일 작은 수 or 큰 수로 걸려서 분할이 제대로 이뤄지지 않을 경우) : O(N^2)

-> 삽입정렬과 반대로, 데이터가 거의 정렬된 상태에서 피벗으로 계속 맨 앞 데이터를 고를 경우 매우 비효율적

-> 최악의 경우를 피하기 위해 랜덤하게 피벗을 정하는 경우가 일반적

 

visualalgo - quick sort

 

4. 계수 정렬

데이터 범위만큼의 배열을 만들고, 그 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시켜서 정렬하는 알고리즘

정렬해야할 데이터가 전부 정수이고, 최대값이 작을 때(수의 범위가 작을때) 사용할 수 있는 정렬 알고리즘

 

N이 데이터의 개수, K가 최대값의 크기일때,

시간복잡도 : O(N+K) 

-> N을 값의 범위라고 한다면, O(N)으로 쓸 수 있다. 비교 정렬에 비해 훨씬 빠르다

공간복잡도 : O(N+K)

-> 만약 범위가 넓은데 계수정렬을 시도한다면 중간에 0 으로 가득찬 배열을 가지게 될수도..

 

visualalgo - counting sort

 

개인적인 생각

정렬 알고리즘에 대해 많이 들어는 봤지만 직접 글로 정리해본적은 처음이다. 알고리즘 문제를 풀때 정렬을 해야하면 간단하게 sort를 해버리는 경우가 대부분이었던 것 같다. 워낙 문제를 많이 안풀어봐서 직접 구현하라는 문제를 아직 본적이 없다. 속도 때문에 계수정렬을 사용해야 하는 경우 정도만 본 것 같다. 파고 들어가면 볼게 한도끝도 없겠지만 일단 능력 부족으로 간단하게 남기며 이만..