정렬 (Sorting)

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

정렬의 종류에는 여러 가지가 있는데, 그중에서 선택정렬, 삽입정렬, 퀵정렬, 계수정렬에 대해 알아볼 것이다.

정렬을 하면 이진 탐색이 가능해지기 때문에 잘 알아두면 도움이 많이 될 것 같다.

 

우선 정렬의 종류를 알아보기 전에 정렬 알고리즘의 두 가지 성질을 먼저 알아볼 것이다.

🍁 정렬 알고리즘의 두 가지 성질

1. stable vs unstable

- 같은 숫지면 입력된 순서가 정렬 후에도 그대로 유지되도록 하는 게 더 바람직하다! -> stable하다!

2. in-place vs not in-place

- 정렬을 하면서 추가로 사용하는 메모리의 양

- in-place는 기존 리스트에서 정렬을 하는 것이고, not in-place는 리스트를 추가로 생성해서 사용하는 것이다.

- in-place는 추가 메모리를 \(O(1)\)정도만 사용한다.

- not in-place는 N개의 숫자를 정렬할 때 \(O(N)\) 정도의 메모리를 또 사용한다.

🍀 선택정렬(Selection Sort)

- 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

- 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료된다.
- 탐색 범위는 갈수록 줄어든다.
- 이중 반복문으로 구현할 수 있다.
- N-1번 만큼 가장 작은 수를 찾아서 앞으로 보내고, 매번 가장 작은 수를 찾기 위해 비교 연산이 필요하기 때문에 시간복잡도는 \(O(N^2)\)이다.

🍀 삽입정렬(Insertion Sort)

- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

- 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬 되어있다고 가정한다.

-> 두 번째 데이터부터 정렬 시작.(첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문)

 

- 정렬이 이루어진 원소는 항상 오름차순을 유지한다. -> 특정한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

- 선택 정렬에 비해 구현 난이도가 높은 편이지만 일반적으로 더 효율적으로 동작한다.
- 시간복잡도는 \(O(N^2)\)이지만, 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
    - 최선의 경우 O(N)의 시간복잡도를 가진다.

=> 정렬이 거의 이루어진 상태로 입력이 주어진다면, 삽입 정렬을 사용하자!

 

🍀 퀵 정렬(Quick Sort)

- 기준을 설정하고 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방법으로 동작한다.
- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정

동작 예시

1. 피벗을 정하고 왼쪽과 오른쪽에서 차례로 오면서 왼쪽은 피벗보다 큰 값이, 오른쪽은 피벗보다 작은 값이 오면 멈추고 위치를 변경한다.
2. 위치를 바꾼 후 계속 나아간다
3. 계속 가다가 위치가 엇갈리는 경우 '피벗'과 '작은 데이터'의 위치를 서로 변경한다.
4. 이제 피벗의 왼쪽에 있는 데이터는 모두 피벗보다 작고, 오른쪽에 있는 데이터는 피벗보다 크다.
    - 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할 혹은 파티션이라고 한다.
5. 왼쪽 파트와 오른쪽 파트에 대해서 1~4번의 동작을 반복한다.-> 재귀함수로 구현
6. 종료 조건은 현재 리스트의 데이터 개수가 1일 경우이다.
    - 이미 정렬 되어 있다고 간주할 수 있으며, 분할이 불가능. 

시간복잡도

- 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 \(O(NlogN)\)을 기대할 수 있다.
   - 너비 x 높이 = N x logN = NlogN

- 평균의 경우  \(O(NlogN)\)의 시간 복잡도를 가짐
- 최악의 경우 \(O(N^2)\)의 시간 복잡도를 가짐.

- 데이터가 무작위로 입력되는 경우, 퀵 정렬은 매우 빠르게 동작하지만, 이미 정렬 되어 있는 경우에는 매우 느리게 동작한다. (삽입 정렬과 반대!)

 

🍀 계수 정렬(Count Sort)

- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.
    - 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.

        -> 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 가능

        -> why? 모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언해야 하기 때문

동작 과정

1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
3. 결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력

 

- 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 시간복잡도는 \(O(N+K)\)이다.

- 공간복잡도 또한 \(O(N+K)\)이다.
- 때에 따라서 심각한 비효율성을 초래할 수 있음(데이터가 0과 999,999로만 이루어진 경우)
- 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용될 수 있다.
    - 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적이다.

🍀 파이썬의 정렬 라이브러리

- sorted() 함수 제공

- 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어짐(정확히는 병합정렬과 삽입정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘)

- 병합정렬은 퀵 정렬보다 느리지만, 최악의 경우에도 \(O(NlogN)\)을 보장한다.
* 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있음

 

 

정렬알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택정렬	O(N^2)	O(N)	아이디어가 매우 간단
삽입정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때는 가장 빠름
퀵정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합하며, 충분히 빠름
계수정렬	O(N+K)	O(N+K)	데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠름

 

---

📚 참고 : 이것이 취업을 위한 코딩 테스트다 with 파이썬

🎞 참고 : Chan-Su Shin youtube 정렬 알고리즘