Assignments 4

1. 선형 시간 복잡도를 갖는 중앙값 찾기 알고리즘은 다음과 같이 작동합니다.

1. 배열을 크기가 5인 부분배열로 분할합니다.
2. 각 부분배열의 중앙값을 찾아 새로운 배열에 추가합니다.
3. 위 과정을 반복하여 크기가 5보다 작은 부분배열이 생길 때까지 수행합니다.
4. 새로운 배열에서 중앙값을 재귀적으로 찾습니다.

 

이 알고리즘의 시간 복잡도는 각 부분배열에서 중앙값을 찾는데 O(1)의 시간이 소요되므로, 분할된 부분배열의 개수에 비례하는 O(n)의 시간이 소요됩니다. 따라서 전체적인 시간 복잡도는 O(n)입니다.

파이썬으로 구현한 코드는 다음과 같습니다.

def linear_median_find(arr):
    n = len(arr)
    if n == 1:
        return arr[0]
    medians = []
    i = 0
    while i < n:
        j = min(i + 5, n)
        sub_arr = arr[i:j]
        sub_arr.sort()
        medians.append(sub_arr[len(sub_arr) // 2])
        i += 5
    pivot = linear_median_find(medians)
    left = [x for x in arr if x < pivot]
    right = [x for x in arr if x > pivot]
    k = len(left)
    if k == n // 2:
        return pivot
    elif k < n // 2:
        return linear_median_find(right)
    else:
        return linear_median_find(left)

위 코드는 재귀적으로 중앙값을 찾는 함수 linear_median_find을 구현한 것입니다. medians 리스트에는 각 부분배열의 중앙값을 저장하고, 이 중앙값들 중에서 재귀적으로 중앙값을 찾아 pivot 변수에 저장합니다. left 리스트와 right 리스트에는 각각 pivot보다 작은 원소와 큰 원소를 저장하며, 이를 이용하여 재귀적으로 중앙값을 찾습니다.

 

2. 해시 함수에서 계수 a가 0이 되어서는 안 되는 이유는 충돌을 방지하기 위해서입니다

해시 함수는 키 값과 연관된 해시 값을 계산하는 함수입니다. 해시 값은 일반적으로 배열의 인덱스로 사용되며, 계수 a는 해시 함수에서 사용되는 상수입니다. 계수 a가 0이 되면, 모든 키의 해시 값이 0이 되기 때문에 충돌이 발생할 확률이 매우 높아집니다. 즉, 서로 다른 키들이 같은 해시 값에 매핑되어 충돌이 발생할 가능성이 크게 증가합니다.

따라서 계수 a는 0이 아닌 임의의 값을 가져야 합니다.

파이썬 코드로 해시 함수를 구현해 보겠습니다. 계수 a를 랜덤한 값으로 지정하여 충돌을 최소화하는 해시 함수를 만들어 봅시다.

위 코드에서 key는 해시 함수의 인자로 전달되는 키 값이며, size는 해시 테이블의 크기입니다. random.randint(1, size-1)는 1부터 size-1까지의 랜덤한 값을 계수 a로 사용합니다. key와 a를 곱한 후 size로 나누어 나머지 값을 반환하면, key의 해시 값이 나오게 됩니다.

 

3. Basic quick sort (7번에 모든 알고리즘 한 번에 구현 하는 부분이 있음)

Basic quick sort는 Pivot으로 첫 번째 또는 마지막 값을 선택하여 정렬하는 방식입니다. Pivot 값보다 작은 값들은 Pivot 왼쪽으로, 큰 값들은 Pivot 오른쪽으로 옮겨지게 됩니다. 이 과정은 Pivot 값이 배열의 정 가운데 위치하게 될 때까지 반복적으로 수행됩니다.

 

• Pivot으로 배열의 가장 왼쪽 값을 선택한다.
  pivot을 기준으로 큰 값은 오른쪽으로, 작은 값은 왼쪽으로 옮긴다.
  왼쪽, 오른쪽 배열에 대해 같은 과정을 반복한다.
  재귀적으로 호출되며, 원소의 개수가 1 이하일 경우 종료한다.

def basic_quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    left = []
    right = []

    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])

    return basic_quick_sort(left) + [pivot] + basic_quick_sort(right)

4.  Intelligent Quick Sort

Intelligent quick sort는 Pivot 값으로 배열의 중앙값(median)을 선택하여 정렬하는 방식입니다. Pivot 값이 가운데 위치하게 되므로, 배열이 균등하게 분할되어 더욱 효율적으로 정렬할 수 있습니다.

• Pivot으로 배열의 중간 값을 선택한다.
• pivot을 기준으로 큰 값은 오른쪽으로, 작은 값은 왼쪽으로 옮긴다.
• 왼쪽, 오른쪽 배열에 대해 같은 과정을 반복한다.
• 재귀적으로 호출되며, 원소의 개수가 1 이하일 경우 종료한다.

def intelligent_quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = []
    right = []

    for i in range(len(arr)):
        if i != len(arr) // 2:
            if arr[i] < pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])

    return intelligent_quick_sort(left) + [pivot] + intelligent_quick_sort(right)

5. Paranoid Quick Sort

Paranoid quick sort는 Pivot 값으로 "E(Good choice)"를 선택하여 정렬하는 방식입니다. E(Good choice)란, Pivot 값을 선택하기 위한 다양한 기준을 결합한 결과물로, Pivot 값을 균등하게 선택하기 위한 목적으로 만들어진 값입니다.

 

