[Algorithm] 정렬 알고리즘

기초적인 정렬 알고리즘

선택정렬

가장 큰 원소를 찾아 배열의 마지막 인덱스의 원소와 자리를 바꾼다.

이후 마지막 인덱스 원소를 제외한 나머지로 반복한다.

def selectionSort(lst):
    size = len(lst)
    for i in range(size):
	    maxIdx = lst.index(max(lst[:size-i]))
	    lst[maxIdx], lst[(size-i)-1] = lst[(size-i)-1], lst[maxIdx]
    return lst

버블정렬

제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. (비교를 통해 큰 원소를 뒤로 보냄)

def bubbleSort(lst):
    size = len(lst)
    for i in range(size):
        for j in range((size-1)-i):
            if (lst[j] > lst[j+1]):
                lst[j] , lst[j+1] = lst[j+1], lst[j]
    return lst

삽입정렬

이미 정렬된 i개 원소를 가진 배열에 하나의 원소를 더해, 정렬된 i+1개의 배열을 만든다.

이를 반복한다. 선택정렬과 버블정렬은 배열을 줄여가면서 정렬하지만, 삽입정렬은 배열을 늘려가며 정렬한다.

def insertSort(lst):
    size = len(lst)
    for i in range(1, size):
        loc = i - 1
        newItem = lst[i]
        while loc >= 0 and newItem < lst[loc]:
            lst[loc + 1] = lst[loc]
            loc -= 1
        lst[loc+1] = newItem
    return lst

고급 정렬 알고리즘

병합정렬

입력을 반으로 나눈 후, 전반부와 후반부를 각각 독립적으로 정렬한 후 합친다.

전반부와 후반부를 정렬할 때에도 반으로 나눠 정렬하고 합치는 것은 반복한다. 재귀적.

def mergeSort(lst):
    if len(lst) <= 1:
        return lst
    half = len(lst) // 2
    leftList = mergeSort(lst[:half])
    rightList = mergeSort(lst[half:])
    return merge(leftList, rightList)

def merge(left, right):
    lst = []
    while True:
        if len(left) == 0 or len(right) == 0:
            break
        if left[0] < right[0]:
            lst.append(left[0])
            left = left[1:]
        else:
            lst.append(right[0])
            right = right[1:]
    if len(left) == 0:
        lst.extend(right)
    elif len(right) == 0:
        lst.extend(left)
    return lst

퀵정렬

평균적으로 좋은 성능을 갖는다. 배열에서 기준 원소 (pivot)을 정하고 이를 기준으로 작은 것은 전반부, 큰 것은 후반부로 보내고, 전반부와 후반부에 대해서 다시 적용한다. 재귀적.

def quickSort(lst):
    if len(lst) <= 1:
        return lst
    stand = lst[0]
    left = [i for i in lst if i < stand]
    right = [i for i in lst if i > stand]
    equal = [i for i in lst if i == stand]
    return quickSort(left) + equal + quickSort(right)

힙정렬

자료구조 힙을 사용한다. 최소 힙(루트 노드가 최솟값)과 최대 힙으로 나눌 수 있다.

 

힙은 이진 트리구조로, 2가지 조건을 만족한다. (꽉 채워진 이진트리)

1) 맨 아래층을 제외하고 모두 채워져 있다.

2) 맨 아래층은 왼쪽부터 모두 채워져 있다.

 

먼저, 힙을 만든다. (최소 힙으로 구현)

자료구조 힙 -> 배열

위와 같은 자료구조 힙을 배열로 정리하기 위해서

부모노드의 인덱스 K에 자식 노드의 인덱스는 왼쪽(2K) 오른쪽(2K+1)로 정해진다.

 

만들어진 힙에서 루트 노드를 꺼내고 (마지막 인덱스와 교체),

마지막 인덱스를 제외하고 다시 힙 구조로 만들고, 반복한다.