파이썬 Merge Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(nlogn)

(CASE 1)

def mergeSort(A):

    left = []

    right = []

    if len(A) > 1:

        mid = len(A) / 2

        for l in range(0, mid, 1):

            left.append(A[l])

        for r in range(mid, len(A), 1):

            right.append(A[r])

        mergeSort(left)

        mergeSort(right)

        i=j=k=0

        while i < len(left) and j < len(right):

            if left[i] < right[j]:

                A[k]=left[i]

                i += 1

            else:

                A[k]=right[j]

                j += 1

            k += 1

        while i < len(left):

            A[k]=left[i]

            i += 1

            k += 1

        while j < len(right):

            A[k]=right[j]

            j += 1

            k += 1

if __name__ == '__main__':

    A= [1, 8, 6, 10, 4, 5, 3, 22]

    mergeSort(A)

    print A

(CASE 2)

def merge_sort(A, first, last):

    mid = 0

    if first < last:

        mid = (first + last) / 2

        merge_sort(A, first, mid)

        merge_sort(A, mid+1, last)

        merge(A, first, last)

def merge(A, first, last):

    temp = []

    mid = (first + last) / 2

    i = first

    j = mid + 1

    k = 0

    while i <= mid and j <= last:

        if A[i] <= A[j]:

            temp.append(A[i])

            i += 1

        else:

            temp.append(A[j])

            j += 1

    if i > mid:

        for t in range(j, last+1):

            temp.append(A[t])

    else:

        for t in range(i, mid+1):

            temp.append(A[t])

    for t in range(first, last+1, 1):

        A[t] = temp[k]

        k += 1

if __name__ == '__main__':

    A= [1, 8, 6, 10, 4, 5, 3, 22]

    merge_sort(A, 0, len(A)-1)

    print A

파이썬 Heap Sort로 내림차순으로 정렬하는 방식입니다.

시간복잡도 : O(nlogn)

def heapify(A, n, k):

    while 2*k+1 < n:

        L = 2*k+1

        R = 2*k+2

        if A[k] > A[L]:

            m = L

        else:

            m = k

        if R < n and A[m] > A[R]:

            m = R

        if k != m:

            A[k], A[m] = A[m], A[k]

            k = m

        else:

            break

def make_heap(A):

    for k in range(len(A)/2, -1, -1):

        heapify(A, len(A), k)

def heapSort(A):

    make_heap(A)

    n = len(A)

    for k in range(len(A)-1):

        A[0], A[n-1] = A[n-1], A[0]

        n = n-1

        heapify(A, n, 0)

if __name__ == '__main__':

    A = [3, 10, 7, 9, 8, 5, 12, 21, 4, 15]

    heapSort(A)

    print A

파이썬 Heap Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(nlogn)

def heapify(A, n, k):

    while 2*k+1 < n:

        L = 2*k+1

        R = 2*k+2

        if A[k] < A[L]:

            m = L

        else:

            m = k

        if R < n and A[m] < A[R]:

            m = R

        if k != m:

            A[k], A[m] = A[m], A[k]

            k = m

        else:

            break

def make_heap(A):

    for k in range(len(A)/2, -1, -1):

        heapify(A, len(A), k)

def heapSort(A):

    make_heap(A)

    n = len(A)

    for k in range(n-1):

        A[0], A[n-1] = A[n-1], A[0]

        n -= 1

        heapify(A, n, 0)

if __name__ == '__main__':

    A = [3, 10, 7, 9, 8, 5, 12, 21, 4, 15]

    heapSort(A)

    print A

파이썬 Selection Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(n^2)

def selectionSort(A):

    for i in range(len(A)):

        minValue = i

        for j in range(i+1, len(A)):

            if A[j] < A[minValue]:

                minValue = j

        A[minValue], A[i] = A[i], A[minValue]

if __name__ == '__main__':

    A = [4, 1, 5, 8, 6, 2, 3, 7, 10]

    selectionSort(A)

    print A

파이썬 Insertion Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(n^2)

def insertionSort(A):

    for i in range(1, len(A)):

        temp = A[i]

        j = i

        while j > 0 and A[j-1] > temp:

            A[j] = A[j-1]

            j -= 1

        A[j] = temp

if __name__ == '__main__':

    A = [4, 1, 5, 8, 6, 2, 3, 7, 10]

    insertionSort(A)

    print A

파이썬 Quick Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(n^2) - Worst Case 일 때 이지만,

일반적으로는 가장 빠른 정렬으로 시간복잡도를 O(nlogn) 으로 봅니다.

def quickSort(A, first, last):

    left = first + 1

    right = last

    if first >= last:

        return

    pivot = A[first]

    while left <= right:

        while left <= last and A[left] < pivot:

            left += 1

        while right > first and A[right] >= pivot:

            right -= 1

        if left <= right:

            A[left], A[right] = A[right], A[left]

            left += 1

            right -= 1

    A[right], A[first] = A[first], A[right]

    quickSort(A, first, right-1)

    quickSort(A, left, last)

if __name__ == '__main__':

    A = [4, 1, 5, 8, 6, 2, 3, 7, 10]

    quickSort(A, 0, len(A)-1)

    print A

파이썬 Bubble Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(n^2)

def bubbleSort(A):

    for i in range(len(A)):

        for j in range(1, len(A)):

            if A[j-1] > A[j]:

                A[j-1], A[j] = A[j], A[j-1]

if __name__ == '__main__':

    A = [1, 9, 2, 5, 4, 8, 15, 3]

    bubbleSort(A)

    print A

Algorithm 메뉴에 포스팅했던 백준 알고리즘 문제들에 대하여,

예전에 알고리즘을 처음 해보기 시작할 때 문제풀어보기에 급급히 작성했던 코드들이어서 

부족한 코드도, 수정해야하는 코드도 많은데 보완없이 그대로 올렸던 터라 많이 고쳐야 할 것 같습니다.

최근 블로그 활동을 많이 못하게 되었는데, 조만간 전체적인 코드 수정과 함께 

시간이 된다면 추가적으로 문제들을 더 올려보도록 노력하겠습니다.