• 탐색 : 여러 개의 자료 중 원하는 것을 찾아냄
• 정렬 : 주어진 자료를 순서에 맞춰 나열

1. 순차 탐색 = 선형 탐색

리스트 안에 있는 원소를 하나씩 순차적으로 비교하면서 탐색

1) 순차 탐색 알고리즘

def search_list(a, x):
	n = len(a)
    for i in range(0, n):
    	if x == a[i]:
        	return i
    return -1
    
v = [17, 92, 18, 33, 58, 7, 33, 42]
print(search_list(v, 18)) # 2

• 입력
  • 리스트 : a
  • 탐색 값 : x
• 출력
  • 인덱스 값 : 찾음
  • -1 : 못 찾음

2) 성능

O(n)

3) 응용

3-1) 탐색 값의 모든 위치 반환하는 알고리즘

def search_all(a, x):
    l = []
    n = len(a)
    for i in range(0, n):
        if a[i] == x:
            l.append(i)
    return l

v = [17, 92, 18, 33, 58, 7, 33, 42]
print(search_all(v, 18)) #[2]
print(search_all(v, 33)) #[3, 6]
print(search_all(v, 900)) #[]

• 탐색 값과 리스트를 순차적으로 비교하여 해당 인덱스를 리스트에 추가

3-2) 학생 번호에 해당하는 학생 이름 찾기

def get_name(s_no, s_name, find_no):
	n = len(s_no)
    for i in range(0, n):
    	if find_no == s_no[i]:
        	return s_name[i]
    return '?'

sample_no = [39, 14, 67, 105]
sample_name = ["Justin", "John", "Mike", "Summer"]
print(get_name(sample_no, sample_name, 105)) # summer
print(get_name(sample_no, sample_name, 777)) # ?

• 입력
  • 학생 번호 리스트 : s_no
  • 학생 이름 리스트 : s_name
  • 찾는 학생 번호 : find_no
• 출력
  • 해당하는 학생 이름 : 찾음
  • ? : 못 찾음

2. 선택 정렬

1) 간단하게 구현한 선택 정렬

def find_min_idx(a):
    n = len(a)
    min_idx = 0
    for i in range(1, n):
        if a[i] < a[min_idx]:
            min_idx = i
    return min_idx

def sel_sort(a):
    result = []
    while a:
        min_idx = find_min_idx(a)
        value = a.pop(min_idx)
        result.append(value)
    return result

d = [2,4,5,1,3]
print(sel_sort(d))

• result = [] : 새 리스트 생성하여 정렬된 값 저장
• value = a.pop(min_idx) : 찾은 최솟값을 a 리스트에서 pop

2) 선택 정렬 알고리즘

def sel_sort(a):
    n = len(a)
    for i in range(0, n-1):
        min_idx = i
        for j in range(i+1, n):
            if a[j] < a[min_idx]:
                min_idx = j

        a[i], a[min_idx] = a[min_idx], a[i]  

• for j in range(i+1, n): : i부터 끝까지 최솟값을 찾음
• a[i], a[min_idx] = a[min_idx], a[i] : 리스트 안에서 두 자료의 값의 위치 변경

3) 성능

• 이전 동명이인 찾기 알고리즘과 비슷 : 연산횟수 n(n-1)/2

  O(n^2)

4) 응용 : 내림차순 정렬

def sel_reverse(a):
    n = len(a)
    for i in range(0, n-1):
        max_idx = i
        for j in range(i+1, n):
            if a[j] > a[max_idx]:
                max_idx = j
            a[i], a[max_idx] = a[max_idx], a[i]

3. 삽입 정렬

1) 간단하게 구현한 삽입 정렬

def find_ins_idx(r, v):
    for i in range(0, len(r)):
        if v < r[i]:
            return i
    return len(r)

def ins_sort(a):
    result = []
    while a:
        value = a.pop(0)
        ins_idx = find_ins_idx(result, value)
        result.insert(ins_idx, value)
    return result

d = [2,4,5,1,3]
print(ins_sort(d))

• ins_idx = find_ins_idx(result, value) : 꺼낸 값을 어느 위치에 넣을 지 정함
• def find_ins_idx(r, v): : 리스트 r에서 v가 들어가야할 위치를 정해주는 함수
• for i in range(0, len(r)): : 이미 정렬된 r을 앞에서부터 순차적으로 탐색
• if v < r[i]: return i : v값보다 i번째 위치의 값이 더 크면 r[i] 바로 앞에 놓여야 정렬의 순서가 맞음
• return len(r) : 적절한 위치를 못 찾았을 때, v가 r의 모든 자료보다 크기 때문에 r의 맨 뒤로 위치
• result.insert(ins_idx, value) : 찾은 위치에 해당 값 넣고, 나머지 값들은 그에 따라 한 칸씩 뒤로 밀려남.

