정렬 알고리즘 (시간복잡도 비교)

이진탐색	순차탐색	합병정렬, 퀵정렬, 힙정렬	버블정렬, 삽입정렬, 선택정렬 / 쉘정렬
O(logn)	O(n)	O(nlogn)	O(n2) / O(n1.25)

 

분할과 정복 알고리즘

>> 문제의 입력을 2/n으로 분할하고, 이를 다시 합병하여 문제를 해결하는 방식

 

이진탐색 O(logn)

>> 탐색범위의 중간부터 시작하여, 비교를 통해 절반의 숫자를 제거하는 방식으로,

문제가 2개로 분화되나, 그중 한개는 정렬할 필요가 없으며, 부분문제의 크기가 1/2로 감소하는 알고리즘

 

합병정렬 O(nlogn)

>> 문제의 입력을 2개의 부분문제로 분할, 부분문제의 크기가 1/2로 감소, 분할 정복 후 합병하는 방식

문제가 a로 분할되고, 부분문제의 크기가 1/b로 감소하는 알고리즘

 

퀵정렬 O(nlogn)

>> 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식

문제가 2개로 분할되고, 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

 

힙정렬 O(nlogn)

>> 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방식

 

버블정렬 O(n2)

>> 이웃한 두개의 원소를 비교하여 순서가 서로 다르면 원소의 자리를 서로 바꾸고, 

그렇지 않으면 그 위치에 그대로 놓음

int i, j, temp;
for(i=0; i < n-1; i++)
    for(j=0; i < n-i-1; j++)
        if(array[j] > array[j+1]) {
            temp = array[j];
            array[j] = array[j+1]
            array[j+1] = temp;
        }

 

선택정렬 O(n2)

>> 가장 작은 데이터를 '선택'해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법

문제를 2개로 분할하고, 2개는 관여하지 않으며, 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

 

삽입정렬 O(n2)

>> 데이터를 앞에서부터 하나씩 확인하며, 데이터를 적절한 위치에 '삽입'하는 방법

부분문제의 크기가 1, 2개씩 감소하는 알고리즘

def ins_sort(a):
    n = len(a):
    for i in range(1, n):
        key = a[i]
        j = i-1
        while j>=0 and a[j] > key:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = key

d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)

 

쉘정렬 O(n1.5)

>> 간격 h를 설정하여, 그룹을 만들어 정렬을 수행하다가 마지막에는 삽입정렬을 수행하는 방식

def shell_sort(a):
    h = 4
    while h >= 1:
        for i in range(h, len(a)):
            j = i
            while (j>=h) and a[j-h] > a[j]:
                a[j], a[j-h] = a[j-h], a[j]
                j -= h
            h //= 3
a = [55, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
print('정렬 전:\t', end = '')
print(a)
shell_sort(a)
print('정렬 후:\t', end = '')
print(a)

 

계수정렬 O(N + K)

>> 데이터의 크기 한정되어 있는 경우에만 사용가능하지만, 매우 빠르게 동작함.

특정한 값을 가지는 데이터의 개수를 '카운트'하는 방법