알고리즘 기본기 다지기10. 비교 정렬 (선택, 삽입, 힙, 합병, 퀵)

선택정렬(Selection Sort)

오름차순 정렬일 경우, 작은 값부터 맨 앞으로 보내 정렬하는 것을 말한다. 일종의 PQ-sort(Prioity Queue Sort, 우선순위 큐 정렬)이며 우선순위 큐가 무순리스트로 구현된다.

 

1. 주어진 리스트중 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 바꾼다.
3. 맨 처음 위치를 제외하고 나머지 리스트 값을 변경한다.

알고리즘이 단순하여 사용할 수 있는 메모리가 제한적일때 성능상 이점을 보일 수 있다.

예제

패스	테이블
0	[1,3,5,4,8,9,0,2]
1	[0,1,3,5,4,8,9,2]
2	[0,1,3,5,4,8,9,2]
3	[0,1,2,3,5,4,8,9]
4	[0,1,2,3,5,4,8,9]
5	[0,1,2,3,4,5,8,9]
6	[0,1,2,3,4,5,8,9]
7	[0,1,2,3,4,5,8,9]
8	[0,1,2,3,4,5,8,9]

삽입 정렬(Insertion Sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬알고리즘이다.  일종의 PQ-sort(Prioity Queue Sort, 우선순위 큐 정렬)이며 우선순위 큐가 순서리스트로 구현된다.

배열이 길어질 수록 효율이 떨어진다. 하지만 구현이 간단하다는 장점이 있다.

힙(Heap)

우선순위 큐 데이터구조를 만드는데에 무순리스트, 순서리스트 방식을 사용했었다. 이 외에도 힙라는 데이터구조를 사용하여 우선순위 큐를 구현할 수 있다.

• 힙 순서(heap order) : 모든 부모-자식 관계의 노드에서 부모의 키가 자식노드보다 작거나 같은 이진트리이다.
• 완전이진트리(complete binary tree) : 힙은 완전 이진트리로 구성되어야 한다.

완전이진트리(Complete Binary tree)

• 노드의 개수 = 깊이 i * 2
• 깊이 h -1 에서 내부 노드들은 외부 노드들의 왼쪽에 존재한다.
• 힙의 마지막 노드는 깊이 h-1의 오른쪽 내부노드이다.

힙을 이용한 우선순위 큐 구현

힙을 구성하는 이진트리 내부노드를 (키, 원소) 쌍의 데이터 항목응로 저장한다.

힙에 삽입 시,

1. 키 k를 삽입할 준비
2. 새로운 마지막 노드 z 찾기
3. 키 k를 z에 저장한 수 z를 내부 노드로 확장
4. 힙 순서(heap order) 정렬

우선순위 큐는 루트 키를 삭제하는 것을 원칙으로 한다.

힙에 노드 삭제 시,

1. 루트를 삭제하여 저장된 키를 반환
2. 루트 키를 마지막 노드 w의 키로 대체
3. 힙 순서 정렬

힙 정렬

힙은 우선순위 큐를 구현한 하나의 형태로 정렬에 응용될 수 있다. 내림차순 정렬을 위해 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

1. n개의 노드에 대한 완전이진트리 구성
2. 최대 힙을 구성
3. 가장 큰수를 가장 작은 수와 교환, 이를 힙 정렬이 완료될 때까지 반복

제지리 힙정렬

힙 정렬의 공간 사용을 줄일 수 있다. 배열의 경우 공간 문제가 발생할 수 있다. 주로 리스트가 주어진 경우 적용된다.

이전의 최소 힙(min-heap)이 아닌 최대힙(max-heap)을 사용한다. 

상향식 힙정렬

힙 정렬의 속도를 높일 수 있다. 만약 힙에 저장되어야 할 모든 키들이 미리 줘진다면 상향식 힙 생성을 하여 힙 정렬의 속도를 높일 수 있다.

합병정렬(Merge sort) 

비교 기반 정렬 알고리즘이다. 

n-way 합병 정렬 개념

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

2-way 합병 정렬

1. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다
2. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
3. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
4. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

퀵정렬(Quick Sort)

합병 정렬과 마찬가지로 분할통치법에 기초한 정렬 알고리즘이다.

1. 분할(divide) : 입력 리스트 원소 가운데 기준 원소를 택하여 리스트를 세부분으로 분할한다.(기준 원소보다 작은 원소들, 기준 원소와 같은 원소들, 기준 원소보다 큰 원소들)
2. 재귀(recur) : 기준 원소보다 작은 원소 집합과와 큰 원소집합들을 정렬한다
3. 통치(conquer) : 세 분할 된 집합들을 결합한다.

비교정렬(Comparison based sorting)

선택정렬, 삽입정렬, 힙정렬, 합병정렬, 퀵 정령들은 공통적으로 무순리스트의키들을 비교하여 원소들을 키 순서에 따라 재배치하는 비교정렬이다.

	시간	주요 전략
선택 정렬	O(n^2)	우선순위 큐(무순리스트)
삽입 정렬	O(n^2)	우선순위 큐(순서리스트)
힙 정렬	O(n log n)	우선순위 큐(힙)
합병 정렬	O(n log n)	분할 통치
퀵정렬	O(n log n)	분할 통치

 

연습문제

백준

2750(수 정렬하기) 2751(수 정렬하기2)

참고

백준 온라인저지 https://www.acmicpc.net/
LeetCode https://leetcode.com/
위키백과 https://ko.wikipedia.org/

문제 풀이

Github https://github.com/cri-kim/BlogPractice