정렬 알고리즘

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 알고리즘 내용입니다

목차

• 정렬
• 정렬의 종류
• 정렬 시간복잡도 비교
• 1. 2차 정렬 - 삽입, 선택, 버블
• 2. 선형 정렬 - 카운트 
• 3. 로그 선형 정렬 - sort()와 sorted(), 병합 정렬, 퀵, 힙

 

<정렬>

정렬

정렬이란, 순서없이 나열된 자료를 특정한 키값에 따라 오름차순이나 내림차순으로 자료를 재배열하는 것을 의미한다. 정렬은 자료 탐색에 있어 필수적이다. 

 

정렬의 종류

• 비교 정렬 : 원소들을 정렬할 때 원소들의 순서에만 의존하는 알고리즘. ex) 선택, 버블, 삽입, 퀵, 힙, 병합 정렬 등.
• 비비교 정렬 : ex) 버킷, 계수, 기수 정렬
• 안정 정렬 : 동일한 값에 대해 기존의 순서가 유지되는 정렬 방식 ex) 삽입, 버블, 병합
• 불안정 정렬 : 동일한 값에 대해 기존의 순서가 뒤바뀔 수 있는 정렬 방식
• 내부 정렬 : 정렬하고자 하는 모든 데이터가 메모리에 올라와 정렬이 수행되는 방식
• 외부 정렬 : 정렬하고자 하는 데이터가 너무 크기 때문에 일부만 올려놓은 상태에서 정렬한 것을 다시 합하는 방식
• 제자리 정렬 : 주어진 공간 외에 추가적인 공간을 사용하지 않는 정렬

 

정렬 시간복잡도 비교

 

1. 2차 정렬

1.1) 삽입 정렬 - 안정

• 배열 맨 처음 정렬된 부분에 정렬되지 않은 다음 항목을 반복적으로 삽입하는 방식
• 리스트가 이미 정렬되어 있다면 병합, 퀵 정렬 보다 성능이 좋음.
• 구현이 간단함.
• 값의 양이 길어질수록 효율이 극악으로 떨어짐.

import random   # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5)   # 1<= x < 11의 난수 5개 리스트로 생성
print(a)   # 정렬 전 리스트
print('')
for i in range(1, len(a)):  # 리스트의 크기만큼 반복
    for j in range(i, 0, -1):  # j 인덱스의 값이 줄어드면서 삽입할 위치를 찾을 때까지 반복
        if a[j] < a[j-1]:  # 현재 인덱스가 앞의 원소보다 작다면
            a[j], a[j-1] = a[j-1], a[j]  # swap해서 값 뒤로 밀어내기
        else : break   # 불필요한 반복을 피하기 위해 break
print('')
print(a)   # 정렬 후 리스트 출력

#출력
[8, 9, 3, 1, 6]


[1, 3, 6, 8, 9]

 

1.2) 선택 정렬 - 불안정

• 나보다 작은 항목을 선택하고 자기자리로 바꾸는 정렬.
• 각 회전 단계마다 다음으로 작은 값을 찾아서 이를 올바른 위치에 갖다 놓는 방식.

import random    # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5)    # 1<= x < 10의 난수 5개 리스트로 생성
print(a)    # 정렬 전 리스트
print('')
for i in range(len(a)-1):    # 리스트의 크기-1만큼 반복
    for j in range(i+1, len(a)):    # 해당 인덱스+1부터, 리스트 크기만큼 반복
        if a[i] > a[j]:    # 인덱스의 값이 비교 인덱스보다 더 크다면
            a[i] , a[j]  = a[j], a[i]    # swap 해주기
print('')
print(a)   # 정렬 후 리스트

#출력
[8, 4, 7, 2, 3]


[2, 3, 4, 7, 8]

 

1.3) 버블 정렬 - 안정

모든 원소를 하나하나 비교하여 swap 하는 작업을 반복하는 방식.

