10. Sorting Algorithms

 

지난 번 Linear / Binary Searching 외에도 코딩공부 시 중요한 알고리즘 중 하나인 Sorting에 대해 학습해봅시다.

 

Sorting --> 말 그대로 내림 or 오름차순으로 list 안에 data를 정렬한다는 것이다.

 

총 4가지 Sorting을 배워봅시다.

 

Insertion Sort

 

- 제일 쉬운 버전의 Sorting이다.

 

- Main Idea

 1) 처음엔 비어있는 Empty list에서 시작한다.

 2) Pile에서 Data들을 하나씩 가져와 크기순으로 Empty list에 하나씩 정렬시켜 저장한다.

 3) 정렬된 새로운 list가 output으로 나오게 되는 구조 --> 메모리효율을 위해 in-Place로 이것을 진행하기도 한다.

 4) 위의 3번의 경우, 단점은 원본이 보존되지 않는다.

 

# Insertion Sort

def insertion_sort(lst:list)->None:
    for i in range(1,len(lst)):
        key = lst[i]
        j = i - 1
        while j >= 0 and key < lst[j]:
            lst[j+1] = lst[j]
            j = j - 1
        lst[j+1] = key

 

Sorted 순서도

 

Time Complexity of insertion sort

 

- ith iteration에서 while loop이 하는 일

 1) [Find] Next item을 어디에 Put 할지 찾기 among i items

--> Complexity는 최악의 경우를 생각 + i 와 같이 우리가 만든 표현을 쓰지 않는다. --> O(N)

 

 2) [Shift] item을 오른쪽으로 1칸 이동 --> O(N)

 

 3) [Put] Target item의 위치를 찾아 놓기 --> O(1)

 

- 한 Loop 안에서 최종적으로 Compexity는 O(N)이다.

- 이런 O(N)이 또 for문 N번 도니까 최종적으로 OVerall Complexity는 O(N^2)

 

 

Selection Sort

 

- Main Idea

- Unsorted 부분에서 제일 작은 것을 찾아서 Sorted Region에 차곡차곡 넣는다.

 

# Selection Sort
​
lst = [-7,-4,-1,6,10,5,4,2,15,21]
​
def selection_sort(lst:list)->None:
    for i in range(len(lst)):
        smallest = i
        for j in range(i+1,len(lst)):
            if lst[smallest] > lst[j]:
                smallest = j
        lst[i],lst[smallest] = lst[smallest],lst[i]
                  
selection_sort(lst)
lst
[-7, -4, -1, 2, 4, 5, 6, 10, 15, 21]

 

 

 

 

Q : 위 코드를 Recursion으로 구현할 수 있을까?

https://eglife.tistory.com/29

10 - 1 . Recursion으로 Sort 코드 + Merge Sort 구현해보기

Time Complexity of selection sort

 

- Find the smallest item among N-i unsorted items --> O(N)

- Swap it --> O(1)

 

- 위 O(N) 과정을 총 N회 실시한다. --> O(N)

 

- Overall Complexity --> O(N^2)

 

- Insertion Sort와 비교 시, Input list가 sorted 되어 있다고 하여도 이점은 없다.

(Insertion Sort는 Unsorted 영역이 sorted 되어있는 구조면 time complexity가 확 줄어든다.)

 

 

Merge Sort ( Data의 규모가 클 때 유리 )

 

- Main idea

- 일단 List를 크게 두 개로 나누고

- 각각의 나눠진 List들을 각각 Sort한 다음

- 이것들을 다시 Merge한 뒤 Sort 한다.

 

- 각각쪼개진 list의 경우 최종적으로 더 이상 쪼갤 필요 없이 data가 1개 남을 때까지 쪼갠 뒤에 Merge한다.

 

 

- 그렇지만 이것들을 다시 Merge할 때 기존 Insertion or Selection Sort를 사용하면 time complexity가

- 2*(N/2)^2 + 4*(N/4)^2 .... 이라 결국 O(N^2) 이라 이점이 없다.

 

- Data들을 Merge하면서 Sort할 때, Merged list의 가장 왼쪽편에 올 수 있는 Data 후보는 두 list의 smallest data 2개이다. 그리고 이것이 반복된다.

 

Time Complexity of Merge Sort

 

- 각 Merge마다 Time Complexity가 어떻게 될까

- Compare 2 elements once --> O(1)

- Write the smallest --> O(1)

- Move one pointer on the selected side --> O(1)

 

- 위 사항들이 몇 번 반복되는가? 2(N/2) , 4(N/4) ... O(N)

- 그 깊이는 얼마나 될까? --> log(N) (list들을 반씩 얼마나 쪼개는가? --> 깊이)

 

- Overall time complexity : O(NlogN)

 

# Merge Sort

def merge_sort(list):
    if len(list) > 1 :
        mid = len(list) // 2
        left = list[:mid]
        right = list[mid:]
        
        merge_sort(left)
        merge_sort(right)

 

- 'else'로 위 코드의 base case를 만들어 주지 않은 이유는 len(list)가 1이 되어 버리면 더 이상 sort가 필요하지 않는 순간이라서 굳이 건들지 않는다

 

Q. Merge 코드를 구현해보자

https://eglife.tistory.com/29

10 - 1 . Recursion으로 Sort 코드 + Merge Sort 구현해보기

 

이보다 Time complexity가 더 좋은 Sorting이 가능한가?

( 값을 서로 비교해가며 Sorting하는 것중엔 O(NlogN)이 최고로 효율적이라는 것은 이미 증명이 되어있다. )

 

Linear - Time Sorting( 참고 )

 

- 이것은 특정 조건이 필요하다. and No need to compare each items.

 1) data가 정수여야 한다

 2) data가 특정범위 내에 있어야 한다

 

- Counting Sort

 

def counting_sort(list):
    output = [0] * (len(list))
    count = [0] * (max(list)+1)
    
    for i in range(len(list)):
        count[list[i]] += 1
        
    for i in range(1, len(count)):
        count[i] += count[i-1]
        
    for i in range(len(list)):
        j = len(list) - 1 - i
        count[list[j]] -= 1
        index = count[list[j]]
        output[index] = list[j]
    
    return output

 

많이 복잡하다 Sort..

 

Python library에 기본적으로 구현되어 있는 sort가 이렇게 복잡한 알고리즘으로 이루어져 있었다니 ㅠㅠ 막막~하다