Problem Set 4

Assignments 4

1.      Describe linear median finding algorithm. Show that its time complexity is Θ(n).
2.      In hashing function, why the coefficient a should not be 0?
3.      Read chapter 8.4. Solve example 8.1 in the chapter.
4.      Use the birthday dataset, do the followings:
4.1. Put them into your unsorted array using set.
4.2. Order them with the birth day. You should consider the following algorithms.
- Basic quick sort
Pivot X = A[0] or A[n-1]
- Intelligent quick sort
Pivot X = median of A
-Paranoid quick sort
Pivot X = E(Good choice)
-Tuple sort
1)The month comes first, and the date second
2) The date comes first, and the month second
4.3. Compare the sorting algorithms
 
 
 
 
 
 
 

1. linear median finding algorithm을 설명하고 시간복잡도가 O(n)인 이유를 설명해라.

 
1) 입력 배열이 n개라면 원소 5개짜리 (n/5)그룹으로 나눈다.
 
2) 각 그룹에서 중앙값(_m)을 찾는다.
 
3) 이제 중앙값들의 중앙값을 찾아야 한다. 그런데 어차피 이것도 중앙값을 찾는 문제이다. 따라서 select()를 한 번 재귀호출한다. m = select(M, M/2);
  *M은 _m들로 이루어진 집합(배열)을 의미한다.
  *M/2를 넘기므로 개수가 짝수일 경우 내림 되어 m은 더 앞에 있는 중앙값이 된다.
 
4) (x=m) x를 기준으로 x보다 큰 원소는 s1그룹, x보다 작은 원소는 s2그룹으로 분할한다.
 
5) 분할 정복으로 해결한다.
  *중간값 찾는 경우 k = n/2가 된다.
 
이 알고리즘의 시간 복잡도는 n개의 숫자를 순회하면서 각 숫자마다 비교하고 나누기 때문에 O(n)이다.

 

1. 배열의 모든 요소를 한 번씩 순회하는 과정에서 각 요소를 한 번씩 접근해야 합니다. 이는 O(n)의 시간이 소요됩니다.

 
 
 

2.해싱 함수에서 계수 a가 0이 아니어야 하는 이유는 무엇인가?

 
 
만약, 해싱 함수에서 계수a가 0이 되면 해시충돌이 발생할 수 있다.  해시충돌이 계속 발생하면 메모를 효율적으로 사용할 수 없기 때문에 계수 a가 0이 되면 안된다.

 

해싱 함수에서 계수 a가 0이 아니어야 하는 이유는 해시 충돌을 피하기 위해서입니다.

해시 함수는 입력 데이터를 해시 값으로 변환하는 함수로, 해시 충돌은 서로 다른 입력 데이터가 동일한 해시 값으로 매핑되는 상황을 의미합니다. 해시 충돌이 발생하면 해시 테이블에서 데이터를 검색하거나 삽입하는 과정에서 정확성과 성능 문제가 발생할 수 있습니다.

만약 계수 a가 0이라면 해시 함수는 모든 입력 데이터에 대해 항상 동일한 해시 값을 반환하게 됩니다. 이는 모든 입력 데이터가 동일한 해시 버킷에 매핑되어 충돌이 빈번하게 발생할 것입니다. 이는 해시 테이블의 성능을 저하시키고, 데이터의 검색 또는 삽입 속도를 느리게 만들 수 있습니다.

계수 a가 0이 아닌 경우, 해시 함수는 입력 데이터의 특성을 잘 반영하여 서로 다른 입력 데이터를 서로 다른 해시 값으로 매핑할 수 있습니다. 이는 해시 충돌의 가능성을 줄이고, 해시 테이블의 성능을 향상시킵니다.

따라서 해싱 함수에서 계수 a가 0이 아니어야 하는 이유는 해시 충돌을 피하기 위해서입니다. 계수 a는 일반적으로 0이 아닌 소수로 선택됩니다.

 
 
 

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

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

 
 
 
 
 

4. 생일 dataset을 이용하여 다음을 해결해라.

4-1. 집합을 사용하여 정렬되지 않은 배열에 넣어라. 

import pandas as pd

df = pd.read_csv('Birthday.csv')
Birthday_set = set(df['Birthday'])

Birthday_list = list(Birthday_set)

 
 

4-2, 4-3

<Basic quick sort>

import pandas as pd

df = pd.read_csv('Birthday.csv')
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left, equal, right = [], [], []
    for x in arr:
        if x < pivot:
            left.append(x)
        elif x == pivot:
            equal.append(x)
        else:
            right.append(x)
    return quick_sort(left) + equal + quick_sort(right)
Birthday_list = quick_sort(list(df['Birthday']))

시간 복잡도는 O(nlogn)이고 최악의 경우 O(n^2)이다
 
 

<Intelligent quick sort>

import pandas as pd
def introsort(array, depth_limit):
    n = len(array)
    if n <= 1:
        return array
    elif depth_limit == 0:
        return sorted(array)
    else:
        pivot = array[0]
        left = []
        right = []
        equal = []
        for item in array:
            if item[1] < pivot[1]:
                left.append(item)
            elif item[1] > pivot[1]:
                right.append(item)
            else:
                if item[0] < pivot[0]:
                    left.append(item)
                elif item[0] > pivot[0]:
                    right.append(item)
                else:
                    equal.append(item)
        left = introsort(left, depth_limit-1)
        right = introsort(right, depth_limit-1)
        return left + equal + right

