Sorting (1)

개념 요약

• Sorting algorithm
  : 배열의 요소를 특정 순서로 정렬하는 알고리즘
• 1) Permutation sort (순열 정렬)
  : 정렬된 입력을 찾을 때까지 순열을 생성한다.
• 2) Selection sort (선택 정렬)
  : 정렬되지 않은 배열에서 가장 작은 요소를 선택하고 해당 요소를 정렬되지 않은 배열의 시작에 배치한다.
• 3) Insertion sort (삽입 정렬)
  : 배열에서 정렬되지 않은 부분의 값이 선택되어 정렬된 부분의 올바른 위치에 배치된다.
• 4) Merge sort (합병 정렬)
  : 배열을 반으로 분할하여 각각 따로 정렬한 뒤 합병하여 정렬한다.

ch.1 34번 문제풀이

• 문제 : 아래 중첩 루프의 시간 복잡도 T(n) 구하기
  (어떤 양의 정수 k에 대해서 n이 2의 거듭제곱이라고 가정)

i = n;
while (i >= 1) {
	j = i;
	while (j <= n) {
		< body of the while loop> //Needs O(1)
		j = 2 * j;
	}
	i = floor(i /2);
}

• 풀이

• 기존 풀이

T(n) = (log2n + log n)/2 = O(log2n)

Birthday dataset에 sorting algorithm 적용하기

• Birthday dataset에서 생일 날짜를 보여주는 열을 변수에 저장한 후 해당 열을 배열로 변환한다 -> 이때 결측값은 0으로 채우며 생일 날짜가 저장된 배열에 각각의 정렬 알고리즘을 적용해본다.
  • bd_val : Birthday dataset에서 생일 날짜를 보여주는 열

• Permutation sort

def Permutation_sort(a):
    n = len(a)
    while (is_sorted(a) == False):
        n = len(a)
    	for i in range(0, n):
        	r = random.randint(0, n-1)
        	a[i], a[r] = a[r], a[i]

def is_sorted(a):
    n = len(a)
    for i in range(0, n-1):
        if (a[i] > a[i+1]):
            return False
    return True

Permutation_sort(bd_val)

• Selection sort

def Selection_sort(array, size):
    for i in range(size):
        min_idx = i
        for j in range(i+1, size):
            if array[j] < array[min_idx]:
                min_idx = j
        (array[i], array[min_idx]) = (array[min_idx], array[i])

size = len(bd_val)
Selection_sort(bd_val, size)

• Insertion sort

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

Insertion_sort(bd_val)

• Merge sort

def Merge_sort(array):
    if len(array) > 1:
        r = len(array)//2
        L = array[:r]
        M = array[r:]
        mergeSort(L)
        mergeSort(M)
        i = j = k = 0
        while i < len(L) and j < len(M):
            if L[i] < M[j]:
                array[k] = L[i]
                i += 1
            else:
                array[k] = M[j]
                j += 1
            k += 1
        while i < len(L):
            array[k] = L[i]
            i += 1
            k += 1
        while j < len(M):
            array[k] = M[j]
            j += 1
            k += 1

Merge_sort(bd_val)

-> 각 정렬 알고리즘의 코드를 실행한 결과 생일 날짜가 오름차순으로 정확히 정렬되었다. 효율성을 고려하기 위한 각 정렬 알고리즘의 시간복잡도는 다음과 같다.