정렬(Sort), 탐색(Search)

1 정렬

• 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업
  • [4,5,1,2,3,4] → [1,2,3,4,4,5]

1.1 Python 리스트 정렬 함수

• sorted()

  • 내장 함수(built-in function)

  • 정렬된 새로운 리스트를 얻어냄 (반환함)

  • 해당 리스트는 달라지지 않는다

    L2 = sorted(L, reverse=True)
    

• sort()

  • 리스트의 메서드(method) - 리스트 자료형이 제공하는 기능이다

  • 해당 리스트를 정렬함

    L.sort(reverse=True)

• key 활용

  • key는 정렬 함수의 파라미터로 key에 주어진 함수를 기준으로 삼아 정렬한다

  • 문자열 길이로 정렬하고 싶은 경우

    sorted(L, key=lambda x: len(x))
    sorted(L, key=len) # 강의에 나오지는 않았으나.. 가능한 방법

  • 또 다른 예시(각 원소가 딕셔너리일 때)

    # 이름을 오름차순으로 정렬
    L = [{'name':'John', 'score':83}, {'name':'Paul', 'score':34}]
    L.sort(key=lambda x: x['name'])

2 탐색 알고리즘

2.1 선형 탐색(Linear Search)

• 리스트의 처음부터 순차적으로 탐색하는 방법
• 찾으려는 원소가 끝에 있거나, 리스트의 길이가 길 수록 오래걸린다
• 선형 시간 연산, 리스트의 길이에 비례하는 시간 소요
  → O(n)
• 최악의 경우: 모든 원소를 다 비교해야 하는 경우(찾아야하는 원소가 끝에 있는 경우)

def linear_search(L, x):
	i = 0
	# 탐색 (i가 L 안을 벗어나지 않도록, L[i] 값이 같지 않으면 i를 증가
	# 즉, i가 찾는 원소와 같다면 반복문이 멈추게 된다
	while i < len(L) and L[i] != x:
		i += 1
	
	# i가 len(L)보다 작으면 찾는 값이 리스트 안에 있는 것
	if i < len(L):
		return i
	else: # i가 len(L)보다 크면 찾는 값이 리스트 안에 없는 것
		return -1

• index()와 다르게 리스트에 없는 값을 입력해도 오류가 나지 않는다

2.2 이진 탐색(Binary Search)

• 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능
• 리스트가 크기 순으로 정렬되어 있다는 성질을 이용하는 것
• 찾는 원소가 middle보다 작거나, 큰지를 판단해 탐색 범위를 1/2씩 줄여나가는 원리
  
• 한 번 비교가 일어날 때마다 리스트 반씩 줄인다 (divide & conquer)
  → $O(log_2n)$
  

def binary_search(L, x):
    lower = 0
    upper = len(L) - 1
    idx = -1
    
    while lower <= upper:
        middle = (lower + upper)//2
        if L[middle] == x:
            idx = middle
            break
        elif L[middle] < x:
            lower = middle + 1
        else:
            upper = middle - 1
    
    return idx