정렬 알고리즘

• In-place sort ? 정렬 과정에서 입력 데이터를 저장하기 위해 필요한 메모리 공간 외에, 상수 크기의 메모리 공간만을 사용한다. 즉, 데이터 갯수 n에 비례하는 공간차지를 하지 않는다.
• Time complexity? 설명읽기

비교 기반 정렬 알고리즘

1. Insertion sort

Concept : unsorted list의 숫자 하나를 sorted list내에서 적절한 위치에 삽입.

def insertion_sort(input):

    n = len(input)
    for j in range(1,n,1):
        key = input[j]
        i = j-1

        while i>=0 and input[i]>key:
            input[i+1] = input[i]
            i = i-1
        input[i+1] = key

In-place : Yes (swap memory만 필요)

Time Complexity : best case O(n) / worst case O(n²) / average case O(n²)

2. Bubble sort

Concept : unsorted list를 전체를 앞뒤비교해가며 정렬.

def bubble_sort(input):

    n = len(input)
    for i in range(0,n,1):
        for j in range(n-1,i,-1):
            if input[j] < input[j-1]:
                temp = input[j]
                input [j] = input[j-1]
                input[j-1] = temp

In-place : Yes (swap memory만 필요)

Time Complexity : best case O(n) / worst case O(n²) / average case O(n²)

best case에서 O(n)이 되려면 for j in range(n-1,i,-1): 루프에서 swap여부를 체크하여 없는 경우에 바로 종료해야함, 이런 구현이 없으면 사실상 O(n²)임.

3. Selection sort

Concept : unsorted list에서 가장 작은 값을 sorted에 포함.

def selection_sort(input):

    n= len(input)

    for i in range(0,n,1):
        min = input[i]
        min_index = i

        for j in range(i+1,n,1):
            if min > input[j]:
                min = input[j]
                min_index = j

        temp = input[i]
        input[i] = min
        input[min_index] = temp

In-place : Yes

Time Complexity : best case O(n²) / worst case O(n²) / average case O(n²)

이미 정렬이 되어있는 best case에서도 unsorted에서 가장 작은값을 찾기 위해서 n번을 찾아야하고 이 Iteration을 최소 n-1번 반복해야하므로 best case에서도 O(n²)

4. Merge sort

Concept : 분할정복 방식, 쪼개진 부분이 각각 정렬되어있다면 합치는 과정만 해주면 된다.

def merge_sort(input):
    if len(input)<2:
        return input

    mid = len(input)//2
    low_arr = merge_sort(input[:mid])
    high_arr = merge_sort(input[mid:])

    merged_arr = []
    l=h=0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l]< high_arr[h]:
            merged_arr.append(low_arr[l])
            l+=1
        else:
            merged_arr.append(high_arr[h])
            h+=1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

In-place : No (N만큼의 공간이 더 필요)

Time Complexity : best case O(nlogn) / worst case O(nlogn) / average case O(nlogn)

5. Quick sort

Concept : pivot을 기준으로 왼쪽은 더 작은값, 오른쪽은 더 큰값으로 쪼개기

def partition(input,l,r):
    pivot =input[l]
    pivot_loc = l
    l = l+1

    while True:
        while(input[l]<pivot and l<=len(input)):
            l = l+1
        while(input[r]>pivot and r>=0):
            r = r-1

        if l>r:
            temp = input[r]
            input[r] = pivot
            input[pivot_loc] = temp
            return r
        else:
            temp = input[l]
            input[l] = input[r]
            input[r] = temp

def quick_sort(input,l,r):
    if r>l:
        q = partition(input,l,r)
        quick_sort(input,l,q-1)
        quick_sort(input,q+1,r)

In-place : Yes (swap memory만 필요)

Time Complexity : best case O(nlogn) / worst case O(n²) : pivot을 계속해서 최악으로 뽑아서 가장 낮은 수를 뽑는 경우 / average case O(nlogn)

• Randomized Quicksort : pivot을 랜덤한 위치에서 뽑는다. 이 경우 평균적으로 O(nlogn)에 수렴하는 성능을 보임.

Lower Bounds of Sorting

• 비교기반 정렬알고리즘은 n!의 가능한 순서를 다룬다. 이를 binary search tree로 다루려면 최소 높이는 2^h ≥ n!이 되어야한다.
• h≥ log n! = ∑ log i ≥ ∑ log n/2 ≥ (n+1)/2 * log n/2 = Ω(n log n)

1. Counting Sort

Concept : n개의 value가 0에서 k 사이의 값을 가진다는 사실과 k=O(n)일때, k개의 슬롯 값의 갯수를 카운트해서 정렬하는 방식 Θ(n)에 정렬 가능

방법 : 1) 새로운 배열을 만들고 각 값마다 갯수를 카운트 , 2) 누적해서 sum , 3) 원래 배열에서 해당값의 위치를 새로운 배열에서 찾고 (2) , 4) 해당 위치에 삽입하고 카운트를 -1, 5) 반복

2. Radix Sort

Concept : 가능한 자리수를 알고 있을때, 각 자리수마다 하나하나 정렬하는 방식. n개의 d-digit number가 주어졌을때, Θ(d(n+k)) time에 정렬 가능