__JMY__
MY Devblog
__JMY__
전체 방문자
오늘
어제
  • 분류 전체보기 (52)
    • Dev (52)
      • Algorithm (6)
      • Linux (12)
      • Network (7)
      • Container (2)
      • Python (14)
      • Frontend (2)
      • Etc (9)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • network
  • Sorting
  • hikaricp
  • SCP
  • flexbox
  • Linux
  • tcpdump
  • Python
  • Docker
  • algorithm
  • frontend
  • Ingress
  • flask
  • springboot
  • certificate
  • hash
  • wget
  • Tuple
  • react
  • Kubernetes

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
__JMY__

MY Devblog

Dev/Algorithm

Insertion Sort (삽입정렬)

2020. 12. 23. 21:24

Insertion Sort (삽입정렬)

삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘입니다.

O(n^2)의 시간복잡도를 가지지만 선택정렬, 버블정렬 알고리즘에 비해 빠릅니다.

삽입을 할 때 데이터를 하나씩 밀어야 하기 때문에 배열이 길어질수록 효율이 떨어집니다.

Insertion Sort 정렬과정

초기상태: (5 3 4 2 1 7 6)

(5 3 4 2 1 7 6)

(5 3 4 2 1 7 6)

(3 5 4 2 1 7 6)

(3 4 5 2 1 7 6)

(2 3 4 5 1 7 6)

(1 2 3 4 5 7 6)

(1 2 3 4 5 7 6)

(1 2 3 4 5 6 7)

Insertion Sort 코드 (Python)

def insertion_sort(arr):
    length = len(arr)
    for i in range(length):
        j = i - 1
        key = arr[i]
        while arr[j] > key and j >= 0:
            arr[j+1] = arr[j]
            j = j - 1
        arr[j+1] = key
    return arr
반응형

'Dev > Algorithm' 카테고리의 다른 글

Merge Sort (병합정렬)  (0) 2021.07.15
다익스트라(Dijkstra) 알고리즘  (0) 2021.04.13
Heap Sort (힙정렬)  (0) 2020.12.29
Selection Sort (선택정렬)  (0) 2020.12.22
Bubble Sort (버블정렬)  (0) 2020.12.22
    'Dev/Algorithm' 카테고리의 다른 글
    • 다익스트라(Dijkstra) 알고리즘
    • Heap Sort (힙정렬)
    • Selection Sort (선택정렬)
    • Bubble Sort (버블정렬)
    __JMY__
    __JMY__
    공부내용 정리 블로그

    티스토리툴바