정렬(Sort) , 탐색(Search)

python 리스트의 정렬

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

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

• 정렬 순서는 알파벳 순서 (사전 순서)를 따른다.
• 문자열의 길이가 길다고 더 큰 것이 아니다.
• 문자열 길이 순서로 정렬하려면 ? → 정렬에 이용하는 키(key)를 지정한다.

    L = ["abcd", "xyz" , "spam"]
    sorted(L , key = lambda x : len(x)) # 리스트의 원소를 x로 지정 -> key값을 x의 길이로 지정
    # ["abcd", "spam" , "xyz" ]

• dict 타입의 리스트를 정렬하기

    L = [{"name" : "J" , "score" : 83} , {"name" : "J" , "score" : 87}]
    L.sort(key = lambda x : x[score] , reversed = True)
    #[{"name" : "J" , "score" : 87}{"name" : "J" , "score" : 83}]

탐색 알고리즘

선형 탐색 (Linear Search)

• 지정한 index에서 선형적으로 (일정값을 증가시키며) 값을 찾는 탐색 방법
  • 최악의 경우 (찾고자 하는 값이 가장 끝에 있는 경우) 모든 원소를 전부 비교해보아야한다.
• → 리스트의 길이에 비례하는 시간이 소요된다 ( 시간복잡도 : O(N) )

def Linear Search(lst , num):

    idx = 0
    while (idx < len(lst)) :
        if(lst[idx] == num):
            return idx
        else : 
            idx += 1

    return -1         

이진 탐색 (Binary Search)

• 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 사용가능
• → 크기 순으로 정렬되어 있다는 성질을 이용한 알고리즘.
• <그림 1: 정렬된 리스트에서 30을 찾는 경우>

1. lower와 upper를 통해 middle값을 찾는다.
   • 찾고자 하는 값이 middle 번째 값보다 크다면 middle 이전 index는 탐색 대상에서 제외한다.
     • middle +1 값은 lower가 된다.
   • 찾고자 하는 값이 middle 번째 값보다 작다면 middle 이후 index는 탐색 대상에서 제외한다.
     • middle -1 값은 upper가 된다
2. middle 번째 값이 찾고자 하는 대상의 값과 동일할 때까지 반복한다.

한번의 비교가 일어날 때마다 리스트 탐색 범위를 반씩 줄임 (divid and conquer) → 시간복잡도 : O(logn)

• 이진 탐색 종료 규칙
  • lower ≤ upeer

이진 탐색 실습 문제

• 이진 탐색 구현

def solution(L, x):

    lower = 0 
    upper = len(L)-1

    while(lower <= upper):
        middle = (lower + upper) // 2

        if(L[middle] == x):
            return middle

        if(L[middle] > x):
            upper = middle - 1
        elif(L[middle] < x) :
            lower = middle +1

    return -1