자료구조를 확실히 공부했더니 이전에는 이해되지 않았던 히프정렬이나 트리정렬에 대해서 정확하게 이해할 수 있었다. 구현하는 것도 재밌었고 새로운 알고리즘(유전정렬)을 고안해 보기도 하였다 :)


버블 정렬(Bubble Sort)

인접한 원소를 두 개 비교하여 자리를 교환하는 방식이다. 처음부터 마지막까지 원소를 비교하여 마지막에는 가장 (큰 또는 작은) 원소가 배치된다. 이를 정렬이 끝날때까지 수행하며 시간 복잡도는 O(n^2)이며 구현이 압도적으로 간단하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def bubbleSort(m_list):
    length = len(m_list)

    for i in range(length):
        for j in range((length-1)-i):
            if m_list[j] < m_list[j+1]:
                temp = m_list[j]
                m_list[j] = m_list[j+1]
                m_list[j+1] = temp
        print(m_list)
    return m_list

if __name__=="__main__":
    m_list = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
    print('원본 리스트 :', m_list)
    sort_list = bubbleSort(m_list)
    print('정렬 리스트 :', sort_list)
1
2
3
4
5
6
7
8
9
10
11
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
1 회차 정렬 : [100, 40, 49, 65, 16, 43, 34, 77, 54, 3]
2 회차 정렬 : [100, 49, 65, 40, 43, 34, 77, 54, 16, 3]
3 회차 정렬 : [100, 65, 49, 43, 40, 77, 54, 34, 16, 3]
4 회차 정렬 : [100, 65, 49, 43, 77, 54, 40, 34, 16, 3]
5 회차 정렬 : [100, 65, 49, 77, 54, 43, 40, 34, 16, 3]
6 회차 정렬 : [100, 65, 77, 54, 49, 43, 40, 34, 16, 3]
7 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
8 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
9 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
정렬 리스트 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]


선택 정렬(Selection Sort)

앞 원소부터 기준 위치로 지정하고 기준 위치에서 뒤쪽의 원소들과 크기를 비교하여 가장 (또는 큰) 원소를 선택하여 교체하는 방식이다. 시간 복잡도는 O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def selectionSort(m_list):
    length = len(m_list)

    for i in range(length):
        max = { 'value':0, 'index':0 }
        for j in range(i, length):
            if max['value'] < m_list[j]:
                max['value'] = m_list[j]
                max['index'] = j
        temp = m_list[i]
        m_list[i] = m_list[max['index']]
        m_list[max['index']] = temp
    return m_list

if __name__=="__main__":
    m_list = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
    print('원본 리스트 :', m_list)
    sort_list = selectionSort(m_list)
    print('정렬 리스트 :', sort_list)
1
2
3
4
5
6
7
8
9
10
11
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
1 회차 정렬 : [100, 3, 40, 49, 65, 16, 43, 34, 77, 54]
2 회차 정렬 : [100, 77, 40, 49, 65, 16, 43, 34, 3, 54]
3 회차 정렬 : [100, 77, 65, 49, 40, 16, 43, 34, 3, 54]
4 회차 정렬 : [100, 77, 65, 54, 40, 16, 43, 34, 3, 49]
5 회차 정렬 : [100, 77, 65, 54, 49, 16, 43, 34, 3, 40]
6 회차 정렬 : [100, 77, 65, 54, 49, 43, 16, 34, 3, 40]
7 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 3, 16]
8 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 3, 16]
9 회차 정렬 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]
정렬 리스트 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]


삽입 정렬(Insertion Sort)

사람이 생각하는 정렬의 기본적인 모델로 적당한(?) 값 사이에 엘리먼트를 집어넣는다. 물론 그렇게 하기 위해서 n인 인덱스를 선택했다면 n-1까지 n 인덱스가 들어 갈 수 있도록 공간을 마련해야 한다. 아래 소스코드는 이론을 토대로 작성된 코드라 틀린 부분이 있을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def insertionSort(m_list):
    length = len(m_list)

    for i in range(1, length):
        if m_list[i] < m_list[i-1]:
            for j in range(i, 0, -1):
                if m_list[j] < m_list[j-1]:
                    temp = m_list[j]
                    m_list[j] = m_list[j-1]
                    m_list[j-1] = temp
                else:
                    break
    return m_list

if __name__=="__main__":
    m_list = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
    print('원본 리스트 :', m_list)
    sort_list = insertionSort(m_list)
    print('정렬 리스트 :', sort_list)
