[알고리즘] 배열-정렬과 탐색(Sort&Search)

오늘은 배열의 정렬과 탐색에 대해서 알아봅시다!!

정렬 알고리즘

정렬: 배열안에 들어있는 원소들을 정해진 기준, 규칙에 따라서 나열

python 리스트의 정렬

1. sorted(L)

• 내장 함수 (built-in function)
• 정렬된 새로운 리스트 반환

2. L.sort()

• 리스트의 메서드 (method)
• 해당 리스트 정렬

• 순서를 반대로 정렬(역순): reverse=True

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

• 문자열로 이루어진 리스트의 경우: 정렬 순서는 사전 순서(알파벳 순서)를 따름. 대문자를 소문자보다 우선
• key 지정하여 정렬 방식 설정
  • 정렬에 이용하는 키(key)를 지정하여 정렬 방식을 설정할 수 있다.

  # 문자열의 길이 순 정렬
  # 길이가 같은 경우, 앞에 나온 문자를 앞에 정렬
  sorted(L, key=lambda x:len(x))
  
  # 정렬- 키를 지정하는 또 다른 예 (딕셔너리)
  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(log n)$

lower = 0
upper = len(L) - 1
idx = -1
while lower <= upper:
	middle = (lower + upper) // 2
    if L[middle] == targer:
    ...
    elif L[midle] < targer:
    	lower = ...
    else: 
    	upper = ...