4-7. 포지션 리스트로 삽입 정렬 구현하기

1-2. 시간 복잡도 분석

삽입 정렬을 처음 다룬 게시글이다. 안 봐도 무방.

 

1. 포지션 리스트로 삽입 정렬 문제 풀어보기

• 워크(walk): 마커부터 첫 번째 노드 방향으로 이동한 것. 워크 앞 노드와 피봇을 비교한다.
• 피봇(pivot): 마커의 다음 노드로, 정렬해야 할 대상
• 마커(marker): 정렬된 리스트의 가장 오른쪽 노드

워크, 피봇, 마커

2. insertion_sort

def insertion_sort(L):
	"""Sort PositionalList of comparable elements into nondecreasing order."""
	if len(L) > 1:						# otherwise, no need to sort it
		marker = L.first()
		while marker != L.last():
			pivot = L.after(marker)			# next item to place
			value = pivot.element()
			if value > marker.element():		# pivot is already sorted
				marker = pivot			# pivot becomes new marker
			else:
				walk = marker			# find leftmost item greater than value
				while walk != L.first() and L.before(walk).element() > value:
					walk = L.before(walk)
				L.delete(pivot)
				L.add_before(walk, value)	# reinsert value before walk

---

1) 피봇은 마커의 다음 노드로 설정

 

1번 과정 도식화

• 인자로 받은 L은 포지션 리스트
• 리스트의 길이가 1인 경우에는 별도로 처리하지 않음
• 마커는 첫번째 노드에서 마지막 노드로 이동
• 피봇은 마커의 다음 노드로 설정

def insertion_sort(L):
	"""Sort PositionalList of comparable elements into nondecreasing order."""
	if len(L) > 1:						# otherwise, no need to sort it
		marker = L.first()
		while marker != L.last():
			pivot = L.after(marker)			# next item to place
			value = pivot.element()

 

2) 피봇이 마커보다 크면 정렬된 상태로 생각하고 마커를 피봇으로 이동

2번 과정 도식화

• 피봇이 이미 정렬된 경우 마커를 피봇 위치로 이동

			if value > marker.element():		# pivot is already sorted
				marker = pivot			# pivot becomes new marker

 

3) 워크는 마커부터 시작해 앞으로 이동하면서 워커의 이전 요소와 피봇을 비교

 그림과 같은 상황에서 워크가 25 지점에 도달하면 워크의 이전 요소인 22가 피봇 23보다 작으므로 워크 이동이 중단.

3번 도식화

• 워크를 이동하며 워커의 이전 요소와 피봇을 비교
• 워커의 이전 요소가 피봇보다 크면 앞으로 이동
• 워커의 이전 요소가 피봇보다 작으면 이동을 중단

			else:
				walk = marker			# find leftmost item greater than value
				while walk != L.first() and L.before(walk).element() > value:
					walk = L.before(walk)

 

4) 워크의 이전 요소가 피봇보다 크면 피봇을 워크 앞에 삽입

 피봇이 정렬된 상태가 되었으므로 정렬된 범위의 길이가 1 늘어남

4번 과정 도식화

• 리스트에서 피봇을 삭제한 후 워크 앞에 삽입

				L.delete(pivot)
				L.add_before(walk, value)	# reinsert value before walk

 

3. insertion_sort의 시간 복잡도

배열로 구현한 삽입 정렬 알고리즘에서 삽입 부분은 개선되었지만 비교하는 과정은 동일하다.

INSERTION-SORT(A)			# 주의: index가 1부터 시작되는 것으로 가정되어 있음

for j = 2 to A:length			# 피봇이 하나씩 이동하는 것은 동일
	key = A[j]
	// Insert A[j] into the sorted sequence A[1 .. j - 1]
	i = j - 1
	while i > 0 and A[i] > key	# 피봇과 이전 값을 비교하는 과정도 동일
		A[i + 1] = A[i]
		i = i - 1		# 피봇을 삽입하기 위해 배열 요소를 한 칸씩 미루는 과정은 없어짐.
	A[i + 1] = key

INSERTION-SORT(A)					# cost: times

for j = 2 to A:length					# c1: n
	key = A[j]					# c2: n-1
	// Insert A[j] ~				# 0: n-1
	i = j - 1					# c4: n-1
	while i > 0 and A[i] > key			# c5: σ 𝑗=2 to n tj (tj = j)
		A[i + 1] = A[i]				# c6: σ 𝑗=2 to n (tj-1) (tj = j)
		i = i - 1				# c7: σ 𝑗=2 to n (tj-1) (tj = j)
	A[i + 1] = key					# c8: n-1

 

결과적으로 시간 복잡도는 O(n^2)으로 개선되지 않았다.

 

연결 리스트 정리가 끝났다. 다음 게시물부터는 트리에 대해 다룬다.

중간고사 범위 마지막 파트...!!!!