선택 정렬(Selection Sort)

• 가장 먼저 생각 날 수 있는 자연스러운 정렬 알고리즘

리스트에서 가장 작은 수를 찾아서 0번 인덱스에 있는 수와 자리를 바꿈
그 다음으로 작은 수를 쭉 찾아서 1번 인덱스에 있는 수와 자리를 바꿈
...(끝날때까지)

삽입 정렬(Insertion Sort)

• 각 값이 어떤 위치로 가야할지 찾는 것

리스트 0개, 1개, 2개 ... 씩 보면서 추가된 인덱스에 있는 번호를 삽입하는 형태
리스트의 0번 인덱스는 혼자 있으니까 정렬이 되어 있고,
리스트의 1번 인덱스가 추가되면 0번과 비교해서 그 위치를 정렬하고,
리스트의 2번 인덱스가 추가되면 1번과 비교해서 그것보다 작으면 위치를 바꾸고 또 0번과 비교해서 그것보다 작으면 위치를 바꾸고,
...(끝날때까지)

https://www.toptal.com/developers/sorting-algorithms <- 여기 들어가면 정렬 방법에 따라 어떻게 진행되는지 눈으로 확인해볼 수 있다!

상황에 따라 어떤 정렬방법이 빠른지는 다르다는 걸 알 수 있다. Nearly Sorted 리스트의 경우에는 삽입 정렬(Insertion Sort)이 가장 빠른 반면에 Random 리스트를 정렬할 때는 힙 정렬(Heapsort)이 가장 먼저 끝난다. Reversed 리스트의 경우에는 삽입 정렬이 매우 오래 걸리며, 선택 정렬(Selection Sort)과 합병 정렬(Merge Sort)은 상황에 영향을 받지 않고 일정한 시간이 소요된다.

따라서 정렬 문제의 경우 "절대적인 좋은 답”은 없으며, 상황에 따른 각 알고리즘의 장단점을 파악하여 올바른 알고리즘을 선택해야 한다.

그렇기 때문에 문제를 해결하는 방법을 넘어서 “알고리즘 평가법”을 알아야 한다.

평가의 기준 : 시간과 공간

• 시간 : 빠르게 되는지
• 공간 : 메모리를 적게 쓰는지

이 중 알고리즘에서 중요한 시간을 살펴보자.

시간 복잡도(Time Complexity)

단순 시간이 얼마나 걸리는지 체크하는 건 컴퓨터 사양이나 느린 프로그램 언어 등 외부 영향에 따라 달라지브로 시간 복잡도 라는 기준을 사용한다.

시간 복잡도는 데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는가를 나타낸다.
데이터의 크기에 따라 시간이 선형적으로 증가하는 알고리즘이 지수적 증가하는 알고리즘보다 시간 복잡도가 작다=더 빠른 알고리즘이다 라고 얘기한다.

점근 표기법(Big-O Notation)

소요시간	점근표기법(Big-O)
20n+40	O(n)
2n^2 + 8n + 157	O(n^2)
2n^3 + 8n + 157	O(n^3)
20lgn+ 8n + 157	O(lgn)

• 이렇게 하는 이유는?

1. n이 크다고 가정
n이 별로 크지 않으면, 안 좋은 알고리즘을 써도 큰 문제가 없다.

2. 계수는 신경쓰지 않는다.
2n -> O(n)
n -> O(n)

선형 탐색 알고리즘

def linear_search(element, some_list):
	i = 0                # O(1)
    n = len(some_list)   # O(1)
    
    
    # O(1) x 반복횟수(n) => O(n)
    while i < n:
    	if some_list[i] == element:
        	return i
        i += 1
        
    return -1            # O(1)

• 선형탐색 알고리즘에서의 시간복잡도는 O(n+3) -> O(n) 이다.

이진 탐색 알고리즘

def binary_search(element, some_list):
	start_index = 0                 # O(1)
    end_index = len(some_list) -1   # O(1)
    
    # O(1) x 반복 횟수(log_2n) => O(lgn)
    while start_index <= end_index:
    	midpoint = (start_index + end_index) // 2
        if some_list[midpoint] == element:
        	return midpoint
        elif element < some_list[midpoind]:
        	end_index = midpoint - 1
        else:
        	start_index = midpoint + 1
            
    return None                      # O(1)

• 이진 탐색의 경우 반씩 확인하니까 중간 while문에서 log_2n(lg(n))번 정도 실행된다.
• 따라서 이진탐색 알고리즘의 시간복잡도는 O(lg(n) + 3) -> O(lg(n)) 이다.

점근표기법에서는 n만 사용하나?

트리나 그래프의 경우에는 리스트처럼 선형적이지 않다. 그래프는 꼭짓점(vertex)과 변(edge)로 이루어져 있다. 꼭짓점의 개수를 V, 변의 개수는 E라고 하면 두 꼭짓점 간 최단 경로를 찾는 BFS 알고리즘의 시간 복잡도는 O(V+E)이다.

코드의 모든 줄은 O(1)인가?

인풋 크기와 상관없이 실행되는 코드만 O(1)이며, 그렇지 않은 코드는 시간 복잡도를 따져본다.
sorted나 sort함수를 사용하면 내부적으로 O(nlgn)의 정렬이 이루어지고,
리스트에서 in 으로 값의 존재 여부를 확인하면 내부적으로 O(n)의 선형 탐색이 이루어진다.

코드 없이 알고리즘을 평가하는 팁

• 선형 탐색을 하려면 최악의 경우에 n개를 봐야하니까 O(n)이다.
• 이진 탐색을 하려면 최악의 경우에 log2N을 봐야하니까 O(lgn)이다.