[파이썬] 백준 24051 알고리즘 수업 삽입 정렬 1

백준 24051 알고리즘 수업 - 삽입정렬 1

백준 24051 삽입정렬

☞ 백준 사이트 : https://www.acmicpc.net/problem/24051

삽입정렬 이란

• 주어진 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,
  자신의 위치를 찾아 삽입하는 정렬이다.
• 선택정렬이나 버블정렬과 같은 알고리즘에 비해 빠르며, 안정적인 정렬 알고리즘이다.

삽입정렬 풀이 순서

[4, 5, 1, 3, 2]을 오름차순 정렬로 변경하는 경우

• [4, 5, 1, 3, 2]
  • 2번 index 1을 0번 index부터 비교.
  • 4 보다 작아 0번 index에 insert
  • 나머지 shift
• [1, 4, 5, 3, 2]
  • 3번 index 3과 4 비교 insert
  • 나머지 shift
• [1, 3, 4, 5, 2]
  • 4번 index 2와 3 비교 insert
  • 나머지 shift
• [1, 2, 3, 4, 5]
  • 정렬완료

풀이

1. 배열의 1번 index 부터 마지막까지 반복한다.
2. 값을 맨 앞까지 이동하면서 정렬대상인지 판단되면 이동해야 할 index 저장, 나머지 shift
3. 이동해야할 index가 있다면, 그 자리에 대상 값 저장(insert)

소스 내 값 변경 history

[4, 5, 1, 3, 2]

• 소스 내 while 문 (newItem = 1)
  • [4, 5, 5, 3, 2]
  • [4, 4, 5, 3, 2]
• 소스 내 if 문
  • [1, 4, 5, 3, 2]
• 소스 내 while 문 (newItem = 3)
  • [1, 4, 5, 5, 2]
  • [1, 4, 4, 5, 2]
• 소스내 if 문
  • [1, 3, 4, 5, 2]
• 소스내 while 문 (newItem = 2)
  • [1, 3, 4, 5, 5]
  • [1, 3, 4, 4, 5]
  • [1, 3, 3, 4, 5]
• 소스내 if 문
  • [1, 2, 3, 4, 5]

import sys
#배열 A의 크기 N, 저장횟수 K 입력받는다.
N, K = list(map(int, sys.stdin.readline().rsplit()))
#배열 A의 원소들을 입력받는다.
A = list(map(int, sys.stdin.readline().rsplit()))

def insertion_sort(lst, K):
    cnt = 0
    #1.배열의 1번 index 부터 마지막까지 반복한다.
    for i in range(1, len(lst)):
        loc = i - 1
        newItem = lst[i]

        # 이 지점에서 A[1..i-1]은 이미 정렬되어 있는 상태
        #2.값을 맨 앞까지 이동하면서 정렬대상인지 판단되면 이동해야할 index 저장, 나머지 shift
        while (0 <= loc and newItem < lst[loc]):
            cnt += 1
            lst[loc+1] = lst[loc]
            loc -= 1
            if cnt == K:
                return(print(lst[loc+1]))
        #3.이동해야할 index가 있다면, 그 자리에 대상 값 저장(insert)
        if (loc + 1 != i):
            cnt += 1
            lst[loc + 1] = newItem            
            if cnt == K:
                return(print(lst[loc+1]))
    return(print(-1))
insertion_sort(A,K)
"""
5 7
4 5 1 3 2
5
"""