import random   # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5)     # 1<= x < 10의 난수 5개 리스트로 생성
print(a)    # 정렬 전 리스트
print('')
for i in range(1, len(a)):     # 리스트의 크기만큼 반복
    for j in range(0, len(a)-1):     # 각 회전당 정렬이 끝나지 않은 친구들을 위해 반복
        if a[j] > a[j+1]:     # 현재 인덱스의 값이 다음 인덱스의 값보다 크면 실행
           a[j+1], a[j] = a[j], a[j+1]     # swap해서 위치 바꾸기
print('')
print(a)     # 정렬 후 리스트

#출력
[4, 9, 2, 5, 7]


[2, 4, 5, 7, 9]

 

2. 선형 정렬

2.1) 카운트 정렬(계수 정렬) - 안정

• 요소들을 비교하지 않고 요소들의 개수를 세어서 정렬하는 방식.
• 작은 범위의 정수 그리고 중복된 값이 많이 분포되어있는 배열을 정렬할 때 효과적이고 빠름.
• 비교 정렬은 두 원소를 집어 비교를 해야 하기 때문에 O(n log n)이상이 필요하지만 카운트 정렬은 비교 정렬이 아니기 때문에 O(k + n)이라는 획기적인 속도를 낼 수 있음. 여기서 k는 원소들의 값의 range크기
• 양의 정수에 대해서만 적용 가능

import random     # random 메소드 사용을 위해 import

def counting_sort(arr, size, m):
    count = [0 for _ in range(m)]
    tmp = [0 for _ in range(size)]

    for x in arr:
        count[x] += 1

    for x in range(1, m):
        count[x] += count[x - 1]

    for x in range(size - 1, -1, -1):
        count[arr[x]] -= 1
        tmp[count[arr[x]]] = arr[x]

    return tmp

def main():
    m = 5
    size = 20
    arr = [random.randrange(m) for _ in range(size)]
    print('정렬전 :', arr)
    print('정렬후 :', counting_sort(arr, size, m))

if __name__ == '__main__':
    main()

 

3. 로그 선형 정렬

3.1) sort()와 sorted()

• sort() - 원본 리스트 자체를 정렬
• sorted() - 정렬된 새로운 리스트를 반한

 

3.2) 병합 정렬(합병, 머지 정렬) - 안정

• 리스트를 두 부분으로 쪼개서 작은 값부터 하나하나 병합하는 방식.
• 배열이 큰 경우 효율적임.
• 재귀함수를 이용해서 구현할 수 있으며, 데이터 크기만큼의 스택 메모리가 필요함.
• 병합 정렬의 분할 및 병합 과정

병합정렬 구현의 여러가지 경우

가) pop메서드를 사용하여 구현

나) 제자리 정렬을 구현

다) 정렬된 파일을 병합하는 경우

가) pop()메서드를 사용하여 다음과 같이 구현할 수 있다.
   (각 두 배열은 정렬되어 있다.)
def merge(left, right):
   if not left or not right: return left or right # 아무것도 병합하지 않는다.
   result = []
   while left and right:
       if left[-1] >= right[-1]:
           result.append(left.pop())
       else:
           result.append(right.pop())
   result.reverse()
   return (left or right) + result
>>> l1 = [1, 2, 3, 4, 5, 6, 7]
>>> l2 = [2, 4, 5, 8]
>>> merge(l1, l2)
[1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8]


나) 제자리 정렬을 구현하는 경우, 한 배열의 끝에 0이 채워져 있고,
    다른 배열에는 첫 배열에서 끝에 0이 채워진 크기만큼의 요소가 있다.
   (각 두 배열은 정렬되어 있다.)
>>> l1 = [1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0]
>>> l2 = [2, 4, 5, 8]
>>> merge_two_arrays_inplace(l1, l2)
[1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8]


다) 정렬된 파일은 다음과 같이 병합(파일을 로딩할 충분한 RAM이 필요).
>>> list_files = ["1.dat", "2.dat", "3.dat"]
>>> merge_files(list_files)
[1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8]

병합 정렬 구현 5가지 방법

