:)

Sorting (3) 본문

Algorithm

Sorting (3)

andre99 2024. 9. 11. 15:54
  1. linear median finding algorithm
    • 시간복잡도가 Θ(n)임을 보여주기
n<5 => T(n) ≤ c < 10*c < 10*c*n
T(n) ≤ c*n + T(n/5) + T(7n/10)
     ≤ c*n + 10*c*n/5 + 10*c*7n/10
     = c*n + 10*c*9n/10
     = 10*c*n
=> T(n) = Θ(n)
  1. hashing function에서 계수 a가 0이 아니어야 하는 이유
  • 계수 a가 0일 경우 데이터의 key값이 없어지기 때문에 0이 아니어야 한다.
  1. 예제 8.1 풀이
  • 만약 n개의 키가 m개의 바구니에 균일하게 분포되어 있고, 각 키가 검색 키가 될 확률이 거의 같다고 하면, 성공한 검색의 평균 비교 횟수는 다음과 같다.
n/2m + 1/2

만약 키가 균일하게 분포되어 있고 n=2m이라면, 실패한 검색은 각각 2m/m = 2번의 비교만 필요하고, 성공한 검색은 평균 비교 횟수가 다음과 같다.

2m/2m + 1/2 = 3/2

만약 모두 같은 바구니에 분포되어 있을 경우 순차검색과 유사하나 같은 바구니에 분포되어 있을 확률은 낮다. 키가 바구니에 균일하게 분포되어 있을 경우 좋은 해시 효과를 얻을 수 있다. 이분검색 알고리즘을 사용하여 효율적으로 검색을 수행할 수 있다.

  1. birthday dataset 활용하기
  • Birthday dataset에서 생일 날짜를 보여주는 열을 변수에 저장한 후 해당 열을 배열로 변환한다 -> 이때 결측값은 0으로 채우며 생일 날짜가 저장된 배열에 각각의 정렬 알고리즘을 적용해본다.
    • bd_val : Birthday dataset에서 생일 날짜를 보여주는 데이터프레임을 numpy 형태로 표현
    • bd_li : bd_val을 list 형태로 변환
    • tuple_li : float 형태의 생일 데이터를 문자열로 변경한 후 month와 date를 분리하여 튜플로 이루어진 리스트로 변환

4.1 unsorted array에 넣기

  • 코드
def unsorted_arr(arr, n, insert_val, pos) :
    for i in range(n-1,pos-1,-1) :
        arr[i + 1] = arr[i]
    arr[pos] = insert_val
arr = bd_val
n = 5
print("unordered array set에 넣기\n")
print("insert 전: ")
for i in range(0,n) :
    print(arr[i],end='\n')
x = 3.03
pos = 2
unsorted_arr(arr, n, x, pos)
n+=1
print("\ninsert 후: ")
for i in range(0,n) :
    print(arr[i],end='\n')
  • 실행 결과

4.2 다음 알고리즘을 고려하여 생일 날짜에 대해 정렬하기

  • Basic quick sort
    Pivot X = A[0] or A[n-1]
    • 코드 
      def partition(array, low, high):
	pivot = array[0]
	i = low - 1
	for j in range(low, high):
		if array[j] <= pivot:
			i = i + 1
			(array[i], array[j]) = (array[j], array[i])
	(array[i + 1], array[high]) = (array[high], array[i + 1])
	return i + 1
      def quick_sort(array, low, high):
	if low < high:
		pi = partition(array, low, high)
		quick_sort(array, low, pi - 1)
		quick_sort(array, pi + 1, high)
array = bd_li
quick_sort(array, 0, len(array) - 1)
print(array)
    • 실행 결과 
      [0.0, 0.0, 0.0, 12.31, 1.01, 1.09, 1.12, 1.14, 1.15, 1.17, 1.19, 1.19, 1.2, 1.2, 1.27, 1.28, 1.3, 2.02, 2.07, 2.07, 2.2, 2.22, 2.25, 3.03, 3.05, 3.09, 3.09, 3.1, 3.26, 3.28, 3.28, 4.02, 4.07, 4.11, 4.2, 4.25, 4.28, 4.28, 5.01, 5.12, 5.18, 5.18, 5.19, 5.22, 5.25, 5.29, 5.31, 6.03, 6.08, 6.09, 6.14, 6.16, 6.16, 6.2, 6.23, 7.02, 7.04, 7.06, 7.1, 7.19, 7.19, 8.02, 8.02, 8.12, 8.21, 8.23, 8.28, 9.02, 9.03, 9.05, 9.05, 9.07, 9.08, 9.13, 9.16, 9.25, 9.25, 9.27, 10.04, 10.12, 10.19, 10.19, 10.23, 10.25, 10.28, 10.29, 11.04, 11.15, 11.15, 11.21, 11.28, 11.29, 12.01, 12.04, 12.05, 12.16, 12.19, 12.21, 12.29, 12.29]
  • Intelligent quick sort
    Pivot X = median of A
    • 코드 
      import statistics as st
