알고리즘 2 - Sorting(Shell,Shuffle,Convex Hull)

Shell Sort의 중요성

기존 정렬 방법(Insertion Sort)의 활용 방안

간단한 아이디어로 성능 향상

코드 사이즈가 작아 메모리가 한정적인 임베디드 시스템에 사용하기 좋다

 

현 문제점:

실험상으로는 ~NlogN인 기존 정렬 방식보다 빠를 수 있음을 보였지만 수학적 모델을 사용해 모든 경우에 대해 정확히 비교를 못함

h-sort의 h 줄여 나가는 최적의 방식도 합의하지 못함

01-1. Insertion Sort <- 복습

01-2. h-sort 

02. Shell Sort <- Insertion Sort+h-sort 
03. Shuffle Sort (Shuffling에 정렬 방법 적용)
04. Convex Hull (Tight boundary 찾기 위해 정렬 방법 적용) -> 응용하면 graham's Scan

Insertion Sort

 

따라서 SWAP의 횟수가 성능에 영향을 미친다.

입력데이터의 상태에 따라 얼만큼 정렬이 되어있는지에 따라 성능에 극심한 차이가 있음

average case

순서 바꾸어야 할 원소의 쌍이 N에 비례한 개수 이하라면 (<= cN개)
~N회 작업이 필요하므로 Insertion Sort가 다른 정렬 방법에 비해 유리

(이 조건을 만족하는 경우를 partially ordered 상태라 함)

 

인접한 원소끼리 SWAP 함에 따라

Inversion 수만큼 비교 & 정렬이 안된 경우만 SWAP 수행

 

Inversion이란? 정렬 순서가 어긋난 쌍을 말한다

Insertion Sort는 inversion 수만큼 Swap 수행한다

위의 오름차순을 보면 inversion은 총 6이다 따라서 6회 swap을 수행한것이다.

 

그럼 이때까지 Insertion Sort는 매번 정렬순서가 어긋날때마다 인접한 원소끼리 SWAP을 하여 worst case가 생긴다

의문점: Insertion Sort는 인접한 원소끼리 swap 하므로 한 swap이 한 inversion만 해결 한 swap이 여러 inversion 한 번에 해결하게 할 수 없을까? -> h-sort

 

h-Sort

 

Q)그럼 h-sort에서 1-sort를 수행할시에는 지금까지 해온 Insertion sort 방식과 동일한가?

답은 yes이다. 1칸뒤와 SWAP을 수행하는데 한쌍 SWAP하는것과 동일하다.

 

Q)a-sort,b-sort (a<b)중어느쪽이할일이더많을까?왜그러한가? 또한 어느 쪽이 더 완전한 정렬 결과에 가까운 결과를 내는가?

답은 둘다 a-sort이다. 값이 작을수록 SWAP이 빈번하게 발생하기 때문이고 그에 따른 작업량이 많아진다. 1-sort가 완전 정렬결과를 내는것을 생각해보면된다.

따라서 h-sort는 h가 원소 n보다 작아야된다.

h는 뛰어넘어 정렬할 횟수이고 n은 배열로 치면 칸개수 임으로 (h<n)이다.

h가 n보다 큰 경우는 정렬을 할수없다!

 

 

 

 

Shell Sort 

h를 점진적으로 1까지 감소시켜 가며 h-sort를 수행하며 완정 정렬을 시킴(h-sort + Insertion의 활용방안이라고 볼수있다.)

따라서 13-Sort는 n에 비례한 시간복잡도를 가지고있고 4-sort 나 1-sort도 동일한 ~n 시간복잡도를 가지고 있다.

Q)Shell Sort 의 h-sort여러번 수행할때 h의 값은 어떻게 선정해야될까?라는 의문이 생긴다

답은 Donald Knuth가 제안한 방법. 다음 h를 계산하기 쉬운 편이며, 성능도 괜찮음Donald Knuth가 제안한 방법. 다음 h를 계산하기 쉬운 편이며, 성능도 괜찮음 : 3x+1이다. x는 1대입->나온값4대입->13->40 이런식으로 정한다.

 

Q) N = 30이라면 h의 최댓값은 어떤 값이 되는가?

shell sort의 h-sort의 h값은 h = 3x+1 임으로 앞에서 말했듯이 N(정렬할모든칸개수)를 h(h만큼 뛰어넘어 정렬할 수)가 넘으면 안되는 한에서 최댓값을 기준으로 시작한다.

1->4->13->40(x)

1->4->13(o)

따라서 답은 13이다. h값은 13->4->1 순서대로 h-sort를 진행하여 나오는 완전정렬이 shell sort이다.

밑에 두개 문제는 위그림을 보며 풀어보길 바란다.P 19

[Q] 두 번째 while loop에서 h = h//3 (3으로 나눈 후 소수 점 아래 제외) 하면 Knuth의 수열 3x+1을 따르는 이유는?

[Q] 첫 while loop에서는 왜 “N을 넘지 않는” h의 최댓값을 구하는가? (h가 이보다 커지면 안되나?)

 

 

 

Shuffle (Shuffle Sort, Knuth’s Shuffle)

Shuffle Sort

입력 데이터의 각 원소에 대해 random 실수 발생

발생한 실수 값 key로 사용해 정렬

 

p22

Shuffle Sort을 알기전에 Shuffle부터 알고가자!

shuffle 이란? 입력데이터의 순서를 임의로 섞는것을 말한다. ->특히 대부분의 경우 uniformly random 하게 섞음

