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

2024. 9. 1. 19:18· CS Study/CLRS (자료구조 | 알고리즘)
목차
  1. 1. Introduction
  2. 2. Insertion Sort
  3. 3. Exercises
  4. Q1) [31,41,59,26,41,58]을 Insertion-Sort 하시오.
  5. Q2) Insertion-sort 를 오름차순이 아닌 내림차순으로 정렬하는 코드 작성
  6. Q3) Searching 알고리즘 작성 (인덱스 출력)

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. 1. Introduction
  2. 2. Insertion Sort
  3. 3. Exercises
  4. Q1) [31,41,59,26,41,58]을 Insertion-Sort 하시오.
  5. Q2) Insertion-sort 를 오름차순이 아닌 내림차순으로 정렬하는 코드 작성
  6. Q3) Searching 알고리즘 작성 (인덱스 출력)
'CS Study/CLRS (자료구조 | 알고리즘)' 카테고리의 다른 글
  • [CLRS] [2-3] Merge Sort(병합 정렬)
  • [CLRS] [2-2] Analyzing algorithms
  • [CLRS] [1-2] Algorithms as a technology
  • [CLRS] [1-1] Algorithms?
23학번이수현
23학번이수현
밑바닥부터 시작하는 AI보안전문가23학번이수현 님의 블로그입니다.
23학번이수현
밑바닥부터 시작하는 AI보안전문가
23학번이수현
전체
오늘
어제
  • 분류 전체보기 (240)
    • Statistic Study (47)
      • Mathematical Statistics(수리통.. (47)
    • Mathematics Study (15)
      • Linear Algebra (선형대수학) (15)
    • CS Study (71)
      • CLRS (자료구조 | 알고리즘) (49)
      • Database(DB) (11)
      • C++ (11)
      • 객체지향 프로그래밍(OOP) (0)
    • DS Study (56)
      • CS 229(Machine Learning) (19)
      • CS 224n(NLP) (5)
      • Web Scraping (7)
      • R4DS(R언어) (20)
      • 밑바닥부터 시작하는 딥러닝 1 (5)
    • 코딩테스트 (5)
      • 백준-Python (5)
    • Paper Review(논문 리뷰) (43)
      • Deep Learning (16)
      • TCGA 관련 논문 (4)
      • Computer Vision (18)
      • NLP (5)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • web scraping
  • 데이터분석
  • C++
  • Data Structure
  • Introduction to Algorithms
  • NLP
  • R4DS
  • 백준
  • AI
  • clrs
  • 선형대수학
  • 논문 리뷰
  • db
  • 자료구조
  • 정렬
  • cs 224n
  • R언어
  • Machine Learning
  • Algorithms
  • LSTM
  • Linear Algebra
  • cs229
  • 파이썬
  • 수리통계학
  • 딥러닝
  • introduction to algoritmhs
  • 알고리즘
  • 시간복잡도
  • deep learning
  • graph

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
23학번이수현
[CLRS] [2-1] 삽입 정렬(Insertion sort)?
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.