[TIL] 정렬

DO IT 알고리즘입문 CH06

 

CH06 정렬 알고리즘

정렬 Sorting 이름, 학번, 학점 등의 키 Key 를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업

 

오름차순 Ascending Order 값이 작은 데이터를 앞쪽에 늘어놓는 것

내림차순 Descending Order 값이 큰 데이터를 앞쪽에 늘어놓는 것

안정적인 알고리즘 - 값이 같은 원소의 순서가 정렬한 후에도 유지되는 알고리즘

안정적이지 않은 알고리즘 - 정렬한 후에도 원래의 순서가 유지된다는 보장이 없다

내부 정렬 Internal Sorting 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용

외부 정렬 External Sorting 정렬할 데이터가 많아서 하나의 배열에서 작업할 수 없는 경우 사용

정렬 알고리즘 - 데이터를 교환, 선택, 삽입하며 정렬을 완료

버블 정렬 Bubble Sort

이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘

패스 Pass 일련의 비교, 교환 과정

시간 복잡도 O(n^2)

단순 선택 정렬 Straight Selection Sort

가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘

시간 복잡도 O(n^2)

단순 삽입 정렬 Straight Insertion Sort

주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘

장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 빠르다

단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다

시간 복잡도 O(n^2)

셸 정렬 Shell Sort

단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘

정렬할 배열에서 h 만큼 떨어진 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행

h 값은 서로 배수가 되지 않도록 정해야 한다 ( 거꾸로 봤을 때 1 부터 시작해서 h * 3 + 1 의 수열을 사용하여 계산 )

이웃하지 않고 떨어져 있는 원소를 서로 교환하므로 안정적이지 않다

시간 복잡도 O(n^1.25)

퀵 정렬 Quick Sort

가장 빠른 정렬 알고리즘

피벗 Pivot - 그룹을 나누는 기준

배열에서 Pivot 기준으로 두 그룹으로 나누어서 왼쪽 끝 원소의 인덱스를 pl, 오른쪽 끝 원소의 인덱스를 pr 로 설정하고

a[pl] ≥ x 가 성립하는 원소를 찾을 때까지 pl 을 오른쪽 방향으로 스캔

a[pr] ≤ x 가 성립하는 원소를 찾을 때까지 pr 을 왼쪽 방향으로 스캔

a[pl] 과 a[pr] 이 맞는 조건에서 위치할 때 두 값을 서로 교환하는 작업을 반복한다

모든 작업이 완료된 이후 a[pl] 과 a[pr] 이 같은 위치에 있을 때 같은 원소이지만 서로 교환한다 왜냐하면, 원소를 교환할 때마다 매번 pl 과 pr 가 같은 위치에 있는지 체크해야 하기 때문, 매번 체크하는 횟수보다 1번만 같은 원소를 교환하는 것이 비용이 적게 든다

퀵 정렬 또한 서로 이웃하지 않는 원소를 교환하므로 안정적이지 않은 알고리즘이다

시간 복잡도 O(n log n) ~ 최악의 경우 O(n^2)

피벗 선택하기
1. 나누어야 할 배열의 원소 수가 3 이상이면, 배열에서 임의의 원소 3개를 꺼내 중앙값인 원소를 피벗으로 선택
2. 나누어야 할 배열의 맨 앞 원소, 가운데 원소, 맨 끝 원소를 정렬한 뒤 가운데 원소와 맨 끝에서 두번째 원소를 교환한다, 맨 끝에서 두번째 원소값 a[right-1] 이 피벗으로 선택되었고, 그 동시에 나눌 대상을 a[left+1] ~ a[right-2] 로 좁힌다 

 + 퀵 정렬 추가 공부는 요기에 https://helloahram.tistory.com/13

병합 정렬 Merge Sort

배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘

시간 복잡도 O(n), 데이터 원소 수가 n 일 때 병합 정렬의 단계는 log n 만큼 필요하므로 전체 시간 복잡도는 O(n log n)

코드 구현은 요기에 https://helloahram.tistory.com/17

힙 정렬 Heap Sort

Heap - 부모의 값이 자식의 값보다 항상 크다 or 항상 작다 라는 조건을 만족하는 완전 이진 트리 (대소 관계만 일정하면 됨)

완전 - 부모는 왼쪽 자식부터 추가하여 모양을 유지하라

이진 - 부모가 가질 수 있는 자식의 최대 개수는 2개

+ 힙 Heap 이란?

우선순위 큐를 위해 고안된 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료 구조

여러 개의 값들 중에서 최대값이나 최소값을 빠르게 찾아내도록 만들어진 자료 구조

힙의 데이터 저장의 경우, 들어올 새 노드를 우선 순위가 가장 낮다는 가정을 하고 맨 끝 위치에 저장한다 → 부모 노드와 우선 순위를 비교해서 위치가 바뀌어야 하면 바꾸는 작업을 반복한다

힙의 데이터 삭제의 경우, 루트 노드를 반환(삭제)하고 마지막 노드 n 을 루트 노드 자리에 옮긴다 → n 의 왼쪽, 오른쪽 자식 노드 중 우선 순위가 높은 것과 비교를 반복한다

트리의 높이가 연산 횟수가 되므로 O(logN) 의 시간 복잡도를 가진다

도수 정렬 Counting Sort

* 추가 공부 필요

분포수 세기 Distribution Counting 정렬, 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘

도수 분포표 - 자료를 몇 개의 등급으로 나누고 각 등급에 속하는 도수를 조사하여 나타낸 표

 

 

참고한 블로그

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html