더북(TheBook)

     

    2쉽게 설명한 삽입 정렬 알고리즘

     

    삽입 정렬로 줄 세우는 방법을 떠올려 보면서 프로그램을 만들어 봅니다.

     

    icon_cakewalk 프로그램 9-1

     

    쉽게 설명한 삽입 정렬 알고리즘

     

    ◉ 예제 소스 p09-1-isort.py

    # 쉽게 설명한 삽입 정렬

    # 입력: 리스트 a

    # 출력: 정렬된 새 리스트

     

    # 리스트 r에서 v가 들어가야 할 위치를 돌려주는 함수

    def find_ins_idx(r, v):

        # 이미 정렬된 리스트 r의 자료를 앞에서부터 차례로 확인하여

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

            # v 값보다 i번 위치에 있는 자료 값이 크면

            # v가 그 값 바로 앞에 놓여야 정렬 순서가 유지됨

            if v < r[i]:

                return i

        # 적절한 위치를 못 찾았을 때는

        # v가 r의 모든 자료보다 크다는 뜻이므로 맨 뒤에 삽입

        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))

     

    신간 소식 구독하기
    뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.