정렬 / 탐색

선택정렬

: n >= 1 개의 서로 다른 정수의 집합을 정렬

"정렬되지 않은 정수들 중에서 가장 작은 값을 찾아서 정렬된 리스트 다음 자리에 놓는다."

# 선택 정렬
def SelectionSort(a, n): # n개의 정수 a[0]부터 a[n-1]까지 비감소 순으로 정렬
    for i in range(n): # a[i]와 a[n-1] 사이에 가장 작은 정수를 찾음
        for j in range(i, n):
            if a[i] > a[j]:
                temp = a[i]
                a[i] = a[j]
                a[j] = temp
    return a

list = list()
num = int(input()) # 리스트 크기 입력
for i in range(num):
    new = int(input())
    list.append(new)

print(SelectionSort(list, num))

---

이원 탐색

: 이미 정렬된 배열 a[0]...a[n-1]에서 x = a[j]인 j를 반환

# 입력값 : 리스트, key

def BinarySearch(list, key):
    left = 0
    right = len(list) - 1

    while(left <= right):
        middle = int((left + right) / 2)

        if key < list[middle]:
            right = middle - 1
        elif key > list[middle]:
            left = middle + 1
        elif key == list[middle]:
            return middle

    return -1

def SelectionSort(a, n):
    for i in range(n):
        for j in range(i, n):
            if a[i] > a[j]:
                temp = a[i]
                a[i] = a[j]
                a[j] = temp
    return a

n = int(input('배열 크기 : '))
list = list()
for i in range(n):
    list.append(int(input()))
key = int(input('찾고자 하는 키 : '))

list = SelectionSort(list, n) # 정렬

print(BinarySearch(list, key))

---

순환 알고리즘

: 수행이 완료되기 전에 자기 자신을 다시 호출

• 직접 순환 (direct recursion) : 함수가 그 수행이 완료되기 전에 자기 자신을 다시 호출
• 간접 순환 (indirect recursion) 호출 함수를 다시 호출하게 되어 있느 다른 함수를 호출

---

순환 이원 탐색

: 재귀호출을 통한 이원 탐색

# 입력값 : 리스트, key

def RotateBinarySearch(list, key, left, right):
    middle = int((left + right)/2)
    if(left <= right):
        if key < list[middle]:
            return RotateBinarySearch(list, key, left, middle - 1)
        elif key > list[middle]:
            return RotateBinarySearch(list, key, middle + 1, right)
        elif key == list[middle]:
            return middle
    else:
        return -1

def SelectionSort(a, n):
    for i in range(n):
        for j in range(i, n):
            if a[i] > a[j]:
                temp = a[i]
                a[i] = a[j]
                a[j] = temp
    return a

n = int(input('배열 크기 : '))
list = list()
for i in range(n):
    list.append(int(input()))
key = int(input('찾고자 하는 키 : '))

list = SelectionSort(list, n) # 정렬
left = 0
right = n - 1
print(RotateBinarySearch(list, key, left, right))