1) pop()을 이용한 병합 정렬
def merge_sort(seq):
    if len(seq) < 2:
        return seq
    mid = len(seq) // 2
    left, right = seq[:mid], seq[mid:]
    if len(left) > 1:
        left = merge_sort(left)
    if len(right) > 1:
        right = merge_sort(right)

    res = []
    while left and right:
        if left[-1] >= right[-1]:
            res.append(left.pop())
        else:
            res.append(right.pop())
    res.reverse()
    return(left or right) + res


2) 두 함수로 나누어서 구현한다. 한 함수에서는 배열을 나누고, 또 다른 함수에서는 배열을 병합한다.
def merge_sort_sep(seq):
    if len(seq) < 2:
        return seq
    mid = len(seq) // 2
    left = merge_sort_sep(seq[:mid])
    right = merge_sort_sep(seq[mid:])
    return merge(left, right)
def merge(left, right):
    if not left or not right:
        return left or right
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    if left[i:]:
        result.extend(left[i:])
    if right[j:]:
        result.extend(right[j:])
    # print(result)
    return result


3) 각 두 배열은 정렬된 상태다. 시간복잡도는 O(2n)이다.
def merge_2n(left, right):
    if not left or not right:
        return left or right
    result = []
    while left and right:
        if left[-1] >= right[-1]:
            result.append(left.pop())
        else:
            result.append(right.pop())
    result.reverse()
    return (left or right) + result


4) 제자리 정렬로 구현한다.
def merge_two_arrays_inplace(l1, l2):
    if not l1 or not l2:
        return l1 or l2
    p2 = len(l2) - 1
    p1 = len(l1) - len(l2) - 1
    p12 = len(l1) - 1
    while p2 >= 0 and p1 >= 0:
        item_to_be_merged = l2[p2]
        item_bigger_array = l1[p1]
        if item_to_be_merged < item_bigger_array:
            l1[p12] = item_bigger_array
            p1 -= 1
        else:
            l1[p12] = item_to_be_merged
            p2 -= 1
        p12 -= 1
    return l1


5) 파일을 병합한다.
def merge_files(list_files):
    result = []
    final = []
    for filename in list_files:
        aux = []
        with open(filename, "r") as file:
            for line in file:
                aux.append(int(line))
        result.append(aux)
    final.extend(result.pop())
    for l in result:
        final = merge(l, final)
    return finaldef test_merge_sort():
    seq = [3, 5, 2, 6, 8, 1, 0, 3, 5, 6, 2]
    seq_sorted = sorted(seq)
    assert(merge_sort(seq) == seq_sorted)  # 1
    assert(merge_sort_sep(seq) == seq_sorted)  # 2

    l1 = [1, 2, 3, 4, 5, 6, 7]
    l2 = [2, 4, 5, 8]
    l_sorted = [1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8]
    assert(merge_2n(l1, l2) == l_sorted)  # 3
    l1 = [1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0]
    l2 = [2, 4, 5, 8]
    l_sorted = [1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8]
    assert(merge_two_arrays_inplace(l1, l2) == l_sorted)  # 4
    list_files = ["a.dat", "b.dat", "c.dat"]
    l_sorted = [1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8]
    assert(merge_files(list_files) == l_sorted)  # 5
    print("테스트 통과!")

if __name__ == "__main__":
    test_merge_sort() 

3.3) 퀵 정렬 - 불안정

• 리스트에서 기준이 되는 하나의 요소인 피벗. 피벗 앞에는 피벗보다 작은 값, 뒤에는 피벗보다 큰  값이 오도록 피벗을 기준으로 리스트를 둘로 나누는 방식.
• 피벗을 잘 선택하는 것이 성능의 핵심이다.
• 재귀 함수를 통해 구현됨.
• 데이터양이 n배 많아 진다면, 실행 시간은 n배 보다 조금 더 많아진다.
• 퀵 정렬 분할 및 병합 과정

퀵 정렬 구현 3가지 방법

1) 한 함수로 구현한다(캐시 사용).
2) 1)의 퀵 정렬을 두 함수로 나누어 구현한다(캐시 사용).

