Python algorithm 개념 및 실습 - 정렬(2)

알고리즘이란 ?

• 어떤 일을 하기 위한 명령의 집합
• 문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
• 어떤 문제를 해결하기 위한 절차나 방법

 

알고리즘 복잡도

• Complexity
  • 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
• 알고리즘의 성능을 객관적으로 평가하는 기준
  • 시간복잡도(time complexity) : 실행 횟수로 판단
  • 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
• 빅오 표기법 ( Big O Notation)
  • 알고리즘이 얼마나 빠른지 표시하는 방법
  • 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
  • 연산의 횟수를 비교함
  • O(n) : 계산 복잡도 
    • O : 빅 O
    • n : 연산 횟수
    • O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
    • O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
    • O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
    • O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
    • O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
    • O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑

 

병합정렬 : 분해 + 병합. 주어진 리스트 안의 자료를 큰수부터 작은 수 순서로 배열하는 정렬

• 알고리즘 복잡도 : O(nlogn)

def merge_sort1(list1):

    # 리스트 크기 구하기

    size = len(list1)

    # 종료 조건 : 분해, 병합을 안해도 되는 상황

    if size <= 1:  # 하나만 있으면 정렬할 필요 없음

        return list1

    # 분해 작업

    mid = size // 2  # 중간 구하기(정수나눗셈)

 

   # 재귀호출로 첫번째 그룹[6, 8, 3, 9, 10] => mid=2 g1 = [6,8], g2 = [3,9,10] .. => 하나가 남을 때까지 계속 루프

    g1 = merge_sort1(list1[:mid])

    # 재귀호출로 두번째 그룹[1, 2, 4, 7, 5] => mid=2 g1 = [1,2], g2 = [4,7,5] ..=> 하나가 남을 때까지 계속 루프

    g2 = merge_sort1(list1[mid:])

    # 병합 작업

    # python은 리스트가 비어 있으면 False로 인식.

    result = []

    # len(g1) > 0 and

    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

if __name__ == "__main__":

    list1 = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]

    print("병합 정렬 : ", merge_sort1(list1))

 

 

하나의 리스트로 작성

def merge_sort(list1):

    # 리스트 구하기

    size = len(list1)

    # 종료 조건

    if size <= 1:  # 하나만 있으면 정렬할 필요 없음

        return list1

    # 분해 작업

    mid = size // 2  # 중간 구하기

    g1 = list1[:mid]

    g2 = list1[mid:]

    merge_sort(g1)

    merge_sort(g2)

    # 병합 작업

    # 변수 사용

    i1, i2, ia = 0, 0, 0

    # 두 그룹에 자료가 남아 있을 때까지

    while i1 < len(g1) and i2 < len(g2):

        if g1[i1] < g2[i2]:

            list1[ia] = g1[i1]

            i1 += 1

            ia += 1

        else:

            list1[ia] = g2[i2]

            i2 += 1

            ia += 1

    # 남아 있는 자료 결과에 추가

    while i1 < len(g1):

        list1[ia] = g1[i1]

        i1 += 1

        ia += 1

    while i2 < len(g2):

        list1[ia] = g2[i2]

        i2 += 1

        ia += 1

if __name__ == "__main__":

    list1 = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]

    merge_sort(list1)

    print("병합 정렬 : ", list1)

 

 

퀵정렬 : 정렬할 전체 원소에 대해 정렬을 하지 않고 기준점(=pivot)을 중심으로 작은값은 왼쪽 부분, 큰 값은 오른쪽 부분으로 분할해서 정렬

def quick_sort(list1):

    # 리스트 크기 구하기

    size = len(list1)

    # 종료

    if size <= 1:

        return list1

    # 기준값 정하기

    pivot = list1[-1]  # 첫번째는 5

    # 기준값 보다 작은 요소 담기

    g1 = []

    # 기준값보다 큰 요소 담기

    g2 = []

    # 정렬할 땐 for문 사용

    for i in range(0, size - 1):  # 마지막 값은 기준값이기 때문에 제외

        if list1[i] < pivot:

            g1.append(list1[i])  # g1 = [3,1,2,4] 5보다 작은 값

        else:

            g2.append(list1[i])  # g2 = [6,8,9,10,7] 5보다 큰 값

    # 결과값 합치기

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

if __name__ == "__main__":

    list1 = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]

    print("퀵정렬 : ", quick_sort(list1))

 

하나가지고 정렬하기

def quick_sort(list1, start, end):

    # 종료

    # 하나의 리스트가 0이면 더이상 할 필요 없음

    if end - start <= 0:

        return

   # 기준값 정하기

    pivot = list1[end]

    i = start

    # 정렬할 땐 for문 사용

    for j in range(start, end):

        if list1[j] < pivot:

            list1[i], list1[j] = list1[j], list1[i]

            i += 1

    list1[i], list1[end] = list1[end], list1[i]

    # 재귀호출

    quick_sort(list1, start, i - 1)

    quick_sort(list1, i + 1, end)

if __name__ == "__main__":

    list1 = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]

# start값 = 0, end값 = len(list1)-1

    quick_sort(list1, 0, len(list1) - 1)

    print("퀵정렬 : ", list1)