Sorting

Sorting

---

Bubble

시간복잡도는 $O(N^2)$이다.
공간복잡도는 $O(1)$

def bubbleSort(n, a):
    cumulatedNumSwap = 0
    for i in range(0, n):
        numSwap = 0
        for j in range(0, n-1):
            if a[j] > a[j+1]:
                temp = a[j]
                a[j] = a[j+1]
                a[j+1] = temp
                numSwap += 1
        cumulatedNumSwap += numSwap
        if numSwap == 0:
            break
    return cumulatedNumSwap, a

if __name__ == "__main__":
    a = [2, 1, 3, 1, 2]
    numSwap, sortedA = bubbleSort(len(a), a)

    print("Array is sorted in %d swaps."%numSwap)
    print("First Element: %d"%sortedA[0])
    print("Last Element: %d"%sortedA[-1])

Insertion

Time Complexity:

• best: $O(n)$
• worst: $O(n^2)$
  Space Complexity: $O(1)$

간단한 삽입정렬

def InsertionSort(input):
    for i in range(len(input)-1):
        for j in range(i+1,len(input)):
            if(input[j] < input[i]):
                input[i], input[j] = input[j], input[i]
    return input

import random

def InsertionSort(input):

    for idx, valueToInsert in enumerate(input):
        # select the hole position where number is to be inserted
        holePosition = idx

        # check if previous no. is larger than value to be inserted
        while holePosition > 0 and input[holePosition-1] > valueToInsert:
            input[holePosition - 1], input[holePosition] = input[holePosition], input[holePosition-1]
            holePosition = holePosition - 1

    return input

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    InsertionSort(A)
    print(A)

실행결과

[84, 59, 97, 41, 6, 93, 80, 62, 19, 37, 83, 24, 86, 95, 46]
[6, 19, 24, 37, 41, 46, 59, 62, 80, 83, 84, 86, 93, 95, 97]

Selection

Time complexity: $O(n^2)$
Space complexity: $O(1)$

import random
def selectionSort(input):
    for i in range(len(input) - 1):
        # assume the min is the first element
        idx_min = i
        j = i + 1

        # test against elements after i to find the smallest
        while j < len(input):
            if(input[j] < input[idx_min]):
                # found new minimum; remember its index
                idx_min = j
            j = j + 1

        if idx_min is not i:
            # swap
            input[idx_min], input[i] = input[i], input[idx_min]

    return input

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    selectionSort(A)
    print(A)

실행결과

[72, 10, 31, 7, 51, 11, 97, 9, 45, 54, 35, 26, 61, 55, 13]
[7, 9, 10, 11, 13, 26, 31, 35, 45, 51, 54, 55, 61, 72, 97]

Merge

worst와 average모두 $O(n \log n)$인 엄청나게 좋은 알고리즘이다.
하지만 공간 복잡도는 $O(n)$을 메모리는 많이 사용 합니다.
그래도 기본적인 Dvide and Conquer를 적용한 알고리즘이기에 확실히 알고 넘어가면 좋다.

위키피디아에 나온 그림으로 나타낸 동작 방법은 아래와 같다.

$T(n)=2T\left(\frac{n}{2}\right)+n$
$\begin{aligned}
T(n)&=2\left(2T\left(\frac{n}{4}\right)+\frac{n}{2}\right)+n \newline
&=4T\left(\frac{n}{4}\right)+n+n\newline
&=…\newline
&\approx O(\underbrace{n+n+…+n}_{\log n})\newline
&=O(n\log n)
\end{aligned}$

코드는 아래와 같다.

import random

# Time Complexity O(nLogn)
# Space Complexity O(n)

def mergeSort(A):
    ### Base case ###

    if len(A) <= 1:
        return A

    ### A를 반으로 쪼개서 recursive call을 해 주고 정렬된 반쪽짜리들을 받아옵니다.
    left = mergeSort(A[:int(len(A)/2)])
    right = mergeSort(A[int(len(A)/2):])

    ### 여기서부터 두 개의 쪼개졌던 list를 합치는 Merge 부분입니다.
    ### 여기서 포인트는 정렬된 상태로 돌아왔기 때문에 앞에서부터 순차적으로 한번만 돌면 정렬시킬 수 있다는 것입니다.
    i, j, k = 0, 0, 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
    if i == len(left): #만약 left의 원소를 모두 채웠고, right가 남아있을 때.
        while j<len(right):
            A[k] = right[j]
            j += 1
            k += 1
    elif j == len(right): #만약 right의 원소를 모두 채웠고, left가 남아있을 때.
        while i<len(left):
            A[k] = left[i]
            i += 1
            k += 1
    return A #마지막으로 정렬된 list를 리턴합니다.

if __name__ == "__main__":

    A=[random.randint(1,100) for _ in range(10)]
    print("unsorted List:")
    print(A)
    print("Sorted List:")
    print(mergeSort(A))

실행결과

unsorted List:
[94, 22, 47, 26, 28, 29, 33, 53, 5, 54]
Sorted List:
[5, 22, 26, 28, 29, 33, 47, 53, 54, 94]

참고자료
https://smlee729.github.io/python/algorithm/2015/03/03/1-merge-sort.html

Quick

분할 정복 알고리즘으로 Sorting한다.
Merge Sort와 다르게 분할 할 때 복잡하고 병합할 때는 복잡하지 않다.

평균 시간 복잡도는 $O(nlogn)$이다. 메모리 측면에서 좀 더 효율 적이다. 따라서 실제로 동작하는 속도가 좀 더 빠르다.
$$T(n)\approx n+2T(\frac{n}{2})$$

하지만, 최악의 상황인 이미 정렬이 완료된 List를 정렬할 경우 $T(n)=n+T(n-1)$으로 분할 된다.
왜냐하면 pivot이 가장 큰 값이라면 left side는 n-1개가 존재하고 이 부분을 계속 quick sort로 recursive하게 호출이 발생하기 때문이다. 결국 $O(n^2)$의 복잡도를 가진다.

Pivot이 Median값이라면 merge sort와 같은 복잡도를 가진다. 최악의 경우를 피하는 방법은 통상 random choice를 이용한다.

import random

# 아까 말씀드렸다시피, pivot을 선택한 후에(parition 함수의 결과값으로 pivot의 최종 index가 나옵니다.) recursive call로 쪼갭니다.
def quicksort(A, start, end):
    if start < end:
        p = partition(A, start, end)
        quicksort(A, start, p - 1)
        quicksort(A, p + 1, end)


# 이제 pivot을 뽑는 과정을 알아봅시다.
def partition(A, start, end):
    pivot = end
    wall = start
    # 나머지 원소들은 A[hi]와 비교하면서 재정렬합니다.
    for i in range(start, end):
        if A[i] < A[pivot]:
            #swap
            A[i], A[wall] = A[wall], A[i]
            wall += 1
    A[pivot], A[wall] = A[wall], A[pivot] # 마지막으로 pivot을 자신보다 큰 원소들의 첫번째 원소와 바꿔줍니다. (전반부, 후반부를 나누기 위해서)
    return wall

if __name__ == "__main__":
    A = [random.randint(0, 100) for _ in range(15)]  # 임의로 0~100까지 15개 수를 뽑습니다.
    print(A)
    quicksort(A, 0, len(A)-1)
    print(A)