자료구조📗 - python 정렬(sort), 탐색(search)

python 리스트의 정렬

1. sorted()
   • 내장 함수(built-in function)
   • 정렬된 새로운 리스트를 얻어냄
2. .sort()
   • 리스트의 메서드(method)
   • 해당 리스트를 정렬함

L = [3, 8, 2, 7]
L2 = sorted(L)
#L2 = [2, 3, 7, 8]
#L = [3, 8, 2, 7]

L.sort()
#L =[2, 3, 7, 8]

정렬의 순서를 반대로

reverse=True

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

문자열로 이루어진 리스트 정렬

• 정렬 순서는 사전 순서(알파벳 순서)를 따른다.
• Q. 문자열 길이 순서로 정렬하려면?
  -> 정렬에 이용하는 키(key)를 지정

L = ['abcd', 'xyz', 'spamm']
sorted(L, key = lambda x: len(x))
>>> ['xyz', 'abcd', 'spamm']

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

L=[{'name':'John', 'score': 83},
	{'name':'Paul', 'score': 92}]

L.sort(key=lambda x:x['name'])
# -> 레코드들을 이름 순서대로 정렬

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

탐색 알고리즘1 - 선형 탐색(Linear Search)

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

def linear_search(L,x):
    i = 0
    while i < len(L) and L[i] != x:
        i += 1
    if i < len(L):
        return i
    else:
        return -1

탐색 알고리즘2 - 이진 탐색(Binary Search)

• 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능
• 크기 순으로 정렬되어 있다는 성질 이용
• 한번 비교가 일어날 때마다 리스트 반씩 줄임(divide & conquer)
  -O(logn)