2016-05-18 오후 4:16
정렬이란??
정렬을 n개의 숫자로 입력받아 점점 커지거나 작아지는 순서로 배열, 나열 하는것
오름차순 increasing order
내림차순decreasing order
선택정렬
설명을 하자면
단계적으로 설명하는게 효과적이다.
한마디로 "선택을 해서 정렬을 하는 알고리즘이다. "
그럼 무엇을 선택할래 ?
최소값 선택
오름차순
최대값 선택
내림차순
최소값이나 ㅅ최대값을 선택해서 정렬한다.
- 최소값 선택정렬
- 정렬되지 않은 숫자중에 가장 작은 숫자 선택
- 선택한 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 바꾸면 정렬된것이다.
다시 1번 부터 반복
정확성 증명
수학적 귀납법 이용
i 번째 선택한 숫자가 i번째 작은 숫자인지를 증명
성능분석
최고차 항을 세타로 표현
모든 숫자들을 비교하는것
시간 복잡도는 세타 n 제곱
왜냐면 n(n-1)*½이기 때문에 최고차항은 n²이기때문에
Θ(n²)
삽입정렬
"삽입해서 정렬한다. "
Key 값과 정렬된 리스트가 주어졌을 때, key 값을 정렬된 리스트의 알맞은 위치에 삽입
삽입 정렬이라는 것은 키값이랑 정렬된 배열이 필요하다.
문제를 변경해도 되지만 알고리즘 성능에 영향을 미쳐서는 안됨
For 문에서는 항상 횟수를 +1해서 세어 줘야됨
- 최선의 경우 = 정렬하려고 하는데 정렬이 되어있는경우 키값 바로 앞에 있는수가 항상 작기 때문에 비교횟수는 항상 1번 n에대한 선형함수가 되므로 an+b
- 최악의 경우 = 최악의 경우는 반대로 정렬되어 있는경우 키값 앞은 항상 키값보다 크기 때문에 n에 대한 2차함수가 되므로 an²+bn+c 로 표현된다.
- 평균의 경우 = n²
하지만 정렬되어 잇는경우에 최선, 최악이 정해지기 때문에 이런경우 거의 없다
공간 복잡도
자기자리에서 앞뒤로 움직이기 때문에 선형시간으로 결정된다.
정리
키값이 있다.
정렬된 배열안에 알맞은 위치에 집어넣는다.
삽입을 할때 몇번 비교 하냐에 따라 비교횟수달라지지만 평균적으로 시간복잡도는N²이다.
합병정렬
"합병을 이용한 정렬 알고리즘 "
두개의 정렬된 배열이 주어졌을 때, 정렬된 하나의 배열로 합병
입력이 두개
Ex:)
두개의 배열중 첫번재 값들끼리 비교하여 제일 작은 값 찾는다
<1,5,6,8>
<2,4,7,9>
1이 작기때문에
<1,x,x,x,x,x,x,x,>
<5,6,8>
<2,4,7,9>
5와 2중 2가 작기때문에
<1,2,x,x,x,x,x,x,x>
.
.
.
.이런식으로
정렬 된다.
수행시간은 Θ(n₁+n₂)
이동횟수는 n₁+n₂
비교횟수는 n₁+n₂ 보다 작거나 같다.
결국, 비교횟수 +이동횟수<=2(n₁+n₂)
최종적으로 성능은 Θ(n₁+n₂)
정렬된 두개의 리스트를 받아야 한다.
입력이 n개로 들어오면 안맞아서 맞춰줄 필요가 있음
그래서 ...
Divide-and-conquer approach!!
크기가 커서 풀기 어려운 하나의 문제를 크기가 작아서 풀기 쉬운 여러개의 문제로 바꾸어서 푸는 방법
- Divide
- n Keys 를 두개의 n/2 keys로 나눈다.
- Conquer
- 합병정렬을 사용하여 두개의 배열을 정렬한다.
- Combine
- 두 개의 정렬된 배열을 하나로 합치는 과정
8개의 입력을
8
4- 4
2-2 2-2
이렇게 나눈다.
합병정렬은 1개가 될때까지 계속 쪼갠다 . \
그런다음 다시 합친다.
순서는
8
4-4
2-2 2-2
1 1 1 1 1 1 1 1
2-2 2-2
4-4
8 정렬완료!
Divide와 merge 의 과정 반복
Soudo code
A: n개의 수가 있는 배열
p: 배열의 첫번째 인덱스
r: 배열의 마지막
Merge-Sort(A,p,r)
If p<r // 배열안의 숫자가 1나가 될때까지
q=|(q+r)/2| //중간 지점
Merge-Sort(A,p,r) // 재귀하여 앞부분 반으로 쪼갬
Merge-Sort(A,q+1,r)// 재귀하여 뒷부분을 반으로 쪼갬
Merge(A,p,q,r)
합병정렬 수행시간
2T(n/2)+Θ(n)
크기가 1인 n 개의 문제를 푸는 시간
2T(n/2)+cn 이라고 하기도 함
바이너리 트리의 높이의 값이 키 포인트
N개의 입력이 주어졌을 때 1이 될때까지 바이너리로 나누어야 하는 횟수는
Logn+1
Θ(n logn)