def partition(array, low, high):
	pivot = st.median(array)
	i = low - 1
	for j in range(low, high):
		if array[j] <= pivot:
			i = i + 1
			(array[i], array[j]) = (array[j], array[i])
	(array[i + 1], array[high]) = (array[high], array[i + 1])
	return i + 1
      def quick_sort(array, low, high):
	if low < high:
		pi = partition(array, low, high)
		quick_sort(array, low, pi - 1)
		quick_sort(array, pi + 1, high)
array = bd_li
quick_sort(array, 0, len(array) - 1)
print(array)
    • 실행 결과 
      [0.0, 0.0, 0.0, 1.01, 1.09, 1.12, 1.14, 1.15, 1.17, 1.19, 1.19, 1.2, 1.2, 1.27, 1.28, 1.3, 2.02, 2.07, 2.07, 2.2, 2.22, 2.25, 3.03, 3.05, 3.09, 3.09, 3.1, 3.26, 3.28, 3.28, 4.02, 4.07, 4.11, 4.2, 4.25, 4.28, 4.28, 5.01, 5.12, 5.18, 5.18, 5.19, 5.22, 5.25, 5.29, 5.31, 6.03, 6.08, 6.09, 6.14, 12.29, 12.31, 6.16, 6.16, 6.2, 6.23, 7.02, 7.04, 7.06, 7.1, 7.19, 7.19, 8.02, 8.02, 8.12, 8.21, 8.23, 8.28, 9.02, 9.03, 9.05, 9.05, 9.07, 9.08, 9.13, 9.16, 9.25, 9.25, 9.27, 10.04, 10.12, 10.19, 10.19, 10.23, 10.25, 10.28, 10.29, 11.04, 11.15, 11.15, 11.21, 11.28, 11.29, 12.01, 12.04, 12.05, 12.16, 12.19, 12.21, 12.29]
  • Paranoid quick sort
    Pivot X = E(Good choice)
    • 코드 
      import random
def partition(A, left_index, right_index):
   pivot = A[left_index]
   i = left_index + 1
   for j in range(left_index + 1, right_index):
       if A[j] < pivot:
           A[j], A[i] = A[i], A[j]
           i += 1
   A[left_index], A[i - 1] = A[i - 1], A[left_index]
   return i - 1
      def quick_sort_random(A, left, right):
   if left < right:
       pivot = random.randint(left, right - 1)
       A[pivot], A[left] = (A[left],A[pivot],)  
       pivot_index = partition(A, left, right)
       quick_sort_random(A, left, pivot_index) 
       quick_sort_random(A, pivot_index + 1, right) 
nums = bd_li
quick_sort_random(nums, 0, len(nums))
print(nums)
    • 실행 결과 
      [0.0, 0.0, 0.0, 1.01, 1.09, 1.12, 1.14, 1.15, 1.17, 1.19, 1.19, 1.2, 1.2, 1.27, 1.28, 1.3, 2.02, 2.07, 2.07, 2.2, 2.22, 2.25, 3.03, 3.05, 3.09, 3.09, 3.1, 3.26, 3.28, 3.28, 4.02, 4.07, 4.11, 4.2, 4.25, 4.28, 4.28, 5.01, 5.12, 5.18, 5.18, 5.19, 5.22, 5.25, 5.29, 5.31, 6.03, 6.08, 6.09, 6.14, 6.16, 6.16, 6.2, 6.23, 7.02, 7.04, 7.06, 7.1, 7.19, 7.19, 8.02, 8.02, 8.12, 8.21, 8.23, 8.28, 9.02, 9.03, 9.05, 9.05, 9.07, 9.08, 9.13, 9.16, 9.25, 9.25, 9.27, 10.04, 10.12, 10.19, 10.19, 10.23, 10.25, 10.28, 10.29, 11.04, 11.15, 11.15, 11.21, 11.28, 11.29, 12.01, 12.04, 12.05, 12.16, 12.19, 12.21, 12.29, 12.29, 12.31]
  • Tuple sort
    1) The month comes first, and the date second
    • 코드 
      import operator
def sort_tuples(tuples, key):
   return sorted(tuples, key=operator.itemgetter(key))