2) 삽입 정렬 알고리즘

def ins_sort(a):
    n = len(a)
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = key

d = [2,4,5,1,3]
ins_sort(d)
print(d)

• for i in range(1, n): : 1부터 n-1까지 탐색
• key = a[i] : i번 위치에 있는 값을 key로 설정
• j = i - 1 : j를 i 바로 왼쪽의 값으로 설정
• while j >= 0 and a[j] > key: : 리스트의 j번 위치에 있는 값과 키를 비교하여 key가 삽입될 위치 찾음
• a[j+1] = a[j] : j가 key값보다 크기 때문에 한 칸 옆으로 미룸
• a[j+1] = key : 찾은 삽입 위치에 key 저장

ex)

3) 성능

O(n^2)

4) 내림차순 삽입 정렬

def inf_sort(a):
    n = len(a)
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] < key:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = key

4. 병합 정렬

• 그룹을 나눠서 비교 후 정렬
• 재귀 이용

1) 간단 코드

def merge_sort(a):
    n = len(a)

    if n <= 1:
        return a
    
    mid = n // 2
    g1 = merge_sort(a[:mid])
    g2 = merge_sort(a[mid:])

    result = []

    while g1 and g2:
        if g1[0] < g2[0]:
            result.append(g1.pop(0))
        else:
            result.append(g2.pop(0))

    while g1:
        result.append(g1.pop(0))
    while g2:
        result.append(g2.pop(0))
    return result

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(merge_sort(d))

• if n <= 1: return a : 종료 조건. 정렬할 리스트의 자료 개수가 한 개 이하면 정렬 불필요.
• mid = n // 2 : 중간점을 기준으로 그룹을 2개로 나눔
• g1 = merge_sort(a[:mid]); g2 = merge_sort(a[mid:]) : 재귀 함수를 통해 두 그룹 정렬함
• while g1 and g2: : 두 그룹에 자료가 모두 남아있는 경우
• if g1[0] < g2[0]: result.append(g1.pop(0)) : 맨 앞 두 원소만 비교 후 더 작은 원소는 result에 넣고 기존 그룹에서 삭제함.
• while g1: result.append(g1.pop(0)) : 그룹 내 남은 원소들 result 값에 채워넣음
• a[:mid] : 리스트의 0번부터 mid번 전까지

2) 재귀 호출

병합 정렬 알고리즘 : 병합 정렬을 하는 과정에서 나누어진 리스트를 다시 두 번의 병합 정렬로 정렬하는 것

3) 병합 정렬 알고리즘

def m_sort(a):
    n = len(a)
    if n <= 1:
        return
    mid = n // 2
    g1 = a[:mid]
    g2 = a[mid:]

    m_sort(g1)
    m_sort(g2)

    i1 = 0
    i2 = 0
    ia = 0

    while i1 < len(g1) and i2 < len(g2):
        if g1[i1] < g2[i2]:
            a[ia] = g1[i1]
            i1 += 1
            ia += 1
        else:
            a[ia] = g2[i2]
            i2 += 1
            ia += 1
    while i1 < len(g1):
        a[ia] = g1[i1]
        i1 += 1
        ia += 1
    while i2 < len(g2):
        a[ia] = g2[i2]
        i2 += 1
        ia += 1           

    
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
m_sort(d)
print(d)

• 입력 리스트 값 내에서 값들을 직접 변경함.

4) 성능 분석

분할 정복(divide and conquer) : 큰 문제를 작은 문제로 나누어서 푸는 방법

• 복잡도 : O(n * log n)

5) 내림차순

def m_sort(a):
    n = len(a)
    if n <= 1:
        return
    mid = n // 2
    g1 = a[:mid]
    g2 = a[mid:]

    m_sort(g1)
    m_sort(g2)

    i1 = 0
    i2 = 0
    ia = 0

    while i1 < len(g1) and i2 < len(g2):
        if g1[i1] > g2[i2]:
            a[ia] = g1[i1]
            i1 += 1
            ia += 1
        else:
            a[ia] = g2[i2]
            i2 += 1
            ia += 1
    while i1 < len(g1):
        a[ia] = g1[i1]
        i1 += 1
        ia += 1
    while i2 < len(g2):
        a[ia] = g2[i2]
        i2 += 1
        ia += 1           

5. 퀵 정렬

