목차
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
'CS Study > CLRS (자료구조 | 알고리즘)' 카테고리의 다른 글
[CLRS] [2-4] Bubble Sort(버블 정렬) (0) | 2024.09.04 |
---|---|
[CLRS] [2-3] Merge Sort(병합 정렬) (1) | 2024.09.04 |
[CLRS] [2-2] Analyzing algorithms (0) | 2024.09.02 |
[CLRS] [1-2] Algorithms as a technology (3) | 2024.09.01 |
[CLRS] [1-1] Algorithms? (1) | 2024.09.01 |
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
'CS Study > CLRS (자료구조 | 알고리즘)' 카테고리의 다른 글
[CLRS] [2-4] Bubble Sort(버블 정렬) (0) | 2024.09.04 |
---|---|
[CLRS] [2-3] Merge Sort(병합 정렬) (1) | 2024.09.04 |
[CLRS] [2-2] Analyzing algorithms (0) | 2024.09.02 |
[CLRS] [1-2] Algorithms as a technology (3) | 2024.09.01 |
[CLRS] [1-1] Algorithms? (1) | 2024.09.01 |