더북(TheBook)

     

    3일반적인 삽입 정렬 알고리즘

     

    이번에는 입력 리스트 안에서 직접 위치를 바꿔 정렬하는 삽입 정렬 프로그램을 살펴보겠습니다. 구체적인 동작 과정은 연습 문제 9-1 풀이에서 설명하겠습니다.

     

    icon_cakewalk 프로그램 9-2

     

    일반적인 삽입 정렬 알고리즘

     

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

    # 삽입 정렬

    # 입력: 리스트 a

    # 출력: 없음(입력으로 주어진 a가 정렬됨)

     

    def ins_sort(a):

        n = len(a)

        for i in range(1, n): # 1부터 n -1까지

            key = a[i] # i번 위치에 있는 값을 key에 저장

            # j를 i 바로 왼쪽 위치로 저장

            j = i - 1

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

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

                a[j + 1] = a[j] # 삽입할 공간이 생기도록 값을 오른쪽으로 한 칸 이동

                j -= 1

            a[j + 1] = key # 찾은 삽입 위치에 key를 저장

     

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

    ins_sort(d)

    print(d)a

     

    icon_result 실행 결과

     

    [1, 2, 3, 4, 5]

     

     

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