• ‘그룹을 둘로 나눠 재귀 호출’하는 방식은 병합 정렬과 같지만, 그룹을 나눌 때 미리 기준과 비교해서 나눈다
• 즉, 먼저 기준과 비교해서 그룹을 나눈 후 각각 재귀 호출 후 합치는 방식

1) 간단 코드

def qsort(a):
    n = len(a)

    if n <= 1:
        return a
    
    pivot = a[-1]
    g1 = []
    g2 = []

    for i in range(0, n-1):
        if a[i] < pivot:
            g1.append(a[i])
        else:
            g2.append(a[i])
    return qsort(g1) + pivot + qsort(g2)

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(qsort(d))

• pivot = a[-1] : 기준 값을 설정 후, 기준에 맞춰 그룹을 설정함
• for i in range(0, n-1): : 기준값이 현재 맨 마지막 값이기 때문에 기준값 전까지 비교
• if a[i] < pivot: g1.append(a[i]) : 기준값과 비교 후 기준값보다 작으면 g1, 큰 경우 g2에 저장
• return qsort(g1) + pivot + qsort(g2) : 각 그룹에 대해 재귀호출을 통해 퀵 정렬 수행, 기준값과 합쳐 하나의 리스트로 리턴함.

2) 퀵 정렬 알고리즘

def quick_sort_sub(a, start, end):
    if end - start <= 0:
        return
    
    pivot = a[end]
    i = start
    for j in range(start, end):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1

    a[i], a[end] = a[end], a[i]
    quick_sort_sub(a, start, i-1)
    quick_sort_sub(a, i+1, end)

def quick_sort(a):
    quick_sort_sub(a, 0, len(a) - 1)

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
quick_sort(d)
print(d)

• 기준 값(현재는 맨 마지막의 값)을 정하고 그에 맞춰 리스트 안에서 위치 설정
• [기준값들보다 작은값들, 기준값, 기준값들보다 큰 값들]
• quick_sort_sub(a, start, i-1) : 기준값을 제외하고 기준값보다 작은 값들을 재귀 호출로 재정렬

3) 성능 분석

• 최악의 경우 : O(n^2) - 기준값이 최소, 최댓값인 경우
• 평균의 경우 : O(n * log n)

6. 이분 탐색 = 이진 탐색

• 조건 : 리스트가 정렬되어 있음
• 탐색 후 해당 인덱스 반환, 없으면 -1

1) 원리

1. 중간 위치 찾기
2. 찾는 값과 중간 위치 값 비교
3. 같다면 인덱스 반환
4. 찾는 값이 중간 위치값보다 큼 : 중간 값 기준 오른쪽으로 재탐색
5. 찾는 값이 중간 위치값보다 작음 : 중간 값 기준 왼쪽으로 재탐색

2) 이진 탐색 알고리즘

def binary_search(a, x):
    start = 0
    end = len(a) - 1

    while start <= end:
        mid = (start + end) // 2
        if x == a[mid]:
            return mid
        elif x > a[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return -1

d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search(d, 36))
print(binary_search(d, 50))

3) 재귀호출을 이용한 이진 탐색 알고리즘

def binary_recur(a, x, start, end):
    if start > end:
        return -1

    mid = (start + end) // 2
    if x == a[mid]:
        return mid
    elif x > a[mid]:
        return binary_recur(a, x, mid + 1, end)
    else:
        return binary_recur(a, x, start, mid - 1)

def binary_recursion(a, x):
    return binary_recur(a, x, 0, len(a)-1)


d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_recursion(d, 36))

7. 정렬 알고리즘

• 1) 선택 정렬
  • 동작 원리 : 남은 자료 중 최솟값을 뽑아 차례로 배치
  • 계산 복잡도 : O(n^2)
• 2) 삽입 정렬
  • 동작 원리 : 자료를 하나씩 적절한 위치에 삽입
  • 계산 복잡도 : O(n^2)
• 3) 병합 정렬
  • 동작 원리 : 그룹을 나눈 후 그룹을 기준으로 재귀호출을 통해 각각 정렬 후 병합
  • 계산 복잡도 : O(n * log n)
• 4) 퀵 정렬
  • 동작 원리 : 기준을 선택 해 기준에 맞게 그룹을 나눈 후 그룹별로 재귀호출을 통해 정렬
  • 계산 복잡도 : O(n * log n)
• 5) 거품 정렬
  • 동작 원리 : 앞뒤로 이웃한 자료 비교 후 크기가 뒤집힌 경우 순서를 변경
  • 계산 복잡도 : O(n^2)