[알고리즘2] Sorting (Shell Sort, Shuffle Sort, Convex Hull)

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶Contents

• Insertion Sort
• h-Sort
• Shell Sort
• Shuffle Sort
• Convex Hull (Tight boundarry 찾기 위해 정렬 방법 적용)

 

▶Insertion Sort

• 이미 정렬된 a[0] ~ a[i-1]에 a[i]를 적절한 위치 (정렬되었을 때의 위치) 찾아 추가한다.
• 그 결과 a[0] ~ a[i]까지 정렬된 상태가 된다.

입력 데이터의 상태	대소 비교 횟수	swap 횟수
(best case) 이미 정렬된 상태	N - 1	0
(worst case) 반대 방향으로 정렬된 상태	~N^2 / 2	~N^2 / 2
(average case) 각 원소를 절반 정도 이동시켜야 하는 상태	~N^2 / 4	~N^2 / 4

 

▶h-Sort

• 모든 h만큼 떨어진 원소끼리 정렬된 상태로 만든다.
  • 이때 insertion sort방식을 이용한다.
• Shell Sort에서 사용하는 기본 operation이 h-Sort이다.

def hInsertionSort(a, h):
	for i in range(h, len(a)):
		key = a[i]
		j = i-h
		while j>=0 and a[j] > key:
			a[j+h] = a[j]
			j -= h
		a[j+h] = key

728x90

def insertionSort(a): 
	for i in range(1, len(a)):
		key = a[i] 
		j = i-1
		while j>=0 and a[j] > key:
			a[j+1] = a[j]
			j -= 1
		a[j+1] = key

h-sort와 insertion sort를 비교해보면,

insertion sort는 1칸씩 이동하는데 h-sort는 h칸씩 이동하면서 비교한다.

최종적으로는 1-sort를 수행해 완전히 정렬된 상태로 만들어야 한다.

• h-sort에서 h값은 어떻게 선정해야 하나?
  • 2^k : 1 ← 2 ← 4 ← 8 ← 16 ← 32 ← ...
    • 홀짝끼리 각각만 정렬되기에 좋지 않다.
  • 2^k - 1 : 1 ← 3 ← 7 ← 15 ← 31 ← 63 ← ...
    • 2^k와 같은 문제는 없다.
  • 3x + 1 : 1 ← 4 ← 13 ← 0 ← 121 ← 364
    • Donald Knuth가 제안한 방법
    • 다음 h를 계산하기 쉬운 편이며, 성능도 괜찮다.
  • 1 ← 5 ← 19 ← 41 ← 109 ← 209 ← ...
    • R.Sedgewick 교수가 제안한 방법
    • 지금까지 보인 수열 중에 성능이 가장 나은 편이다.

 

▶Shell Sort

def shellSort(a):
	N = len(a)
	h = 1
	while h < N/3:
		h = 3*h + 1 # Knuth's Sequence 1, 4, 13, 40, ...
	while h >= 1: 
		hInsertionSort(a, h)
		h = h//3

• Shell Sort의 성능 분석: 아직 정확한 수학적 모델을 찾지는 못했다.
• 각 h-sort가 실험적으로 ≤ cN회 (c는 작은 정수) 비교/swap 하는 걸로 보였으나 정확한 수학적 모델은 찾지 못했다.
• h = 3x + 1을 사용하는 경우 ~logN 회의 h-sort 수행한다.
• 따라서 ~NlogN 회의 비교/swap을 수행할 것으로 예측된다.

▶Shuffle Sort

• Shell Sort

import random

def shuffleSort(a):
	# Generate a random real number for each entry in a[]
	r = []
	for _ in range(len(a)):
		r.append(random.random())
	# Sort according to the random real number
	return [i for i, _ in sorted(zip(a,r), key=lambda x: x[1])]

 

• Knuth's Shuffle
  • Iteration i 때 a[0]~a[i] 중 하나를 uniformly random 하게 선정해 a[i]와 swap
  • 그 결과 a[0] ~ a[i]가 uniformly random 하게 shuffle 된 상태이다.

import random

def knuthShuffle(a):
	for i in range(1, len(a)):
		j = random.randint(0,i) # Randomly select a position among 0 ~ i
		a[i], a[j] = a[j], a[i] # Swap a[i], a[j]

 

▶Convex Hull

• Convex (볼록한) Hull (껍데기) of a set of N points:
• 집합의 꼭짓점이 점인 모든 주어진 점을 덮는 가장 작은 다각형

• convex hull 활용 예
  • Robot Motion Planning
    • Polygon(다각형) 형태 장애물 있을 때 두 지점 s와 t 간 최단 경로 찾기
  • Farthest Pair 찾기
    • 평면 상에 N개의 점이 있을 때, 서로 거리가 가장 먼 두 점 찾기
• convex hull에 대해 알아야 할 성질
  • 반시계 방향 순서로 포함할 점 선택
  • 최저점과 각도 순으로 선택
    • y값이 가장 작은 점을 p라고 둔다.
    • p로부터의 각도가 증가하는 순으로 점을 골라서 파악한다.

첫 번째 방법 : 반시계 방향 turn 반복 + 각도 순으로 선택

y값 가장 작은 점 p에서 시작해 반시계 방향 각도 가장 작은 점으로 연결
마지막에 a → b 순서로 선택했다면 b로부터 a-b 라인과 반시계 방향 각도 가장 작은 점으로 연결

두 번째 방법 : Graham's Scan

y값 가장 작은 점 p에서 시작해 다른 모든 점과의 반시계 방향 각도 계산
각도가 작은 점 순으로 차례로 연결해 보며 새로운 점 연결할 때마다 아래 수행

마지막에 i→j→k 순으로 연결했다면 i-j선 기준으로 볼 때 j-k가 반시계 방향의 turn이 아니라면
(즉 i-j-k가 convex 아닌 concave angle을 만든다면)
j는 잘못 연결된 것으로 보고 convex hull에서 제외 (즉 i-k 직접 연결)
더는 제외할 점 없을 때까지 마지막 세 점의 concave 여부 확인 반복

 

▶정리 : Sort & Applications

• Shell Sort
  • Insertion Sort를 넓은 간격 → 좁은 간격 순서로 적용함으로써 성능을 향상시킨 예
• Shuffle
  • 원소 수만큼 난수 발생 후 Sort
  • Insertion Sort와 유사한 방식으로 한 원소 씩 추가해 가되, 랜덤한 위치에 추가
• Convex Hull
  • Sort를 활용해 tight한 boundary 찾기
• 이들은 Sort를 직접 활용하거나, Sort와 유사한 방법 활용하며 Sort의 성능이 방법의 성능에 큰 영향 미친다.