코드잇 알고리즘(2)

선형 탐색 알고리즘(linear search algorithm)

하나씩 순서대로 쭉 보면서 내가 원하는 값을 찾는 방법

def linear_search(element, some_list):
    # 코드를 작성하세요.
    linear_search = some_list
    for i in range(len(linear_search)):
        if linear_search[i] == element:
            return i
    if i == len(linear_search):
        return None

이진 탐색 알고리즘(binary search algorithm)

가운데를 똑 잘라서 내가 원하는 값이 왼쪽 오른쪽 어디에 있는지 확인. 오른쪽에 있다면 오른쪽의 반을 또 잘라서 어떤 부분에 있는지 확인. 계속해서 1/2씩 잘라서 원하는 값을 찾는 방법

def binary_search(element, some_list):
    # 코드를 작성하세요.
    bi_list = some_list
    start_idx = 0
    end_idx = len(bi_list)
    
    while end_idx != 0:
        half_idx = (start_idx + end_idx) // 2
        if element == bi_list[half_idx]:
            return half_idx
        elif element < bi_list[half_idx]:
            end_idx = half_idx
        elif element > bi_list[half_idx]:
            start_idx = half_idx
    
    return None

 

최악의 경우 고려할 경우의 수
리스트 길이	선형 탐색	이진 탐색
16	16개	4개
32	32개	5개
64	64개	6개
128	128개	7개

이진탐색은 항상 쓸 수 없고, 정렬된 리스트에서만 사용이 가능하기 때문에 선형 탐색도 아주 쓸모없는 건 아니다.

 

정렬(Sorting)

리스트의 원소들을 특정 순서로 정리하는 것(알파벳 순, 숫자 크기 순 등)

선택 정렬(Selection Sort)

자연스러운 정렬 알고리즘. 각 위치에 어떤 값이 들어갈지 찾는다. 

1. 가장 작은 값을 찾아서 0번에 넣음
2. 그 다음 가장 작은 값을 찾아서 1번에 넣음
3. ~
4. 정렬 끝!

def selection_sort(some_list):
    for i in range(len(some_list)-1):
        min_val, min_idx = some_list[i], i
        for j in range(i+1, len(some_list)):
            if min_val > some_list[j]:
                min_val, min_idx = some_list[j], j
        some_list[i], some_list[min_idx] = some_list[min_idx], some_list[i]
    return some_list

삽입정렬(Insertion Sort)

각 값이 어떤 위치에 들어갈지 찾는다. 

1. 리스트의 첫번째 값은 정렬되어 있기 때문에 패스
2. 리스트의 2번 값을 봤을 때 1번 값보다 작으면 1번 값을 2번 자리에 넣고 2번째 값을 1번째 자리에 넣음. 
   2번 값이 1번 값보다 크면 패스
3. 리스트의 3번 값을 보고 2번처럼 진행
4. ~
5. 정렬 끝!

def insertion_sort(some_list):
    answer = some_list
    for i in range(len(some_list)-1):
        for j in range(i+1, len(some_list)):
            if some_list[i] > some_list[j]:
                answer[i], answer[j] = some_list[j], some_list[i]
    return answer

https://www.toptal.com/developers/sorting-algorithms

이 외에도 퀵 정렬, 힙 정렬, 거품 정렬 등 여러가지 정렬 알고리즘이 있다.