[Algorithm] 정렬

기본 개념

정렬은 컨테이너에 저장된 데이터를 크기 순으로 나열하는 알고리즘을 말한다.

정렬 알고리즘은 굉장히 많은 알고리즘들의 기초 토대가 되기 때문에, 잘 알고 있어야한다.

다음과 같은 수열이 있다고 가정해보자.

3, 500, 2, 600, 5, 150, 800, 1, 2500, 800

수열을 작은 수에서부터 큰 수로 나열하는것을 오름차순 정렬이라 한다.

1, 2, 3, 5, 150, 500, 600, 800, 800, 2500

수열을 큰 수에서부터 작은 수로 나열하는것을 내림차순 정렬이라 한다.

2500, 800, 800, 600, 500, 150, 5, 3, 2, 1

 

어떤 정렬 알고리즘으로 수열을 정렬하였을 때 같은 크기의 원소가 정렬 후에도 순서가 유지된다면,

그 정렬을 Stable Sort라 부른다. 반대로 순서가 보장되지 않는 경우 Unstable Sort라 부른다.

 

 

정렬의 종류

거품 정렬 (Bubble Sort)

제일 뒤 원소부터 2개씩 원소를 비교해가며 작은 원소와 큰 원소의 위치를 교환(swap)한다.

이 과정을 N번 수행하면 수열이 정렬된 상태가 될 것이다.

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

안정성 : Stable

 

선택 정렬 (Selection Sort)

전체 범위의 대한 최대 원소를 찾아 맨 뒤로 보낸다.

N - 1 범위의 대한 최대 원소를 찾아 N - 1 위치로 보낸다.

N - 2 범위의 대한 최대 원소를 찾아 N - 2 위치로 보낸다.

...

이 과정을 수행하고 나면 수열이 정렬된 상태가 될 것이다.

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

안정성 : Unstable

 

삽입 정렬 (insertion Sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

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

안정성 : Stable

 

힙 정렬 (Heap Sort)

힙이라는 자료구조를 이용한 정렬 알고리즘이다. 힙은 최대 원소를 바로 꺼낼 수 있고,

최대 원소가 제거된 힙은 빠르게 복구된다.

그러므로 힙에서 최대 원소를 차례대로 꺼내면 정렬이 완성된다.

힙에 모든 원소를 넣기위해 O(NlogN)

힙을 N번 복구하기위해 O(logN) * N

시간복잡도 : O(NlogN)

안정성 : Unstable

 

병합 정렬 (Merge Sort)

병합 정렬은 MergeSort라는 재귀적 연산을 정의한다.

MergeSort는 수열을 반으로 쪼개고,

왼쪽 부분수열에 대해 MergeSort,

오른쪽 부분수열에 대해 MergeSort,

두 부분수열이 정렬되어 있으니, 정렬된 두 부분수열을 합치며 정렬한다.

시간복잡도 : O(NlogN)

안정성 : Stable

 

 

퀵 정렬 (Quick Sort)

퀵 정렬은 QuickSort라는 재귀적 연산을 정의한다.

수열 내 한 원소를 선택한다. 이 원소를 피벗(Pivot)이라 부른다.

피벗을 기준으로 작은 원소들은 모두 왼쪽으로 보내고, 큰 원소들은 모두 오른쪽으로 보낸다.

왼쪽으로 보내진 부분수열에 대하여 QuickSort,

오른쪽으로 보내진 부분수열에 대하여 QuickSort

시간복잡도 : O(NlogN)

안정성 : Unstable

 

 

정렬 활용 (C++)

C++에서는 STL 에서 정렬 알고리즘을 지원해준다.

STL의 정렬은 상황에 맞게, 컨테이너의 크기에 맞게 적절한 정렬전략을 선택하여 동작하는 복합정렬이다.

 

기본 사용법

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Sort/1-Sort.cpp

insooneelife/AlgorithmTutorial

 

문자열 정렬

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Sort/2-SortString.cpp

insooneelife/AlgorithmTutorial

 

 

구조체 정렬

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Sort/3-SortStruct.cpp

insooneelife/AlgorithmTutorial

 

 

비교연산의 유효성 검증방법

비교연산을 만들기 위해서는 다음과 같은 규칙을 지켜야 한다.

1. a < a는 항상 거짓이다. (비반사성)

2. a < b가 참이면 b < a는 거짓이다. (비대칭성)

3. a < b가 참이고 b < c가 참이면 a < c 이다. (전이성)

4. a < b와 b < a가 모두 거짓이면 a와 b는 같은 값으로 간주한다.

5. a와 b가 같고, b와 c가 같으면 a와 c도 같다. (상등 관계의 전이성)

 

구현

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Deprecated/4-SortCompareValid1.cpp

insooneelife/AlgorithmTutorial

 

 

정렬 비교의 유효성 검증 예제 1.

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Sort/4-SortCompareValid1.cpp

insooneelife/AlgorithmTutorial

 

 

정렬 비교의 유효성 검증 예제 2.

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Sort/5-SortCompareValid2.cpp

insooneelife/AlgorithmTutorial