• Pivot으로 배열의 최소값, 최대값, 중간값 3개를 선택한다.
• 이 중 중간값(median)을 pivot으로 선택한다.
• pivot을 기준으로 큰 값은 오른쪽으로, 작은 값은 왼쪽으로 옮긴다.
• 왼쪽, 오른쪽 배열에 대해 같은 과정을 반복한다.
• 재귀적으로 호출되며, 원소의 개수가 1 이하일 경우 종료한다.

def paranoid_quick_sort(arr):
    if len(arr) <= 1:
        return arr

    a, b, c = arr[0], arr[len(arr) // 2], arr[len(arr) - 1]
    pivot = a if (b <= a <= c or c <= a <= b) else b if (a <= b <= c or c <= b <= a) else c
    left = []
    right = []

    for i in range(len(arr)):
        if i != arr.index(pivot):
            if arr[i] < pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])

    return paranoid_quick_sort(left) + [pivot] + paranoid_quick_sort(right)

6. Tuple Sort

Tuple sort는 생일을 (월, 일)의 형태로 변환하여 정렬하는 알고리즘입니다. 이는 생일 데이터를 다룰 때 가장 직관적이며, 알고리즘의 구현도 매우 간단합니다. 두 가지 방식 중 하나를 선택하여 구현할 수 있습니다.

The month comes first, and the date second

The date comes first, and the month second

이 알고리즘의 구현은 다음과 같습니다.

def tuple_sort(arr, option=1):
    if option == 1:
        return sorted(arr, key=lambda x: (x.split('/')[0], x.split('/')[1]))
    elif option == 2:
        return sorted(arr, key=lambda x: (x.split('/')[1], x.split('/')[0]))

 

7. 한 번에 알고리즘 구현

# 데이터셋 생성
n = 100
birthdays = generate_birthday(n)

# Basic quick sort
def quick_sort_basic(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = []
    right = []
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quick_sort_basic(left) + [pivot] + quick_sort_basic(right)

# Intelligent quick sort
def quick_sort_intelligent(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = []
    right = []
    for i in range(len(arr)):
        if i == len(arr)//2:
            continue
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quick_sort_intelligent(left) + [pivot] + quick_sort_intelligent(right)

# Paranoid quick sort
def quick_sort_paranoid(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[random.randint(0, len(arr)-1)]
    left = []
    right = []
    for i in range(len(arr)):
        if arr[i] == pivot:
            continue
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quick_sort_paranoid(left) + [pivot] + quick_sort_paranoid(right)

# Tuple sort (month comes first)
def tuple_sort_month_first(arr):
    return sorted(arr, key=lambda x: (x[0], x[1]))

# Tuple sort (date comes first)
def tuple_sort_date_first(arr):
    return sorted(arr, key=lambda x: (x[1], x[0]))

8. Compare the sorting algorithms

import time

# 생일 데이터셋 불러오기
with open("birthday.txt") as f:
    data = f.read().splitlines()

# Set으로 중복 제거 및 정렬
birthday_set = sorted(list(set(data)))

# Basic Quick Sort
def basic_quick_sort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return basic_quick_sort(less) + [pivot] + basic_quick_sort(greater)

start_time = time.time()
basic_quick_sort(birthday_set)
print("Basic Quick Sort 실행 시간: %s seconds" % (time.time() - start_time))

# Intelligent Quick Sort
def intelligent_quick_sort(array):
    if len(array) < 2:
        return array
    else:
        # Pivot을 중간값으로 설정
        pivot = array[len(array)//2]
        less = [i for i in array if i < pivot]
        equal = [i for i in array if i == pivot]
        greater = [i for i in array if i > pivot]
        return intelligent_quick_sort(less) + equal + intelligent_quick_sort(greater)

start_time = time.time()
intelligent_quick_sort(birthday_set)
print("Intelligent Quick Sort 실행 시간: %s seconds" % (time.time() - start_time))

# Paranoid Quick Sort
def paranoid_quick_sort(array):
    if len(array) < 2:
        return array
    else:
        # Pivot을 무작위로 설정
        import random
        pivot = random.choice(array)
        less = [i for i in array if i < pivot]
        equal = [i for i in array if i == pivot]
        greater = [i for i in array if i > pivot]
        return paranoid_quick_sort(less) + equal + paranoid_quick_sort(greater)

start_time = time.time()
paranoid_quick_sort(birthday_set)
print("Paranoid Quick Sort 실행 시간: %s seconds" % (time.time() - start_time))

# Tuple Sort - 월이 먼저인 경우
def tuple_sort1(array):
    return sorted(array, key=lambda x: (int(x.split('/')[0]), int(x.split('/')[1])))

start_time = time.time()
tuple_sort1(birthday_set)
print("Tuple Sort (월이 먼저인 경우) 실행 시간: %s seconds" % (time.time() - start_time))

# Tuple Sort - 일이 먼저인 경우
def tuple_sort2(array):
    return sorted(array, key=lambda x: (int(x.split('/')[1]), int(x.split('/')[0])))

start_time = time.time()
tuple_sort2(birthday_set)
print("Tuple Sort (일이 먼저인 경우) 실행 시간: %s seconds" % (time.time() - start_time))