반드시 알아야하는 알고리즘 top 8 - 5. 삽입 정렬

반드시 알아야 하는 알고리즘 top 8

• 재귀 알고리즘 

• 이진 탐색 

• 순차 탐색

• 버블 정렬

• 삽입 정렬

• 탐욕 알고리즘

• 최단거리 알고리즘

• 몬테 카를로 알고리즘

삽입 정렬 

• 삽입 정렬이란 앞의 숫자들을 정렬된 상태라고 가정한 뒤 정렬되지 않은 숫자들을 하나씩 빼서 정렬되어 있는 숫자 사이의 올바른 위치에 삽입하는 정렬 방법을 의미 합니다. 다음 영상을 통해 자세히 살펴보겠습니다. 2:36 부터 삽입정렬 관련 시작입니다.

삽입 정렬 코드 01 : Python 

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

for i in range(1,len(a)):

    for j in range(i):

        if a[i] < a[j]:

            a.insert(j,a.pop(i))

            

• 삽입정렬을 구현한 코드 입니다. 

i = 1 j = 0 a = [1, 4, 5, 2, 3]

i = 2 j = 0 a = [1, 4, 5, 2, 3]

i = 2 j = 1 a = [1, 4, 5, 2, 3]

i = 3 j = 0 a = [1, 4, 5, 2, 3]

i = 3 j = 1 a = [1, 2, 4, 5, 3]

i = 3 j = 2 a = [1, 2, 4, 5, 3]

i = 4 j = 0 a = [1, 2, 4, 5, 3]

i = 4 j = 1 a = [1, 2, 4, 5, 3]

i = 4 j = 2 a = [1, 2, 3, 4, 5]

i = 4 j = 3 a = [1, 2, 3, 4, 5]

• 이 과정을 따라 정렬이 이루어지는 것을 알 수 있습니다. 동영상과 같은 과정으로 진행됩니다.

삽입 정렬 코드 02 : Python

• 이번엔 삽입정렬 코드를 재귀 알고리즘을 사용해 구현한 코드 입니다. 

def basic(i=0,j=0):

    global a

    if j == len(a):

        return

    else:

        if i == j:

            basic(0,j+1)

        else:

            if a[i] > a[j]:

                a.insert(i,a.pop(j))

            basic(i+1,j)

• 이 코드 또한 위의 코드를 재귀적 방법으로 변경해 놓은 것에 불과 하니 편한 방법을 사용해 코드를 작성하면 될 것 같습니다.

• 진행과정은 다음과 같습니다.

i = 0, j = 1, a = [1, 4, 5, 2, 3]

i = 0, j = 2, a = [1, 4, 5, 2, 3]

i = 1, j = 2, a = [1, 4, 5, 2, 3]

i = 0, j = 3, a = [1, 4, 5, 2, 3]

i = 1, j = 3, a = [1, 2, 4, 5, 3]

i = 2, j = 3, a = [1, 2, 4, 5, 3]

i = 0, j = 4, a = [1, 2, 4, 5, 3]

i = 1, j = 4, a = [1, 2, 4, 5, 3]

i = 2, j = 4, a = [1, 2, 3, 4, 5]

i = 3, j = 4, a = [1, 2, 3, 4, 5]

---

부족한 블로그에 방문해 주셔서 감사합니다.

잘못된 부분이나 질문이 있으시면 

댓글로 말씀해주세요.

금방 확인하고 피드백 드리겠습니다.

좋은 하루 되세요. ^^