예: 입력이 [1, 2, 3, 4]라면 shuffle 결과 같은 확률로 아래 중 하나가 됨
[1,2,3,4] [1,2,4,3] [1,3,2,4] [1,3,4,2] [1,4,2,3] [1,4,3,2] [2,1,3,4] [2,1,4,3] [2,3,1,4] [2,3,4,1] [2,4,1,3] [2,4,3,1] [3,1,2,4] [3,1,4,2] [3,2,1,4] [3,2,4,1] [3,4,1,2] [3,4,2,1] [4,1,2,3] [4,1,3,2] [4,2,1,3] [4,2,3,1] [4,3,1,2] [4,3,2,1] =>24개

 

[Q] Uniform Random Shuffle 결과 순서 안 바뀔 수도 있는가? (예: shuffle([1,2,3,4]) = [1,2,3,4])

:yes 

[Q] 입력이 N개의 원소를 갖고 있다면 shuffle 결과 나올 수 있는 경우는 총 몇 가지인가? 또한 Uniformly random하게 섞는다면, 각각이 나올 확률은 무엇인가?

:개수는 N! ->ex) 4개 4*3*2*1

: 1/N!

 

[Q] 길이 N인 데이터를 shuffle해야 한다면 위 방법의 성능은 무엇에 비례하나? 이 방식은 효율적인가?

 

N!만큼 셔플을하고 한개를 랜덤으로 고르는 방식은 낭비라고 생각이들어서 나온것이

Shuffle Sort이다.

 

이제 Shuffle Sort에 대해 설명을 시작하겠다.

 

Knuth’s Shuffle (Uniformly Random, ????-time Shuffle)

p28

h-sort 만든사람이 Knuth’s Shuffle 도 만들었는데 이 방식은 a[0]부터 a[i]까지 균일하게 랜덤으로 shuffle 된다.

 

Knuth’s Shuffle
Iteration i 때 a[0]~a[i] 중 하나를 uniformly random하게 선정해 a[i]와 swap 

그 결과 a[0] ~ a[i]가 uniformly random하게 shuffle된 상태 됨

Knuth’s Shuffle은 결과는 왜 Uniformly Random한가? 

a[0]부터 a[i]까지 균일하게 랜덤으로 shuffle ->Iteration i 때 a[0]~a[i] 중 하나를 uniformly random하게 선정해 a[i]와 swap

 

그러면 여기서 질문이 존재한다

[Q] a[0]는 uniformly random 한가?

맞다 a[0]는 Iteration 0 때 원소가 쓰이기 때문에 셔플된 상태가 맞음

[Q] a[0]-a[1]은 uniformly random 한가?

shuffle된 상태가 맞다. 원소가 쓰이면 셔플된게 맞기때문이다.

 

그럼 Knuth’s Shuffle의 성능은 무엇에 비례할까?

[Q]Insertion sort는 왜 한번에 갈 자리까지 jump 하지 못하고 여러가지 비교/swap을 해야하는가?

로직이 왼쪽 원소와 비교를 하여 크지 않은 원소가 나올때 까지 swap 을 하기 때문이다.

[Q]각 interation 에서 몇번의 비교가 필요한가?

정확x -> 한번일것이다. interation i가 움직이기 때문에 현재부분에서는 한번 비교가 맞다.

[Q]각 interation 에서 몇번의 swap 이 필요한가?

swap은 interation i일때 랜덤한 원소를 뽑아 [랜덤원소]와 [interation i] 가 swap '1번' 일어난다.

 

 

 

Convex Hull (Tight boundary 찾기 위해 정렬 방법 적용)

 

가장 작은 경계 찾기

Convex (볼록한) Hull (껍데기) of a set of N points
Smallest polygon that covers all given points whose vertices are points in the set

N개 점 집합의 볼록(볼록한) 선체(껍데기)
집합에서 꼭짓점이 점인 주어진 점을 모두 포함하는 최소 다각형

Convex Hull이란?
N개 정점 전체 혹은 일부 사용해 만들 수 있는 다각형 중 정점 모두를 내부에 포함하면서 최소 정점으로 만들 수 있는 다각형

1.직선 상의 점은 포함하지 않음. 즉 모서리만 포함

2.Convex hull 이루는 점들을 반시계 방향 (counterclockwise)으로 출력

 

[Q] N개 점이 있을 때(>=3 이고 같은 직선 상에 있지 않음) convex hull에 포함되는 점의 개수는 최대 몇 개인가?

 

활용예시:

Polygon(다각형) 형태 장애물 있을 때 두 지점 s와 t 간 최단경로 찾기

평면 상에 N개의 점이 있을 때, 서로 거리가 가장 먼 두 점 찾기

 

convex hull  처음 선택 점 구하기

 

Graham's Scan

 

최저점으로부터 반시계방향 각도 순 연결->concave angle 만드는 점은 제외

[Q] 이 방법(Graham's Scan)에서 정렬은 언제 사용되나?

 

[Q] Graham's Scan에서 N개의 점이 있을때, 이 방법의 성능은 무엇에 비례하는가?

 

정리: Sort & Applications

 

Shell Sort: Insertion Sort를 넓은 간격 → 좁은 간격(jump) 순서로 적용함으로써 성능을 향상시킨 예 

- 이미 잘 정립된 알고리즘이라도 개선 여지 없는지 생각해 보자.

Shuffle
- 원소 수만큼 난수 발생 후 Sort
- Insertion Sort와 유사한 방식으로 한 원소 씩 추가해 가되, 랜덤한 위치에 추가

Convex Hull
- Sort를 활용해 tight한 boundary 찾기
- 처음에는 정렬과 관련 없어 보이지만, 정렬로 해결되는 문제
- 앞으로도 정렬이 문제를 더 효율적으로 해결하는데 도움 되는 상황인지 생각해 보자.

Sort의 적용 예 상당히 많음
이들은 Sort를 직접 활용하거나, Sort와 유사한 방법 활용하며

Sort의 성능이 방법의 성능에 큰 영향 미침