정렬

1. 선택 정렬

가장 작은 값을 앞으로 보내는 정렬

def selectionSort(alist) :
    for i in range(len(alist)) :
                   minPos = getMinPos(alist, i)
                   temp = alist[minPos]
                   alist[minPos] = alist[i]
                   alist[i] = temp

def getMinPos(alist, start) :
    minPos = start
    for i in range(start+1, len(alist)) :
        if alist[i] < alist[minPos] :
            minPos = i
    return minPos

alist = [1, 4, 5, 9, 8, 2, 7]
selectionSort(alist)
print(alist)

2.순차탐색

앞에서부터 순차적으로 탐색한다.

def sequentialSearch(alist, item) :
    pos = 0
    found = False

    while pos < len(alist) and not found :
        if alist[pos] == item :
            found = True
        else :
            pos += 1

    return found

testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))

3.이진탐색

def search_binary(list, value) :
    low = 0
    high = len(list) - 1
    while low <= high :
        middle = (low+high) // 2
        if list[middle] > value :
            high = middle - 1
        elif list[middle] < value :
            low = middle + 1
        else :
            return middle
    return -1

myList = [2, 6, 11, 13, 18, 20, 22, 27, 29, 30, 34, 38, 41, 42, 45, 47]
print('인덱스 = ', search_binary(myList, 34))

4.삽입 정렬

def find_ins_idx(r, v) :
    for i in range(0, len(r)) :
        if v < r[i] :
            return i
    return len(r)

def ins_sort(a) :
    result = []
    while a :
        value = a.pop(0)
        ins_idx = find_ins_idx(result, value)
        result.insert(ins_idx, value)
    return result

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

5.병합정렬(Merge Sort)

두 개의 값을 비교하여 정렬한다.

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

    mid = n // 2
    g1 = merge_sort(a[:mid])
    g2 = merge_sort(a[mid:])

    result = []
    while g1 and g2 :
        if g1[0] < g2[0] :
            result.append(g1.pop(0))
        else :
            result.append(g2.pop(0))

    while g1 :
        result.append(g1.pop(0))
    while g2 :
        result.append(g2.pop(0))
    return result

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

6.퀵 정렬 (Quick Sort)

병합 정렬과 같이 두 그룹을 비교하지만 비교하기 전 기준을 세워 반을 쪼갠 후 비교한다.

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

    pivot = a[-1]
    g1 = []
    g2 = []
    for i in range(0, n-1) :
        if a[i] < pivot :
            g1.append(a[i])
        else :
            g2.append(a[i])

    return quick_sort(g1) + [pivot] + quick_sort(g2)

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

---

알고리즘

좋은 알고리즘이란 빠른 처리 속도를 내는 알고리즘이 좋은 코드이다.
복잡한 코드의 경우 계산 복잡도를 통해 좋은 알고리즘을 구분할 수 있다.

1.절댓값

✔️ 절대값 알고리즘 1 (부호 판단) : int 타입으로 출력 됨.

import math

def abs_sign(a) :
    if a >= 0 :
        return a
    else :
        return -a

print(abs_sign(5))
print(abs_sign(-3))

✔️ 절대값 알고리즘 2 (제곱 - 제곱근) : float 타입으로 출력 됨.

import math

def abs_square(a) :
    b = a * a
    return math.sqrt(b)

print(abs_square(5))
print(abs_square(-3))

✔️ 1부터 n까지 연속한 숫자의 합 구하기

방법 1

def sum_n(n) :
    return n * (n + 1) // 2

print(sum_n(10))
print(sum_n(100))

방법 2

n = 10
result = sum([ i for i in range(1, n+1)])

print(result)

2.대문자 O표기법

✔️ 계산 복잡도 표현

✔️ 시간 복잡도 표현

✔️ 공간 복잡도 표현

최댓값 구하기

def find_max(a) :
    n = len(a)
    max_v = a[0]
    for i in range(1, n) :
        if a[i] > max_v :
            max_v = a[i]
    return max_v

v = [17, 92, 18, 33, 58, 7, 73, 44, 53]
print(find_max(v))

최댓값의 위치 구하기

def find_max_idx(a) :
    n = len(a)
    max_idx = 0
    for i in range(1, n) :
        if a[i] > a[max_idx] :
            max_idx = i
    return max_idx

v = [17, 92, 18, 33, 58, 7, 73, 44, 53]
print(find_max_idx(v))