3) 두 함수로 나누어서 구현한다(캐시 사용 안 함)

 

퀵 정렬 구현

1) 한 함수로 구현한다(캐시 사용).
def quick_sort_cache(seq):
    if len(seq) < 2:
        return seq
    ipivot = len(seq) // 2  # 피벗 인덱스
    pivot = seq[ipivot]  # 피벗
    before = [x for i, x in enumerate(seq) if x <= pivot and i != ipivot]
    after = [x for i, x in enumerate(seq) if x > pivot and i != ipivot]
    return quick_sort_cache(before) + [pivot] + quick_sort_cache(after)


2) 1)의 퀵 정렬을 두 함수로 나누어 구현한다(캐시 사용).
def partition_devided(seq):
    pivot, seq = seq[0], seq[1:]
    before = []
    after = []
    before = [x for x in seq if x <= pivot]
    after = [x for x in seq if x > pivot]
    return before, pivot, after

def quick_sort_cache_devided(seq):
    if len(seq) < 2:
        return seq
    before, pivot, after = partition_devided(seq)
    return quick_sort_cache_devided(before) \
        + [pivot] \
        + quick_sort_cache_devided(after)


3) 두 함수로 나누어서 구현한다(캐시 사용 안 함)
def partition(seq, start, end):
    pivot = seq[start]
    left = start + 1
    right = end
    done = False
    while not done:
        while left <= right and seq[left] <= pivot:
            left += 1
        while left <= right and pivot < seq[right]:
            right -= 1
        if right < left:
            done = True
        else:
            seq[left], seq[right] = seq[right], seq[left]
    seq[start], seq[right] = seq[right], seq[start]
    # print(right, seq)
    return right

def quick_sort(seq, start, end):
    if start < end:
        pivot = partition(seq, start, end)
        quick_sort(seq, start, pivot - 1)
        quick_sort(seq, pivot + 1, end)
    return seqdef test_quick_sort():
    seq = [3, 5, 2, 6, 8, 1, 0, 3, 5, 6, 2]
    assert(quick_sort_cache(seq) == sorted(seq))
    assert(quick_sort_cache_devided(seq) == sorted(seq))
    assert(quick_sort(seq, 0, len(seq)-1) == sorted(seq))
    print("테스트 통과!")

if __name__ == "__main__":
    test_quick_sort() 

 

3.4) 힙 정렬

• 정렬되지 않은 영역이 힙이라는 점을 제외하면 선택 정렬과 비슷함.
• 파이썬의 내장 heapq 모듈을 사용하여 모든 값을 힙에 push한 다음. 한 번에 하나씩 가장 작은 값을 pop하여 구현할 수 있음.

1) 다른 라이브러리 사용하지 않고 힙 정렬 구현
def heap_sort3(seq):
    for start in range((len(seq)-2)//2, -1, -1):
        siftdown(seq, start, len(seq)-1)
    for end in range(len(seq)-1, 0, -1):
        seq[end], seq[0] = seq[0], seq[end]
        siftdown(seq, 0, end - 1)
    return seq

def siftdown(seq, start, end):
    root = start
    while True:
        child = root * 2 + 1
        if child > end:
            break
        if child + 1 <= end and seq[child] < seq[child + 1]:
            child += 1
        if seq[root] < seq[child]:
            seq[root], seq[child] = seq[child], seq[root]
            root = child
        else:
            break

def test_heap_sort():
    seq = [3, 5, 2, 6, 8, 1, 0, 3, 5, 6, 2]
    assert(heap_sort3(seq) == sorted(seq))
    print("테스트 통과!")

if __name__ == "__main__":
    test_heap_sort() 
  
  
2) heapq 모듈 사용해 구현
import heapq

def heap_sort1(seq):
    h = []
    for value in seq:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

def test_heap_sort1():
    seq = [3, 5, 2, 6, 8, 1, 0, 3, 5, 6, 2]
    assert(heap_sort1(seq) == sorted(seq))
    print("테스트 통과!")

if __name__ == "__main__":
    test_heap_sort1()