tuples = tuple_li
key = 0
print(sort_tuples(tuples, key))
    • 실행 결과 
      [('0', '0'), ('0', '0'), ('0', '0'), ('1', '01'), ('1', '09'), ('1', '12'), ('1', '14'), ('1', '15'), ('1', '17'), ('1', '19'), ('1', '19'), ('1', '2'), ('1', '2'), ('1', '27'), ('1', '28'), ('1', '3'), ('10', '04'), ('10', '12'), ('10', '19'), ('10', '19'), ('10', '23'), ('10', '25'), ('10', '28'), ('10', '29'), ('11', '04'), ('11', '15'), ('11', '15'), ('11', '21'), ('11', '28'), ('11', '29'), ('12', '01'), ('12', '04'), ('12', '05'), ('12', '16'), ('12', '19'), ('12', '21'), ('12', '29'), ('12', '29'), ('12', '31'), ('2', '02'), ('2', '07'), ('2', '07'), ('2', '2'), ('2', '22'), ('2', '25'), ('3', '03'), ('3', '05'), ('3', '09'), ('3', '09'), ('3', '1'), ('3', '26'), ('3', '28'), ('3', '28'), ('4', '02'), ('4', '07'), ('4', '11'), ('4', '2'), ('4', '25'), ('4', '28'), ('4', '28'), ('5', '01'), ('5', '12'), ('5', '18'), ('5', '18'), ('5', '19'), ('5', '22'), ('5', '25'), ('5', '29'), ('5', '31'), ('6', '03'), ('6', '08'), ('6', '09'), ('6', '14'), ('6', '16'), ('6', '16'), ('6', '2'), ('6', '23'), ('7', '02'), ('7', '04'), ('7', '06'), ('7', '1'), ('7', '19'), ('7', '19'), ('8', '02'), ('8', '02'), ('8', '12'), ('8', '21'), ('8', '23'), ('8', '28'), ('9', '02'), ('9', '03'), ('9', '05'), ('9', '05'), ('9', '07'), ('9', '08'), ('9', '13'), ('9', '16'), ('9', '25'), ('9', '25'), ('9', '27')]
      2) The date comes first, and the month second
    • 코드 
      def tuple_sort(tup):
   lst = len(tup)
   for i in range(0, lst):
       for j in range(0, lst-i-1):
           if (tup[j][1] > tup[j + 1][1]):
               temp = tup[j]
               tup[j] = tup[j + 1]
               tup[j + 1] = temp
   return tup
tup = tuple_li
print(tuple_sort(tup))
    • 실행 결과 
      [('0', '0'), ('0', '0'), ('0', '0'), ('1', '01'), ('5', '01'), ('12', '01'), ('2', '02'), ('4', '02'), ('7', '02'), ('8', '02'), ('8', '02'), ('9', '02'), ('3', '03'), ('6', '03'), ('9', '03'), ('7', '04'), ('10', '04'), ('11', '04'), ('12', '04'), ('3', '05'), ('9', '05'), ('9', '05'), ('12', '05'), ('7', '06'), ('2', '07'), ('2', '07'), ('4', '07'), ('9', '07'), ('6', '08'), ('9', '08'), ('1', '09'), ('3', '09'), ('3', '09'), ('6', '09'), ('3', '1'), ('7', '1'), ('4', '11'), ('1', '12'), ('5', '12'), ('8', '12'), ('10', '12'), ('9', '13'), ('1', '14'), ('6', '14'), ('1', '15'), ('11', '15'), ('11', '15'), ('6', '16'), ('6', '16'), ('9', '16'), ('12', '16'), ('1', '17'), ('5', '18'), ('5', '18'), ('1', '19'), ('1', '19'), ('5', '19'), ('7', '19'), ('7', '19'), ('10', '19'), ('10', '19'), ('12', '19'), ('1', '2'), ('1', '2'), ('2', '2'), ('4', '2'), ('6', '2'), ('8', '21'), ('11', '21'), ('12', '21'), ('2', '22'), ('5', '22'), ('6', '23'), ('8', '23'), ('10', '23'), ('2', '25'), ('4', '25'), ('5', '25'), ('9', '25'), ('9', '25'), ('10', '25'), ('3', '26'), ('1', '27'), ('9', '27'), ('1', '28'), ('3', '28'), ('3', '28'), ('4', '28'), ('4', '28'), ('8', '28'), ('10', '28'), ('11', '28'), ('5', '29'), ('10', '29'), ('11', '29'), ('12', '29'), ('12', '29'), ('1', '3'), ('5', '31'), ('12', '31')]

4.3 sorting algorithms 비교하기

  • Basic/Intelligent/Paranoid Quick sort & Tuple sort
    quick sort의 pivot을 선택하는 전략에 따라 달라진다.
    quick sort의 time complexity : O(nlogn)
    tuple sort의 time complexity : O(nlogn)

'Algorithm' 카테고리의 다른 글

Sorting (4)  (0) 2024.09.11
Sorting (2)  (0) 2024.09.11
Sorting (1)  (0) 2024.09.11
Birthday Problem  (0) 2024.09.11
'Algorithm' Related Articles more