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

알고리즘이란 ?

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

 

알고리즘 복잡도

• 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(n ²)

# 이중 for문 사용 - 특정 위치부터 자료 값 중 최솟값의 위치를 찾은 후

# 정렬을 원하는 자리와 교환

# 정렬할 때 대부분 이중 for문을 사용

 

# 오름차순

def selection_sort1(list1):

    size = len(list1)

    for i in range(0, size - 1):  # 0,1,2,3 자리까지만 정렬

        # 최솟값에 대한 변수

        min_idx = i

        for j in range(i + 1, size):

            if list1[j] < list1[min_idx]:

                min_idx = j

        # for문 종료 후 최솟값의 위치를 확인

        # 찾은 최솟값과 정렬 위치를 교환

        list1[i], list1[min_idx] = list1[min_idx], list1[i]

# 내림차순

def selection_sort2(list1):

    size = len(list1)

    for i in range(0, size - 1):

        max_idx = i

        for j in range(i + 1, size):

            if list1[j] > list1[max_idx]:

                max_idx = j

        list1[i], list1[max_idx] = list1[max_idx], list1[i]

if __name__ == "__main__":

    list1 = [35, 9, 2, 85, 17]

    print("오름차순")

    selection_sort1(list1)

    print("선택 정렬 : ", list1)

   

    print("내림차순")

    selection_sort2(list1)

    print("선택 정렬 : ", list1)

 

 

 

삽입 정렬 : 제일 처음에 있는 요소를 기준으로 나머지 요소들과 비교하면 정렬

# result에 v가 들어가야 할 위치를 리턴하는 함수

def find_ins_idx(r, v):

    # r은 이미 정렬된 리스트 상태

    # r의 자료를 앞에서부터 확인

    for i in range(0, len(r)):

        # v가 어느 위치에 들어가는지 찾기

        if v < r[i]:

            return i

    # 적절한 위치를 못 찾을 경우에는 v가 이미 정렬된 리스트보다

    # 크다는 뜻이므로 맨 뒤에 삽입

    return len(r)

def insertion_sort1(list1):

    result = []

    while list1:

        value = list1.pop(0)  # 하나의 값만 가지고 나옴.

        ins_idx = find_ins_idx(result, value)

        result.insert(ins_idx, value)

    return result

if __name__ == "__main__":

    list1 = [2, 4, 5, 1, 3]

    print("삽입 정렬 : ", insertion_sort1(list1))

 

 

하나의 리스트에서 구현

# 오름차순 정렬

def insertion_sort1(list1):

    # 현재 리스트 길이 구하기

    size = len(list1)

    # for 1 ~ n

    for i in range(1, size):

        # i번 위치에 있는 값을 key 변수에 저장

        key = list1[i]

        # j를 i바로 왼쪽 위치로 지정

        j = i - 1

        # 리스트의 j번 위치에 있는 값과 key를 비교해 key가 삽입될 위치 찾기

        # while문

        # j는 0 자리 앞으로는 갈 수 없음

        while j >= 0 and list1[j] > key:

            list1[j + 1] = list1[j]

            j -= 1

        # while문 종료 후 찾은 삽입 위치에 key 저장

        list1[j + 1] = key

if __name__ == "__main__":

    list1 = [2, 4, 5, 1, 3]

    insertion_sort1(list1)

    print("삽입 정렬 : ", list1)