2. 정렬(Sort), 탐색(Search)

배열 - 정렬 (sort)과 탐색 (search)

정렬과 탐색은 많은 응용에 적용되는 알고리즘들 중에서도 가장 널리 알려져 있으며 활용도도 높은 것이라고 할 수 있다.
정렬과 탐색을 위한 여러 자료 구조와 알고리즘들이 있지만, 간단하게 선형 배열을 대상으로 정렬과 탐색의 기초를 배워본다.

정렬(sort)이란?

복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업.

Python의 리스트(list)를 이용한다면, 직접 정렬 알고리즘을 구현할 필요가 없다. list에 내장된 정렬 기능이 있기 때문인데, 아래 와같은 같은 두 방법이 대표적이다.

• 파이선 내장 함수 sorted()
• 리스트에 쓸 수 있는 메서드 .sort()

정렬 순서 반대로
reverse = True
L2 = sorted(L, reverse = True)
L.sort(reverse=True)

수치(number)가 아닌 데이터형의 정렬?

이 경우에는 문자열을 사전에 등장하는 순서에 따라 정렳나다. 문자열의 길이가 더 길다고 더 큰 문자로 취급하는 것이 아니다.
Python 문자열은 대문자가 소문자에 비해 무조건 우선한다. 그렇다면 만약 대소문자 구별을 무시하고 순전히 알파벳 순서에 따라 정렬하려면 어떻게 해야하는가?

• 문자열에 쓸 수 있는 메서드 .lower(), upper()로 통일하여 정렬하거나 casefold() 구분없이 비교하는 메서드가 존재한다.
  위 같은 방법을 쓰지 않는다면 아스키코드 값을 이용하여 대문자 알파벳 마지막 보다 클경우 특정값을 뺄셈연산 하는등 방법이 있을 것 같다.

문자열 길이 순서로 정렬하려면?
-> 정렬에 이용하는 키(key)를 지정
sorted(L, key=lambda x: len(x))

정렬 - 키를 지정하는 또 다른 예 : 딕셔너리(dict)

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

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

탐색(search)이란?

복수의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업. 기본적인 두가지

• 선형 탐색(linear search),또는 순차 탐색(sequential search): 순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아낸다. 배열의 길이에 비례하는 시간이 걸리므로 최악의 경우 배열에 잇는 모든 원소를 다 검사해야 할 수 있다.
• 이진 탐색(binary search):탐색하려는 배열이 이미 정렬되어 있는 경우에만 적용 가능. 배열의 가운데 원소와 찾으려 하는 값을 비교하면(크기 순으로 정렬되어 있다는 성질 이용) 왼쪽에 있을지 오른쪽에 있을지 알 수 있다. (만약 있다면) 그렇다면, 적어도 반대쪽에 없는 것은 확실 하므로 배열의 반을 탐색하지 않고 버릴 수 있다. 이 과정을 반복하면 원하는 값을 찾아낼 수 있다. O(log n)

이진 탐색 코드의 구현

def binary_search(L)
	lower = 0
    upper = len(L) - 1
    idx = -1

    while lower <= upper:
        middle = (lower + upper) // 2
        if L[middle] == target:
            idx = middle
            break
        elif L[middle] < target :
            lower = middle + 1
        else:
            upper = middle - 1
    return idx

이진 탬색 구현해보기.

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

#######################
def solution(L, x):
    lower = 0
    upper = len(L) - 1
    idx = -1

    while lower <= upper:
        middle = (lower + upper) // 2
        print(middle,L[middle],x)
        if L[middle] == x:
            idx = middle
            break
        elif L[middle] < x :
            lower = middle
        else:
            upper = middle

        if (lower - upper) == -1:
            if L[middle+1] == x:
                idx = middle+1
                break
            else:
                break
    return idx

이진 탐색이 선형 탐색보다 빠른 방법이긴 하나 뭔가를 찾으려 한다고 항상 이진 탐색을 적용하는 것이 답은 아니다.
이진 탐색을 쓰기 위해선 우선 배열을 정렬해야하고 크기순으로 정렬하는 것도 작업 시간이 들기에 일회성으로 탐색하는 것 이라면 굳이 크기 순으로 정렬할 필요보다 한번 선형탐색 하는 것이 낫다는 것이다.

본 글은 프로그래머스 - 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 정리한 글입니다.