정렬(Sort), 탐색(Search)

1. 정렬(Sort)

리스트 정렬

(1) sorted()

• 내장함수
• 정렬된 새로운 리스트 반환

L = [3, 8, 2, 7, 6, 10, 9]
L2 = sorted(L)

(2) sort()

• list의 method
• 기존 리스트를 정렬

L = [3, 8, 2, 7, 6, 10, 9]
L.sort()

만약 정렬순서를 내림차순으로 바꾸고 싶다면 reverse = True 추가해주기
* 문자열로 이루어진 리스트의 경우, 정렬 순서는 알파벳 순서를 따름.*

key를 이용하여 정렬 기준 바꾸기

ex1) 문자열 길이 순으로 정렬

L = ['abcd', 'xyz', 'spam']
sorted(L, key = lambda x: len(x))  
# 결과 : ['xyz', 'abcd', 'spam']

ex2) score가 높은 순으로 정렬

L = [{'name' : 'John', 'score' : 83},
	{'name' : 'Paul', 'score' : 92}]
L.sort(key = lambda x: x['score'], reverse = True)

2. 탐색(Search)

데이터에서 특정 원소를 찾아내는 작업

(1) 선형탐색(Linear Search) 혹은 순차탐색

• 시간복잡도 : O(n)

(2) 이진탐색(binary search)

• 탐색하려는 배열이 이미 정렬되어있을 경우 사용가능
• 시간복잡도 : O(logn)

def solution(L, x):
    l = 0
    r = len(L) - 1
    while l <= r:
        m = (l + r) // 2
        if L[m] == x:
            return m
        elif L[m] < x:
            l = m + 1
        elif L[m] > x:
            r = m - 1
    return -1