[알고리즘] 5. 고급 정렬(합병정렬, 퀵정렬)

1. 로그 개념과 효율성

log2 16=4;
logx y = N;
x^n=y;
nlog n <- n이커질수록 o(n)과 속도 차이가 크다

2. 고급정렬 종류

2.1 합병정렬

정렬할 값을 반으로 나눠 각각 정렬 후 두 정렬을 크기순으로 합침

2.1.1 고급정렬 예제

1) 아래 배열 정렬

2) 반으로 나누기->각 값이 하나씩 있을때까지

3) 각각 크기순으로 배열 합치기

2.1.2 합병정렬 시간복잡도

1) 왼쪽 /오른쪽 합병정렬 T(n/2) +T(n/2) => n
2) 두 배열 합치기 o(n)
3) T(n)=2*T(n/2)+O(n)
이걸 풀면…
T(n)=O(nlogn)

2.1.3 합병정렬 재귀함수 디자인

1) 함수 정의
2) 기저조건 s>=e이면 retrun
3) mearge(arr, s, e)
mearge(arr, s, mid)
mearge(arr, mid+1, e)

2.1.4 합병정렬 구현

1
2

2.2 퀵정렬

임의의 값 하나를 기준으로 기준값보다 큰건 오른쪽 작은건 왼쪽으로 보내기

2.2.1 예시

1) 아래 배열 퀵정렬

2) 배열 제일 앞숫자3 기준 정렬

3-1) 3기준 앞 배열 제일 앞 숫자1로 정렬

3-2) 3기준 뒤 배열 중 가장 앞 숫자 5기준으로 정렬

2.2.2 퀵정렬 시간복잡도

평균적으로는 O(nlogn) 가장 오래 걸리면 O(n^2)

2.2.3 퀵정렬 구현

1
2

2.3 힙정렬

트리구조를 이용한 정렬 나중에 나옴!