1
2
3
4
5
6
7
8
9
10
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
1 회차 정렬 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
2 회차 정렬 : [3, 40, 100, 49, 65, 16, 43, 34, 77, 54]
3 회차 정렬 : [3, 40, 49, 100, 65, 16, 43, 34, 77, 54]
4 회차 정렬 : [3, 40, 49, 65, 100, 16, 43, 34, 77, 54]
5 회차 정렬 : [3, 16, 40, 49, 65, 100, 43, 34, 77, 54]
6 회차 정렬 : [3, 16, 40, 43, 49, 65, 100, 34, 77, 54]
7 회차 정렬 : [3, 16, 34, 40, 43, 49, 65, 100, 77, 54]
8 회차 정렬 : [3, 16, 34, 40, 43, 49, 65, 77, 100, 54]
정렬 리스트 : [3, 16, 34, 40, 43, 49, 54, 65, 77, 100]


병합 정렬(Merge Sort)

추후 추가됨


힙 정렬(Heap Sort)

값 들을 힙에 삽입하고 삭제 연산을 반복해서 정렬하는 방법이다. 실제로는 원본 배열에서 정렬을 실시하여 추가 메모리를 사용하지 않는 것이 정석인 것으로 보인다. 히프는 직접 구현한 자료구조를 활용하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def heapSort(m_list):
    length = len(m_list)
    m_heap = Heap()
    for element in m_list:
        m_heap.insertElement(element)
    result = []
    for i in range(length):
        result.append(m_heap.deleteRoot())
        print(result)
    return result

if __name__=="__main__":
    m_list = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
    print('원본 리스트 :', m_list)
    sort_list = heapSort(m_list)
    print('정렬 리스트 :', sort_list)
1
2
3
4
5
6
7
8
9
10
11
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
1 원소 삭제 : [100]
2 원소 삭제 : [100, 77]
3 원소 삭제 : [100, 77, 65]
4 원소 삭제 : [100, 77, 65, 54]
5 원소 삭제 : [100, 77, 65, 54, 49]
6 원소 삭제 : [100, 77, 65, 54, 49, 43]
7 원소 삭제 : [100, 77, 65, 54, 49, 43, 40]
8 원소 삭제 : [100, 77, 65, 54, 49, 43, 40, 34]
9 원소 삭제 : [100, 77, 65, 54, 49, 43, 40, 34, 16]
정렬 리스트 : [100, 77, 65, 54, 49, 43, 40, 34, 16, 3]


퀵 정렬(Quick Sort)

피봇을 두고 피봇의 오른쪽과 왼쪽을 피봇의 크기와 비교하여 정렬하는 방식이다. 피봇보다 큰 L 인덱스와 피봇보다 작은 R 인덱스를 교체한다. LR이 만나면 피봇은 그 자리로 이동하는 방식의 정렬이다.


기수 정렬(Radix Sort)

기수 정렬은 각 원소끼리 비교하지 않고 각 원소의 자릿수에 맞게 배열에 저장했다가 다시 합치는 방식을 반복하여 정렬하는 방식이다. 원소들의 자릿수가 적을때 용이한 정렬법이다. 아래 소스코드는 이론을 토대로 작성된 코드라 틀린 부분이 있을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def radixSort(m_list):
    radix_num = -1

    for i in range(3):
        radix = [ [] for i in range(10) ]
        for element in m_list:
            element_digit = list(str(element))
            element_digit_now = 0
            try:
                element_digit_now = int(element_digit[radix_num])
            except IndexError:
                pass
            radix[element_digit_now].append(element)

        m_list = []
        for i in range(10):
            for j in range(len(radix[i])):
                m_list.append(radix[i][j])
        radix_num -= 1
    return m_list

if __name__=="__main__":
    m_list = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
    print('원본 리스트 :', m_list)
    sort_list = radixSort(m_list)
    print('정렬 리스트 :', sort_list)
1
2
3
4
5
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
1 회차 정렬 : [100, 40, 3, 43, 34, 54, 65, 16, 77, 49]
2 회차 정렬 : [100, 3, 16, 34, 40, 43, 49, 54, 65, 77]
3 회차 정렬 : [3, 16, 34, 40, 43, 49, 54, 65, 77, 100]
정렬 리스트 : [3, 16, 34, 40, 43, 49, 54, 65, 77, 100]


트리 정렬(Tree Sort)

값 들을 이진 탐색 트리에 삽입하고 이진 탐색 트리를 중위 순회하면 정렬이 된다. 트리는 직접 구현한 자료구조를 활용하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def treeSort(m_list):
    length = len(m_list)
    m_search_tree = SearchTree()
    for element in m_list:
        m_search_tree.insertElement(element)
    m_search_tree.inorderTraversal(m_search_tree.root)
    return m_search_tree.inorder_list

