2-1. [정렬], [이분탐색]

1. 선택정렬 (최소값을 찾아서 하나씩 넣는다)

def find_min_idx(a):
    min_i = 0
    for i in range(1, len(a)):
        if a[i] < a[min_i]:
            min_i = i
    return min_i


# 선택정렬: 최소값을 찾아서 하나씩 넣는다... O(N^2)

def sel_sort(a):
    rst = []
    while a:
        i = find_min_idx(a)
        v = a.pop(i)
        rst.append(v)

    return rst


d = [2, 4, 5, 1, 3]
print(sel_sort(d))

 

a = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
N = len(a)

for i in range(N - 1):
    min_i = i
    for j in range(i + 1, N):
        if a[j] < a[min_i]:
            min_i = j
    a[i], a[min_i] = a[min_i], a[i]

print(a)

 

 

2. 삽입정렬 (하나씩 꺼내서 순서 찾아 넣는다)

 

def find_ins_idx(a, v):
    for i in range(len(a)):
        if a[i] > v:
            return i
    return len(a)


# 삽입정렬: 하나씩 꺼내서 순서 찾아 넣는다... O(N^2)

def ins_sort(a):
    rst = []
    while a:
        v = a.pop(0)
        i = find_ins_idx(rst, v)
        rst.insert(i, v)

    return rst


d = [2, 4, 5, 1, 3]
print(ins_sort(d))

 

a = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
N = len(a)

for i in range(1, N):
    for j in range(i, 0, -1):
        if a[j - 1] > a[j]:
            a[j - 1], a[j] = a[j], a[j - 1]
        else:
            break

print(a)

 

 

3. 병합정렬 (각자 정렬한 후 합친다)

 

# 병합정렬: 두 그룹으로 분할해서 각자 정렬한 후 결과를 합친다... O(NlogN)

def merge_sort(a):
    if len(a) == 1:
        return a

    # 분할: 두 그룹으로 분할해서 각자 정렬한 후
    mid = len(a) // 2
    g1 = merge_sort(a[:mid])
    g2 = merge_sort(a[mid:])

    # 병합: 결과를 합친다
    rst = []
    while g1 and g2:
        if g1[0] < g2[0]:
            rst.append(g1.pop(0))
        else:
            rst.append(g2.pop(0))

    if g1:
        rst.extend(g1)
    else:
        rst.extend(g2)

    return rst


d = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print(merge_sort(d))

 

 

4. 퀵정렬 (나누고 각자 정렬한다)

 

# 퀵정렬: 피봇을 기준으로 두 그룹으로 분류한 뒤에 각자 정렬한다... O(NlogN)

def quick_sort(a):
    if len(a) <= 1:
        return a

    pivot = a[0]
    g1 = [x for x in a[1:] if x < pivot]
    g2 = [x for x in a[1:] if x >= pivot]

    return quick_sort(g1) + [pivot] + quick_sort(g2)  # 각자 정렬한다


d = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print(quick_sort(d))

 

 

5. 이진 탐색

 

# 반복문 이용... O(logN)

def binary_search(a, x):
    start = 0
    end = len(a) - 1

    while start <= end:
        mid = (start + end) // 2

        if a[mid] < x:
            start = mid + 1
        elif a[mid] > x:
            end = mid - 1
        else:
            # 조건 충족하는 값을 찾을 때
            return mid

    return -1


d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search(d, 36))

 

# 재귀 이용... O(logN)

def binary_search(a, x, start, end):
    if start > end:
        return -1

    mid = (start + end) // 2

    if a[mid] < x:
        return binary_search(a, x, mid + 1, end)
    elif a[mid] > x:
        return binary_search(a, x, start, mid - 1)
    else:
        return mid


d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search(d, 36, 0, len(d) - 1))

 

# 변형

def binary_search(a, x):
    start = 0
    end = len(a) - 1

    result = 0
    while start <= end:
        mid = (start + end) // 2

        # 조건을 만족하는 최대값을 찾을 때
        if a[mid] <= x:
            start = mid + 1
            result = mid
        else:
            end = mid - 1

    return result if result != 0 else -1


d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search(d, 36))