Sorting Algorithm

In [1]:

from IPython.core.display import display, HTML

display(HTML("<style>.container { width:100% !important; }</style>"))

View Source

Sorting¶

- 공간복잡도는 구현마다 달라집니다...

1. Selection Sort (선택정렬)¶

- iteration 을 돌때마다 제일 작은 원소를 선택
- 선택한 제일 작은 원소를 해당 iteration의 앞의 배치
- 최선 : O(N^2) 
- 평균 : O(N^2)
- 최악 : O(N^2) 

In [5]:

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프
    print(f'{i}th iteration')
    print(f'array : {array}')

print(f'final : {array}')

0th iteration
array : [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]
1th iteration
array : [0, 1, 9, 7, 3, 5, 6, 2, 4, 8]
2th iteration
array : [0, 1, 2, 7, 3, 5, 6, 9, 4, 8]
3th iteration
array : [0, 1, 2, 3, 7, 5, 6, 9, 4, 8]
4th iteration
array : [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
5th iteration
array : [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
6th iteration
array : [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
7th iteration
array : [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
8th iteration
array : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9th iteration
array : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
final : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

2. Insertion Sort (삽입정렬)¶

- i 번째 원소(왼쪽) 까지 정렬되어 있다고 가정하여, i+1번째 원소(오른쪽의 첫번째 원소)를 왼쪽의 맞는 자리에 삽입 
- 선택한 제일 작은 원소를 해당 iteration의 앞의 배치
- 최선 : O(N) - 데이터가 정렬되어 있는 경우 
- 평균 : O(N^2)
- 최악 : O(N^2) 

In [11]:

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break
    print(f'{i}th iteration array : {array}')
    print(f'left array : {array[:i]}')

1th iteration array : [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
left array : [5]
2th iteration array : [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
left array : [5, 7]
3th iteration array : [0, 5, 7, 9, 3, 1, 6, 2, 4, 8]
left array : [0, 5, 7]
4th iteration array : [0, 3, 5, 7, 9, 1, 6, 2, 4, 8]
left array : [0, 3, 5, 7]
5th iteration array : [0, 1, 3, 5, 7, 9, 6, 2, 4, 8]
left array : [0, 1, 3, 5, 7]
6th iteration array : [0, 1, 3, 5, 6, 7, 9, 2, 4, 8]
left array : [0, 1, 3, 5, 6, 7]
7th iteration array : [0, 1, 2, 3, 5, 6, 7, 9, 4, 8]
left array : [0, 1, 2, 3, 5, 6, 7]
8th iteration array : [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
left array : [0, 1, 2, 3, 4, 5, 6, 7]
9th iteration array : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
left array : [0, 1, 2, 3, 4, 5, 6, 7, 8]

3. Quick Sort (퀵정렬)¶

- Hoare Partition 방식
- 주어진 배열에서 첫번째 원소를 pivot 으로 선택 
- 나머지 배열에서 왼쪽 -> 오른쪽 방향으로 pivot 보다 큰 원소를 선택 이때의 index를 - index1
- 나머지 배열에서 오른쪽 -> 왼쪽 방향을 pivot 보다 작은 원소를 선택 이때의 index를 - index2
- 위의 index1 < index2 이면 두개의 위치를 변경
- 만약 index1 > index2 그렇지 않으면 pivot 과 index1의 값을 변경 
- 그 결과 pivot을 기준으로 왼쪽은 pivot 보다 작은 값들 오른쪽은 pivot 보다 큰 값들
- 위 방법을 재귀적으로 실행 
- 최선 : O(NlogN) 
- 평균 : O(NlogN)
- 최악 : O(N^2) - 데이터가 정렬되어 있는 경우 - 삽입 정렬과 반대

In [17]:

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array

    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분
    print(f'array : {array} -> left_side : {left_side}, right_side : {right_side}')
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

array : [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] -> left_side : [0, 3, 1, 2, 4], right_side : [7, 9, 6, 8]
array : [0, 3, 1, 2, 4] -> left_side : [], right_side : [3, 1, 2, 4]
array : [3, 1, 2, 4] -> left_side : [1, 2], right_side : [4]
array : [1, 2] -> left_side : [], right_side : [2]
array : [7, 9, 6, 8] -> left_side : [6], right_side : [9, 8]
array : [9, 8] -> left_side : [8], right_side : []
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

4. Count Sort (계수 정렬)¶

- 특정 조건하에서 매우 빠른 알고리즘
- 특정 조건 : 데이터의 크기 범위가 제한되어 정수형태로 표현할 수 있을때 -> 성적
- 데이터의 크기 범위를 담을 수 있는 배열 선언 
- 데이터의 갯수 N, 최대값 K
- 배열을 순회(0 ~ K) 하며 데이터 각 인덱스(점수)에 해당하는 값 증가
- 최선 : O(N + K) 
- 평균 : O(N + K) 
- 최악 : O(N + K)  

In [20]:

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9 

번외¶

5. Merge Sort (병합 정렬)¶

- 작은 단위로부터 병합을 하며 정렬한는 방법 
- quick sort 는 pivot 을 기준으로 쪼개가며 정렬하는 반면, 이는 그 반대
- 최선 : O(NlogN) 
- 평균 : O(NlogN) 
- 최악 : O(NlogN)  

In [27]:

def merge_sort(arr):
    if len(arr) < 2:
        
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    print(f'low_arr : {low_arr}, high_arr : {high_arr} -> merged_arr : {merged_arr}')
    return merged_arr

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
merge_sort(array)

low_arr : [5], high_arr : [7] -> merged_arr : [5, 7]
low_arr : [0], high_arr : [3] -> merged_arr : [0, 3]
low_arr : [9], high_arr : [0, 3] -> merged_arr : [0, 3, 9]
low_arr : [5, 7], high_arr : [0, 3, 9] -> merged_arr : [0, 3, 5, 7, 9]
low_arr : [1], high_arr : [6] -> merged_arr : [1, 6]
low_arr : [4], high_arr : [8] -> merged_arr : [4, 8]
low_arr : [2], high_arr : [4, 8] -> merged_arr : [2, 4, 8]
low_arr : [1, 6], high_arr : [2, 4, 8] -> merged_arr : [1, 2, 4, 6, 8]
low_arr : [0, 3, 5, 7, 9], high_arr : [1, 2, 4, 6, 8] -> merged_arr : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Out[27]:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

6. Heap Sort (힙 정렬)¶

- Heap Structure 을 이용한 정렬 
- Heap 넣을때의 연산 logN, 뺄때의 연산 logN 이므로 매우 안정적이다. 
- 최선 : O(NlogN) 
- 평균 : O(NlogN) 
- 최악 : O(NlogN) 

In [32]:

import heapq

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
heapq.heapify(array)
sort_array = []
while array:
    sort_array.append(heapq.heappop(array))
print(sort_array)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

7 Bubble Sort (버블 정렬)¶

- iteration 인접한 값들을 비교하며 가장큰 원소를 가장 뒤에 배치
- 최선 : O(N^2) 
- 평균 : O(N^2)
- 최악 : O(N^2) 

In [33]:

def bubbleSort(x):
    length = len(x)-1
    for i in range(length):
        for j in range(length-i):
            if x[j] > x[j+1]:
                x[j], x[j+1] = x[j+1], x[j]
    return x
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
print(bubbleSort(array))

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

8. Python Sort (Tim Sort)¶

- quick sort 와 merge sort 의 혼합

정리¶

• O(n2) 정렬 알고리즘 : 버블정렬, 선택정렬, 삽입정렬 (퀵 정렬과 달리 정렬된 상태에서 O(n))
• O(nlogn) 정렬 알고리즘 : 퀵정렬(삽입정렬과 달리 정렬된 상태에서 O(n2)), 병합정렬, 힙정렬
• O(n+k) 정렬 알고리즘 : 계수정렬 (특정 조건하에서만 작동)
• Python 에서 사용하는 정렬 : Tim Sort (퀵 정렬과 병합 정렬의 혼합)