3강: 정렬(Sort), 탐색(Search)

---

Python 리스트의 정렬

1. sorted()

• 내장 함수(built-in function)
• 정렬된 새로운 리스트를 얻어냄

2. sort()

• 리스트의 매소드(method)
• 해당 리스트를 정렬함

정렬의 순서를 반대로

reverse = True

L2 = sorted(L,reverse = True)
L.sort(reverse = True)

정렬 - 문자열로 이루어진 리스트의 경우

• 정렬 순서는 사전순서(알파벳 순서)를 따름
  • (문자열 길이가 긴 것이 더 큰 것이 아님)
• 문자열 길이 순서로 정렬하려면?
  • 정렬에 이용하는 키(key)를 지정

정렬 - 키를 지정하는 또 다른 예

L = [{'name' : 'John' , 'score' : 83},{'name' : 'Paul' , 'score' : 92}]
L.sort(key = lambda x: x['score'], reverse = True)
-> 레코드 들을 점수 높은 순으로 정렬

---

탐색 알고리즘

1. 선형 탐색(Linear Search)

• 일렬로 나열된 자료를 왼쪽부터 오른쪽으로 차례대로 탐색
  

시간복잡도

• 리스트의 길이에 비례하는 시간소요
  • O(N)
• 최악의 경우 : 모든 원소를 다 비교해 보아야

2. 이진탐색(Binary Search)

• 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능
• 크기 순으로 정렬되어 있다는 성질 이용!
  

시간복잡도

• 한 번 비교가 일어날 때마다 리스트 반씩 줄임 (divide & conquer)
  • O(log N)

---

실습

이진 탐색 구현해보기

코드

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

---