알고리즘 11강 :: 합병 정렬, 퀵 정렬, 힙 정렬

알고리즘 11강을 보며 배운내용

 

 

오늘은 알고리즘 10강에서 알아본 

버블정렬, 선택정렬, 셸 정렬보다

향상된 성능의 알고리즘을 알아본다

 

 

 

합병 정렬

1. 배열을 쪼개지지 않을 때까지 반으로 나누고

2. 합쳐주며 정렬

 

이미 4강에서 알아봤다(4강 링크)

 

✨ 특징

안정적 알고리즘

10강, 11강의 비교 기반 알고리즘 7개 가운데

제자리 정렬 아닌건 이녀석 하나

 

⌛ 시간 복잡도

O(nlogn)

 

 

퀵 정렬

1. 피벗을 중심으로 왼쪽, 오른쪽으로 나누고 정렬

 

⌛ 시간 복잡도

피벗 임의성 보장 하면 O(nlogn)

최악은 O(n²)

 

✨ 특징

제자리 정렬 알고리즘

 

 

힙 정렬

1. 일차원 배열 => 힙으로 변환

2. 힙의 최댓값 삭제

3. 힙 재구성

 

최대 힙: 내림차순 정렬

최소 힙: 오름차순 정렬

 

!! 여기선 내림차순 최대 힙 기준

 

 

힙(heap) 이란?

완전 이진 트리

각 노드의 값은 자신의 자식 노드 값보다 크거나 같다

 

힙의 장점

임의의 값 삽입과 최댓값 삭제가 편하다

 

⌛ 시간 복잡도

O(nlogn)

 

✨ 특징

제자리 정렬 알고리즘

 

힙의 구현

 

번호를 매겨서 일차원 배열로 구현한다

 

일차원 배열의 장점

1. 자식 노드 찾기 쉽다

=> 자식 노드 2i + 1, 2i + 2

 

2. 부모 노드찾기 쉽다

=> (i - 1) / 2

 

임의의 값 삽입

1. 맨 마지막에 넣고

2. 부모 값이 더 크도록 바꿔주며 자리 재배치

 

최댓값 삭제

1. 루트 값과 마지막 값 위치 변경(그런 다음 마지막값 무시)

2. 부모 값이 더 크도록 바꿔주며 자리 재배치

 

 

비교 기반 정렬 알고리즘

기본 성능 O(n²): 버블 정렬, 선택 정렬, 삽입 정렬 ,셸 정렬

향상된 성능 O(nlogn): 합병 정렬, 퀵 정렬, 힙 정렬

 

이 보다 더 좋은 비교 정렬 알고리즘 존재하나?

 

 

데이터 분포 정렬

주어진 원소 중에 자신보다 작거나 같은 값을 갖는 원소의 개수를 계산해서

정렬할 위치를 찾아서 정렬하는 방식

=> 입력값이 어떤 작은 정수 범위 내에 있다는 것을 알고 있을 때만 적용 가능

 

⌛ 시간 복잡도

O(n)

 

 

계수 정렬

비교 기반이 아니라 데이터 분포를 이용한 정렬

=> 입력값의 범위를 미리 알아야된다

그래서 일반적으로 사용 불가 하지만

알게되면 효과적인 알고리즘

 

안정적 정렬 알고리즘

 

빈도수에 따라 정렬을 한다는데

아직 잘 이해가 안간다

시간을 두고 친해져야겠다

 

 

Divide by Jeremy Bezanger #unsplash