탐색, 정렬 알고리즘

최대환·2022년 5월 11일

삽입정렬 선택정렬 선형탐색 이분탐색

알고리즘

목록 보기

7/8

✅ 탐색 알고리즘

선형 탐색(Linear Search Algorithm)

특징

가장 왼쪽부터 가장 오른쪽까지 값을 찾으려는 값과 하나하나 비교하며 탐색하는 방법
정렬이 안되어있어도 쓸 수 있음

예시

# 정렬
[23, 75, 34, 3, 83, 32, 5, 17, 39, 43, 14]

찾으려는 값이 34이면
23과 34를 비교하고 아니여서 넘어가고
75와 34를 비교하고 아니여서 넘어가고
34와 34를 비교해서 정답.

시간복잡도

최선의 경우
찾으려는 값이 23일때 1만큼 걸린다. O(1)만큼 걸린다.

최악의 경우
찾으려는 값이 1일때, 리스트에 없음으로 리스트의 길이인 11만큼 걸린다. O(N)만큼 걸린다.

로직

def linear_search(element, some_list):

    for i in range(len(some_list)):
        if element == some_list[i]:
            return i


print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))

이진 탐색(binary search Algorithm)

특징

리스트의 중간값과 찾으려는 값을 비교해서 틀리면 리스트 범위를 좁히는 형식으로 탐색하는 방법
정렬되어 있어야만 쓸 수 있음

예시

# 정렬
[1, 5, 7, 8, 10, 13, 17, 19, 23, 24, 28, 39]

찾으려는 값이 7이면
리스트의 중간값인 13과 7을 비교하고 아니여서 넘어가고, 리스트의 범위를 [1, 5, 7, 8, 10로 줄인다.
리스트의 중간값인 7과 7을 비교해서 정답

시간복잡도

최선의 경우
찾으려는 값이 13일때 1만큼 걸린다. O(1)만큼 걸린다.

최악의 경우
찾으려는 값이 0일때, 리스트에 없음으로 리스트 길이가 N이고 찾으려는 값을 k로 가정하면,
처음 반절로 나누면 (1/2) x N
두번 나누면 (1/2) x (1/2) x N
k번 나누면 (1/2)^k x N인데
최악의 경우 남는 자료가 1개이기 떄문에
(1/2)^k x N = 1임으로
양변에 2^K 를 곱해주면
N = 2^K 임으로
k = log2(N) 이다.
즉 O(log(N)) 만큼 걸린다.

로직

def binary_search(element, some_list):
    start_index, end_index = 0, len(some_list) - 1

    while start_index <= end_index:
        mid_index = (start_index + end_index) // 2

        if some_list[mid_index] == element:
            return mid_index
        elif some_list[mid_index] < element:
            start_index = mid_index + 1
        elif some_list[mid_index] > element:
            end_index = mid_index - 1

    return None

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

✅ 탐색 알고리즘

선택 정렬(sort selection Algorithmn)

특징

각 위치에 어떤 값이 들어갈지 찾음
가장작은걸 계속 찾아서 정렬시킴

예시

# 정렬
[5, 1, 3, 4, 9, 7]

오름차순으로 정렬시키면
[5, 1, 3, 4, 9, 7]리스트 중에 가장 작은 값인 1을 가장 앞과 바꾼다
-> [1, 5, 3, 4, 9, 7]
5, 3, 4, 9, 7에서 가장 작은 값인 3과 가장 앞과 바꾼다
-> [1, 3, 5, 4, 9, 7]
5, 4, 9, 7에서 가장 작은 값인 4와 가장 앞과 바꾼다
-> [1, 3, 4, 5, 9, 7]
5, 9, 7에서 가장 작은 값인 5가 가장 앞에 있으므로 넘어간다
9, 7에서 가장 작은 값인 7을 가장 앞과 바꾼다
-> [1, 3, 4, 5, 7, 9]

선택 정렬(insertion sort Algorithmn)

특징

각 값이 어떤 위치에 들어갈지 찾음
가장 작은걸

예시

# 정렬
[5, 1, 3, 4, 9, 7]

오름차순으로 정렬시키면
5, 1 에서 1이 5보다 작음으로 위치를 바꾼다.
-> [1, 5, 3, 4, 9, 7]
1, 5, 3에서 3이 5보다 작음으로 위치를 바꾼다. 3이 1보단 큼으로 멈춘다.
-> [1, 3, 5, 4, 9, 7]
1, 3, 5, 4에서 4가 5보다 작음으로 위치를 바꾼다. 4가 3보단 큼으로 멈춘다.
-> [1, 3, 4, 5, 9, 7]
1, 3, 4, 5, 9에서 9가 제일 큼으로 그대로다.
-> [1, 3, 4, 5, 9, 7]
1, 3, 4, 5, 9, 7에서 7이 9보다 작음으로 위치를 바꾼다. 7이 5보단 큼으로 멈춘다.
-> [1, 3, 4, 5, 7, 9]