파이썬 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

Python2 를 설치과정을 살펴보도록 하겠습니다.

파이썬 홈페이지 : https://www.python.org/downloads/ 로 접속하여 아래 그림에서 'Download Python 2.7.11' 버튼을 클릭하여 설치해줍니다.

설치과정입니다. next를 눌러서 설치를 진행합시다.

Python을 설치할 디렉토리 경로를 설정하는 부분입니다. 따로 상관없다면 next를 계속 눌러주어 설치를 진행하면 됩니다.

파이썬 라이브러리와 인터프리터를 설치해주는 부분입니다. next로 진행합니다.

설치과정입니다. 기다리면 됩니다.

설치가 마무리되면, 아래 화면이 뜨고, finish를 눌러서 마쳐주면 설치가 완료됩니다.

시작메뉴로 들어가면, Python2.7버전이 설치된 것을 확인할 수 있습니다. 다음에서 IDLE 창을 눌러서 실행해주면 됩니다.

파이썬 IDLE창으로 실행된 화면입니다. 이상으로 파이썬 설치를 마칠 수 있습니다.