정렬 알고리즘

버블 정렬 (bubble Sort)

버블 정렬은 뒤에서부터 앞으로 정렬을 진행하는 구조를 가지고 있다.
오름차순 정렬 기준으로 배열의 맨 뒷공간에 가장 높은 값을 보내고, 그 앞에 두 번째로 큰 값을 보낸다.
그래서 배열 내 값들을 앞뒤로 서로 비교하며 자리를 바꾸는 작업르 반복한다.

버블 정령은 큰 값들을 뒤에서부터 앞으로 하나씩 쌓아 나가기 때문에 원소가 자리를 잡을 때마다 정렬의 범위가 하니씩 줄어들게 도니다.
제일 작은 값을 찾아 맨 앞에 위치시키는 선택정렬과는 반대의 정렬 방향을 갖는다.
다른 정렬 알고리즘에 비하여 값의 swap이 비번하게 일어난다.
O(n^2)의 시간 복잡도를 갖는다. 루프문을 통해 모든 인덱스에 방문해야 하므로 O(N)의 시간이 소모되고 또 인접한 원소와 대소 비교 및 swap을 위하여 O(N)의 시간이 추가로 필요하기 때문이다

# 큰값을 하나씩 리스트 맨뒤로 정렬
def bubbleSort(lst):
    # 최댓값을 구하는 알고리즘을 len(lst) - 1 만큼 반복한다.
    iters = len(lst) - 1
    for iter in range(iters):
        # 이미 구한 최댓값은 범위에서 제외한다.
        wall = iters - iter
        for cur in range(wall):
            if lst[cur] > lst[cur + 1]:
                lst[cur], lst[cur + 1] = lst[cur + 1], lst[cur]
    return lst

선택 정렬 (selection Sort)

선택 정렬 알고리즘은 데이터중 가장 작은 데이터를 선택하여 맨 앞부터 순서대로 정렬해가는 알고리즘이다.
따라서 뒤 인덱스로 갈수록 비교 범위가 1씩 감소한다는 특징을 갖는다.

입력된 배열에 상관없이 동일한 연산량을 갖기 때문에 최적화의 역지가 적어 성능이 떨어지는 편이다.
오름차순 정렬 기준으로 최소값을 찾기 위해 비교는 여러 번 하지만 스왑은 딱 한 번만 일어난다. 따라서 시간 복잡도는 O(n^2)을 갖는다.
이러한 성능 상의 한계 떄문에 실제로는 잘 쓰이진 않지만, 가장 구현이 쉬운 정렬 알고리즘이다.

def selectionSort(lst):
    iters = len(lst) - 1
    for iter in range(iters):
        minimun = iter
        for cur in range(iter + 1, len(lst)):
            if lst[cur] < lst[minimun]:
                minimun = cur

        if minimun != iter:
            lst[minimun], lst[iter] = lst[iter], lst[minimun]

    return lst

삽입 정렬 (insertion Sort)

삽입 정렬이란 모든 요소를 앞에서부터 정렬 범위를 확장시켜나가며 정렬을 진행한다. 차례대로 이미 정렬된 배열 부분과 확장된 범위 부분을 비교하며, 자신의 위치를 찾아 삽입함으로써 정렬을 완성시키는 알고리즘이다.

정렬이 진행될수록 범위가 넓어진다. outer루프는 순방향, inner루프는 역방향으로 반복을 진행한다.
루프 문을 통해 정렬 범위를 2개로 시작하여 전체로 확장해 나아가기 때문에 기본적으로 O(N)이 소모되며, 각 회차마다 정렬 범위에 추가된 값과 기존 값들과의 대소 비교 및 스왑을 위해 O(N)이 추가적으로 소모된다.
따라서 삽입 정렬은 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘이다.

def insertionSort(lst):
    # 0번째 요소는 이미 정렬되어있으니, 1번째 ~ lst(len)-1 번째를 정렬하면 된다.
    for cur in range(1, len(lst)):
        # 비교지점이 cur-1 ~ 0(=cur-cur)까지 내려간다.
        for delta in range(1, cur + 1):
            cmp = cur - delta
            if lst[cmp] > lst[cmp + 1]:
                lst[cmp], lst[cmp + 1] = lst[cmp + 1], lst[cmp]
            else:
                break
    return lst

퀵 정렬 (quick sort)

퀵 정렬은 분할 정복 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다. pivot을 기준으로 정렬됩니다. pivot이란 정렬을 위해 사용하는 임의의 기준값이다.

퀵 정렬의 성능은 pivot값의 선택에 따라 크게 달라질 수 있다.
이상적인 경우, 작은 값과 큰값이 동일한 개수로 분할된다면, O(NlogN)의 시간 복잡도를 갖게 된다.
하지만 이미 정렬되어 pivot기준으로 값이 한쪽으로 치우치게 된다면 O(N^2)의 시간 복잡도를 갖게 된다.

def quicksort(lst, start, end):
    def partition(part, ps, pe):
        pivot = part[pe]
        i = ps - 1
        for j in range(ps, pe):
            if part[j] <= pivot:
                i += 1
                part[i], part[j] = part[j], part[i]

        part[i + 1], part[pe] = part[pe], part[i + 1]
        return i + 1

    if start >= end:
        return None

    p = partition(lst, start, end)
    quicksort(lst, start, p - 1)
    quicksort(lst, p + 1, end)

    return lst

병합 정렬 (merge sort)

병합 정렬은 퀵 정렬과 동일하게 분할 정복 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다. 주어진 배열의 크기가 1이 될 때까지 반씩 쪼갠 뒤 정렬을 진행하며 병합을 진행한다.

병합 정렬은 크게 split 단계와 merge단계로 나눌 수 있으며, 단순히 중간 인덱스를 찾아야 하는 분할 비용보다 모든 값들을 비교해야 하는 병합 비용이 더욱 크다.
기본 배열을 분할할 때 반복의 수가 거듭할수록 반으로 줄어들기 때문에 O(logN)의 시간이 필요하며, 병합 시 모든 값들을 비교해야 하므로 O(N) 시간이 소모된다.
따라서 병합 정렬은 O(NlogN)의 시간 복잡도를 갖는다.

# merge sort
# 배열 합치기
def merge(arr1, arr2):
    result = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    while i < len(arr1):
        result.append(arr1[i])
        i += 1

    while j < len(arr2):
        result.append(arr2[j])
        j += 1

    return result

# 배열 쪼개기
def mergesort(lst):
    if len(lst) <=1:
        return lst

    mid = len(lst)//2
    L=lst[:mid]
    R=lst[mid:]
    L_sort=mergesort(L)
    R_sort=mergesort(R)

    return merge(L_sort,R_sort)

힙 정렬 (heap Sort)

최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법이다. 정렬해야 할 n개의 요소들로 최대, 최소 힙을 만든다. 그다음으로 한 번에 하나씩 요소를 힙으로 꺼내서 배열에 추가한다.
최대 힙으로 만들어 정렬하면 내림차순이 되고, 최소 힙으로 정렬하면 오름차순이 된다. reverse 같은 메서드를 사용하면 최대 힙으로도 오름차순으로 정렬 가능하다.

힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때이다.
힙 트리의 전체 높이가 logN(완전 이진트리)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 logN 만큼 소요된다.
힙 정렬은 요소의 개수가 n개 일 때 전체적으로 O(NlogN)의 시간 복잡도를 갖게 된다.

# 힙 정렬
import heapq

def sorted_by_heap(lst):
    heap = []
    for elem in lst:
        heapq.heappush(heap, elem)

    desc = [heap.heappop() for _ in range(len(lst))]
    return list(reversed(desc))

저작자표시