df = pd.read_csv('Birthday.csv')
array = df[['name', 'Birthday']].values.tolist()
sorted_array = introsort(array, depth_limit=2)
sorted_df = pd.DataFrame(sorted_array, columns=['name', 'Birthday'])
print(sorted_df)

 

<Paranoid quick sort>

import pandas as pd
def insertion_sort(array):
    for i in range(1, len(array)):
        j = i - 1
        key = array[i]
        while j >= 0 and array[j][1] > key[1]:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = key
    return array
def paranoid_quick_sort(array, depth_limit):
    n = len(array)
    if n <= 1:
        return array
    elif n <= 16:
        return insertion_sort(array)
    elif depth_limit == 0:
        return sorted(array, key=lambda x: x[1])
    else:
        mid = n // 2
        if array[0][1] > array[mid][1]:
            array[0], array[mid] = array[mid], array[0]
        if array[mid][1] > array[-1][1]:
            array[mid], array[-1] = array[-1], array[mid]
        if array[0][1] > array[mid][1]:
            array[0], array[mid] = array[mid], array[0]
        pivot = array[mid]
        left = []
        right = []
        equal = []
        for item in array:
            if item[1] < pivot[1]:
                left.append(item)
            elif item[1] > pivot[1]:
                right.append(item)
            else:
                if item[0] < pivot[0]:
                    left.append(item)
                elif item[0] > pivot[0]:
                    right.append(item)
                else:
                    equal.append(item)
        left = paranoid_quick_sort(left, depth_limit-1)
        right = paranoid_quick_sort(right, depth_limit-1)
        return left + equal + right

df = pd.read_csv('Birthday.csv')
array = df[['name', 'Birthday']].values.tolist()
sorted_array = paranoid_quick_sort(array, depth_limit=16)
sorted_df = pd.DataFrame(sorted_array, columns=['name', 'Birthday'])
print(sorted_df)

Paranoid Quick Sort는 일반적인 퀵 정렬(Quick Sort) 알고리즘의 변형입니다. 퀵 정렬은 분할 정복(divide and conquer) 방법을 사용하여 배열을 정렬하는 빠른 정렬 알고리즘 중 하나입니다.

Paranoid Quick Sort는 퀵 정렬의 단점 중 하나인 최악의 경우 시간 복잡도가 O(n^2)가 되는 경우를 피하기 위해 개발되었습니다. 이 알고리즘은 일반적인 퀵 정렬의 성능을 개선하고 안정성을 높이는 목적으로 고안되었습니다.

Paranoid Quick Sort의 동작은 다음과 같습니다:

배열에서 피벗(pivot)을 선택합니다. 피벗은 일반적으로 배열의 가장 오른쪽 요소를 선택합니다.
배열을 피벗을 기준으로 두 개의 부분 배열로 분할합니다. 왼쪽 부분 배열에는 피벗보다 작거나 같은 요소가 포함되고, 오른쪽 부분 배열에는 피벗보다 큰 요소가 포함됩니다.
왼쪽 부분 배열과 오른쪽 부분 배열에 대해 재귀적으로 Paranoid Quick Sort를 호출합니다.
정렬된 부분 배열을 병합하여 최종 정렬된 배열을 얻습니다.
Paranoid Quick Sort의 핵심 아이디어는 분할 과정에서 피벗을 중복하여 처리하는 것입니다. 일반적인 퀵 정렬에서는 피벗과 같은 값을 가진 요소들이 분할 과정에서 서로 교환되지만, Paranoid Quick Sort에서는 피벗과 같은 값을 가진 요소들을 오른쪽 부분 배열로 보내지 않고 왼쪽 부분 배열에 계속 남겨둡니다. 이렇게 함으로써 피벗과 같은 값의 요소들이 오른쪽 부분 배열로 모이는 상황을 방지하고, 최악의 경우에도 시간 복잡도가 O(n^2)가 되지 않도록 합니다.

Paranoid Quick Sort의 시간 복잡도는 평균적으로 O(n log n)입니다. 이는 분할 과정이 평균적으로 균형적인 분할을 수행하기 때문입니다. 최악의 경우에도 O(n log n)의 성능을 보장하기 때문에, Paranoid Quick Sort는 안정적이고 효율적인 정렬 알고리즘 중 하나로 알려져 있습니다.
 
<Tuple sort>
 

import pandas as pd

df = pd.read_csv('Birthday.csv')
tuples = [(row['name'], row['id'], tuple(map(int, row['birthday'].split('.')))) for _, row in df.iterrows()]
sorted_tuples = sorted(tuples, key=lambda x: (x[2][0], x[2][1]))
for t in sorted_tuples:
    print(t)

 

import pandas as pd

df = pd.read_csv('birthday.csv')
tuples = [(row['name'], row['id'], tuple(map(int, reversed(row['Birthday'].split('/'))))) for _, row in df.iterrows()]
sorted_tuples = sorted(tuples, key=lambda x: x[2])
for t in sorted_tuples:
    print(t)

 
첫번째 원소를 기준으로 오름차순 or 내림차순 출력하는 알고리즘