<자료구조와 알고리즘> 정렬 with Python

Python 리스트의 정렬 함수

1) sorted()

      - 내장 함수

      - 정렬된 새로운 리스트를 얻어낸다

2) sort()

      - 리스트의 메서드

      - 해당 리스트를 정렬한다

 

사용 방법

 L = [3,6,21,5]

L.sort()

L2 = sorted(L)

 

매개변수로 reverse = True를 주면 반대로 정렬된다

 

문자열로 정리를 하려면 어떻게 해야할까?

L = ['abcd', 'xyz', 'spam']

sorted(L, key=lambda x:len(x))

여기서 lambda는 파이썬의 익명함수 문법입니다

lambda 매개변수 : 표현식 형태로 표현합니다

그래서 key 에 x의 길이많큼 주는 것입니다

 

또 다른 예시로

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

{'name':'Paul','score':92}]

L.sort(key = lambda x: x['name']) ==> 레코드들을 이름순서대로 정렬한다는 뜻입니다

---

 

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

첫번쨰 인덱스부터 탐색하려는 값까지 하나 하나 비교해서 결과를 나타내는 것을 뜻합니다리스트의 길이에 비례하는 시간이 소요됩니다.이를 시간 복잡도로 나타내면 O(n) 라고 합니다.최악의 경우: 모든 원소를 다 비교해야 합니다.

 

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

 - 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능

 - 크기 순으로 정렬되어 있다는 성질을 이용

 - 인덱스가 0인 요소를 lower 그리고 전체 리스트 길이의 중간을 middle, 마지막 인덱스를 upper로 지정한 뒤

탐색하려는 수를 middle과 비교해서 작으면 middle을 포함해서 왼쪽에 있는 요소들을 삭제한 뒤 middle + 1 인덱스를 lower 로 시작하여 탐색을 진행한다.

 - 위와 같은 과정을 반복하여 lower와 upper를 계속 지정해줍니다. - 그렇게 원하는 값을 찾아냅니다 - 한 번 비교가 일어날 때마다 리스트가 반씩 줄어듭니다 ( divide & conquer ) - 이에 대한 시간 복잡도는 O(log n) 으로 표현할 수 있습니다

 

이진 탐색 코드의 구현

lower = 0
upper = len(L) - 1
idx = -1 // 발견되는 값에 대한 인덱스
while lower <= upper:
	middle = (lower + upper) // 중간
    if L[middle]= == target :
    	...
    elif L[middle] < target :
    	lower = ...
    else :
    	upper = ...

전체틀은 위와 같이 구현됩니다

 

알고리즘이 중요한 이유는 리스트나 다른 데이터의 값이 커졌을 때 알고리즘에 따라 걸리는 시간의 차이가 굉장히 많이 나기 때문입니다

 

**이진 탐색은 항상 정렬이 되어 있어야 합니다.

 

2가지 탐색(선형, 이진) 중 어떤 탐색방법을 쓰는 게 효율적일까요?

시간 복잡도에 따르면 이진 탐색이 더 빠릅니다. 하지만 이진 탐색이 항상 효율적이다. 라고 하기는 어렵습니다.

왜냐면 값을 탐색하기 위해 선형 탐색은 순차적으로 모든 요소들을 탐색해서 찾아내고 이진 탐색은 정렬한 이후 기존 배열을 절반으로 나눠서 탐색을 지속적으로 진행하기 때문이죠!

다만, 한번만 탐색을 한다고 생각했을 때 정렬을 하고 탐색하는 이진 탐색보다 한번씩 다 뒤지는 게 훨씬 이득이기 때문에 항상 이진 탐색이 효율적이다! 라고 하기에는 어렵습니다!

 

다음은 프로그래머스에서 제공하는 문제에 대한 저의 코드 풀이를 가져온 것입니다.

def solution(L, x):
    answer = 0
    lower = 0
    upper = len(L) - 1
    idx = - 1
    
    while lower <= upper:
        middle = (lower + upper) // 2 # //는 정수몫 연산자
        if L[middle] == x:
            answer = middle
            return answer
        elif L[middle] < x:
            lower = middle + 1
        else:
            upper = middle - 1
    answer = idx
    return answer