TIL_19 : 탐색 & 정렬

🙄 탐색

➡ 탐색이란?

• 저장된 정보들 중에서 원하는 값을 찾는 것

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

• 앞에서부터 순서대로 정보를 찾는 것

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]))

# 0
# None
# 2
# 1
# 4

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

• 찾고자 하는 값이 자료의 중간값보다 큰지 작은지 비교하며 탐색

def binary_search(element, some_list):
    start_index = 0
    end_index = len(some_list) - 1
    while start_index <= end_index:
        mid = (start_index + end_index) // 2
        if element < some_list[mid]:
            end_index = mid - 1
        elif element > some_list[mid]:
            start_index = mid + 1
        else:
            return some_list.index(element)
    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]))

# 0
# None
# 2
# 1
# 4

🙄 정렬

➡ 정렬이란?

• 리스트의 원소들을 특정 순서로 정리하는 것

➡ 선택 정렬 (Selection Sort)

• 각 위치에 어떤 값이 들어갈지 찾는다.
• 가장 먼저 생각이 날 수 있는 자연스러운 정렬 알고리즘
  ex) 가장 작은 값을 찾아서 0번 인덱스에 놓고,
  두번째로 작은 값을 찾아서 1번 인덱스에 놓고
  .....

구현해보기

➡ 삽입 정렬 (Insertion Sort)

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

구현해보기