if __name__=="__main__":
    m_list = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
    print('원본 리스트 :', m_list)
    sort_list = treeSort(m_list)
    print('정렬 리스트 :', sort_list)
1
2
3
4
5
6
7
8
9
10
11
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
1 삽입 순회 : [3]
2 삽입 순회 : [3, 100]
3 삽입 순회 : [3, 40, 100]
4 삽입 순회 : [3, 40, 49, 100]
5 삽입 순회 : [3, 40, 49, 65, 100]
6 삽입 순회 : [3, 16, 40, 49, 65, 100]
7 삽입 순회 : [3, 16, 40, 43, 49, 65, 100]
8 삽입 순회 : [3, 16, 34, 40, 43, 49, 65, 100]
9 삽입 순회 : [3, 16, 34, 40, 43, 49, 65, 77, 100]
정렬 리스트 : [3, 16, 34, 40, 43, 49, 54, 65, 77, 100]


유전 정렬(Genetic Sort)

재미로 만들어 보았다. 비슷한 알고리즘으론 보고정렬이 있으며 성능은 매우 최악이다 ㅋㅋㅋ 적합도 평가를 좀 더 개선하면 좋아질 기미는 보인다. 현재는 10개의 요소를 정렬하는데 최소 0.2초에서 최대 35초가 걸린다. 적합도 평가를 개선하고 염색체를 다소 늘려서 최소 0.08초 최대 7초로 개선했다.

결과

100회를 실시하여 얻은 결과이며 평균적으로 회당 1-2초가 걸렸다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import random
import copy

def geneticSort(m_list, mode):
    MAX_CHROMO = 100
    mutation = 0.35

    chromo = [random.sample(m_list, len(m_list)) for i in range(MAX_CHROMO)]
    evoluation_value = [0 for i in range(MAX_CHROMO)]
    choice_chromo = [0,0]
    
    done = 0
    for i in range(len(m_list) - 1):
        done += 1 * ( i + 1 )

    while True:
        for i in range(MAX_CHROMO):
            for j in range(len(m_list) - 1):
                if chromo[i][j] < chromo[i][j+1]:
                    evoluation_value[i] += 1 * ( j + 1 )
        
        evoluation_max = {
            'first'  : 0,
            'second' : 0,
        }
        for i in range(MAX_CHROMO):
            if evoluation_max['first'] < evoluation_value[i]:
                evoluation_max['first'] = evoluation_value[i]
                choice_chromo[0] = i
                continue
            if evoluation_max['second'] < evoluation_value[i] and i is not choice_chromo[0]:
                evoluation_max['second'] = evoluation_value[i]
                choice_chromo[1] = i

        if done in evoluation_value:
            break

        evoluation_value = [0 for i in range(MAX_CHROMO)]
        new_chromo = []
        for i in range(MAX_CHROMO):
            new_chromo.append(copy.deepcopy(chromo[choice_chromo[random.randint(0, 1)]]))

        for i in range(MAX_CHROMO):
            for j in range(len(m_list)):
                if mutation > random.random():
                    a = random.randint(0, len(new_chromo[i])-1)
                    b = random.randint(0, len(new_chromo[i])-1)
                    temp = new_chromo[i][a]
                    new_chromo[i][a] = new_chromo[i][b]
                    new_chromo[i][b] = temp
    
        if len(m_list)-1 in evoluation_value:
            break
        chromo = copy.deepcopy(new_chromo)
    return chromo[choice_chromo[0]]
    
if __name__=="__main__":
    m_list = [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
    print('원본 리스트 :', m_list)
    sort_list = geneticSort(m_list)
    print('정렬 리스트 :', sort_list)
1
2
3
원본 리스트 : [3, 100, 40, 49, 65, 16, 43, 34, 77, 54]
정렬 리스트 : [3, 16, 34, 40, 43, 49, 54, 65, 77, 100]
실행 시간   : 0.66


각 정렬의 성능

Algorithm Space Complexity (average) Time Complexity (worst) Time Complexity
Bubble sort O(1) O(n^2) O(n^2)
Selection sort O(1) O(n^2) O(n^2)
Insertion sort O(1) O(n^2) O(n^2)
Merge sort O(n) O(nlogn) O(nlogn)
Heap sort O(1) O(nlogn) O(nlogn)
Quick sort O(1) O(nlogn) O(n^2)
Radix sort O(n) O(n) O(n)
WRITTEN BY

배진오

소비적인 일보단 생산적인 일을 추구하며, 좋아하는 일을 잘하고 싶어합니다 :D
im@baejino.com