[CLRS] [2-1] 삽입 정렬(Insertion sort)?

1. Introduction

- 앞서 1-1 에 설명했던 Sorting Problem을 풀기위해 삽입 정렬(Insertion Sort)를 알아보자.

 

2. Insertion Sort

- 적은 수의 요소를 정렬하는 데 효율적인 알고리즘

- 카드를 한손에 들고 정렬하는 방식과 유사

- 각 숫자를 적절한 위치에 삽입하는 방법을 의미함

- 파이썬으로 해당 알고리즘을 구현한 걸 함께 살펴보자.(parameter는 2개 / 배열, 배열길이)

def insertion_sort(A,n):
    for i in range(1,n):
        key = A[i]
        j = i-1
        while j >=0 and A[j] > key:
            A[j+1] = A[j]
            j -=1
        A[j+1] = key
        
--------------------------------------------------
Output

A = [5,2,6,3,1,4]
n = 6

insertion_sort(A,n)
A
[1, 2, 3, 4, 5, 6]

 

 

- for문에서 각 반복마다 A[i]를 A[:i-1]까지 정렬된 Subarray 안에 적합한 위치에 While문을 통해 삽입한다.

- 즉, 왼쪽부터 오른쪽으로 한개씩 한개씩 배열을 정렬해나가는 느낌이다. 

- 해당 그림을 보면 이해하기 편할 듯하다.

 

 

3. Exercises

Q1) [31,41,59,26,41,58]을 Insertion-Sort 하시오.

def insertion_sort(A,n):
    for i in range(1,n):
        key =  A[i]
        j = i-1
        while j>=0 and A[j] > key:
            A[j+1] = A[j]
            j-=1
        A[j+1] = key

A =  [31,41,59,26,41,58]
n =  len(A)

insertion_sort(A,n)
A


-----------------------------------
Output

[26, 31, 41, 41, 58, 59]

 

Q2) Insertion-sort 를 오름차순이 아닌 내림차순으로 정렬하는 코드 작성

def insertion_sort(A,n):
    for i in range(1,n):
        key = A[i]
        j = i-1
        while j>=0 and A[j] < key:# A[j] > key  --> A[j] < key만 수정!
            A[j+1] = A[j]
            j-=1
        A[j+1] = key
        
A = [5,2,6,3,1,4]
n = 6

insertion_sort(A,n)

A


------------------------------------------------
Output

[6, 5, 4, 3, 2, 1]

 

Q3) Searching 알고리즘 작성 (인덱스 출력)

def serching_array(A,x):
    i = 0
    while (i <= len(A)-1) and (x!=A[i]):
        i +=1
    if x == A[i]:
        return i
    else:
        return 'NIL'

A = [6,5,4,3,2,1]
print(serching_array(A,4))

------------------------------------------------

2