jiho_bae
Go devlog
jiho_bae
전체 방문자
오늘
어제
  • 분류 전체보기 (158)
    • JavaScript (38)
      • theory (34)
      • vanilla (4)
    • HTML & CSS (2)
    • Browser (3)
    • CS (6)
      • linux (1)
      • shell (2)
      • compiler (2)
    • DS & Algorithm (87)
      • theory (5)
      • basic (7)
      • programmers (30)
      • baekjoon (45)
    • Design Pattern (2)
    • Error (4)
    • Git & Github (4)
    • Tools (1)
    • 부트캠프 (4)
    • Small Tips (2)
    • Java (3)
    • test (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 계수정렬 자바스크립트
  • 백준 자바스크립트 입력 템플릿
  • 대충만든자판 javascript
  • 백준 17406 nodeJS
  • 프로그래머스 숫자카드나누기 javascript
  • 자바스크립트 모듈 시스템
  • 자바스크립트 커링
  • safari Date format NaN
  • 깃 이전 커밋에서 새 브랜치 만들기
  • 덧칠하기 javascript
  • 자바스크립트 채팅방 스크롤
  • 13460 javascript nodejs
  • 카카오 코딩테스트 양궁대회 nodeJS
  • safari invalid date error
  • javascript use strict
  • 자바스크립트 sort는 왜 그모양일까
  • 자바스크립트 비동기 마이크로 태스크 큐와 렌더링 과정
  • 25632 소수 부르기 게임
  • 자바스크립트 이벤트 위임
  • 리액트 프로젝트 디버깅하기
  • 1753 최단경로 javascript
  • 외벽 점검 javascript
  • 퀵정렬 자바스크립트
  • 자바스크립트 배열의 특수함
  • 병합정렬 자바스크립트
  • fetch 취소하기
  • 억억단을 외우자 javascript
  • 가사 검색 자바스크립트
  • JavaScript
  • 리코쳇 로봇 javascript

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
jiho_bae

Go devlog

삽입 정렬(Insertion Sort) 이란
DS & Algorithm/theory

삽입 정렬(Insertion Sort) 이란

2022. 2. 4. 18:40

삽입 정렬

처리되지 않은 데이터를 적절한 위치에 삽입하는 알고리즘이다.

 

삽입 정렬에서는 배열 첫번째 원소는 정렬되었다고 판단하며, 두번째 원소부터 어떤 위치로 들어가야 할 지 판단한다.
즉, 두번째 원소부터 시작해서 앞에 있는 원소들과 비교하며 삽입할 위치에 데이터를 삽입하며 정렬하는 알고리즘이다.

 

삽입 정렬의 과정은 다음과 같다.

 

1. N번째 인덱스의 값을 저장한다.
2. 1 ~ N-1번째 인덱스에 있는 원소들과 비교하며 적절한 위치를 찾아 삽입한다.
3. 1번 과정과 2번 과정을 반복한다.

 

gif를 통해 이해해보자.

출처 : https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

 

삽입 정렬을 JS 코드를 통해 구현하였다.

  const arr = [5, 6, 3, 1, 8, 7, 2, 4];

  function insertionSort(arr){
      const len = arr.length;

      for(let i=1; i<len; i++){
          let idx = i-1;
          const tmp = arr[i];
          while(tmp < arr[idx] && idx >= 0){
              arr[idx + 1] = arr[idx];
              idx--;
          }
          arr[idx + 1] = tmp;
      };

      return arr;
  }

  console.log(insertionSort(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]

두번째 인덱스(i = 1)부터 탐색을 시작한다.

 

tmp 변수에 삽입할 인덱스의 값을 저장하고, idx 변수를 이용해 i의 바로 왼쪽부터 tmp 변수가 들어갈 위치를 탐색한다.

 

while문을 통해 tmp 변수보다 큰 값을 모두 우측으로 한칸씩 옮긴다.(= 인덱스를 1씩 증가시킨 위치에 값을 이동시킨다.)

tmp < arr[idx] && arr[idx-1] >= tmp 인 위치의 idx를 구한다.
(만약 tmp 변수가 가장 작은 변수라면 idx = 0에 있는 값을 idx = 1로 옮겨준다.)

 

그리고 idx + 1 위치에 tmp 변수를 삽입한다.
(현재 idx 위치는 tmp보다 작은 값이 있거나, 배열의 맨 앞의 앞인 -1을 의미한다.)
(while문에 의해 idx + 1의 위치에 있는 값과 idx + 2에 있는 값이 같으므로, idx + 1에 tmp 변수를 넣어주면 된다.)

 

즉 선택한 인덱스로부터 왼쪽에 있는 원소들과 대소를 비교하는데, 자신보다 작은 값을 가진 인덱스를 찾는다고 생각하면 되겠다.


삽입 정렬의 시간복잡도

평균 시간복잡도는 비교, 교환을 통해 O(N^2)를 가진다.
선택 정렬같이 이중 반복문을 수행하기 때문이다.

최악의 경우는 역으로 정렬된 경우이며 선택 정렬과 같이 n(n-1)/2 => O(n^2)를 보인다.
최선의 경우는 모두 정렬된 경우이며, 비교 O(N), 교환 O(1)로 O(N)의 복잡도를 가진다.

이미 정렬된 상태에서 삽입 정렬을 수행하면..?

  • 기준에서 왼쪽 원소들과 대소를 비교하므로, 모든 원소들은 1번의 비교만으로 정렬이 수행된다.
  • 그러므로 어느 위치에 삽입할지 검색하는 시간이 O(상수)시간으로 대체된다.
  • 정렬을 위해 각 원소를 순회해야 하므로, O(N)의 복잡도를 가진다. 즉, O(N*k) = O(N)의 복잡도를 가진다.

삽입 정렬의 공간복잡도

선택 정렬과 같이 배열 내에서의 swap을 통해 구현하므로, O(N)의 복잡도이다.


장점

선택 정렬에 비해 구현 난이도는 높으나 더 효율적이다.
대부분이 정렬된 배열에서 특히 좋다.
주어진 배열 안에서 인덱스끼리 Swap을 통해 정렬이 수행되므로 공간 효율적이다. (= 제자리 정렬)
안정 정렬이다(=중복 값이 입력 순서와 동일하게 정렬된다.)

 

안정 정렬을 간단한 예시를 통해 이해해보자.

 

 2 3 1 5 4 5 를 삽입 정렬을 통해 정렬하면, 1 2 3 4 5 5 순서로 중복 값 순서를 유지한다.


단점

평균, 최악 시간복잡도가 O(N^2)이다.
배열 길이가 길어질수록 효율이 떨어진다.

저작자표시 (새창열림)

'DS & Algorithm > theory' 카테고리의 다른 글

병합 정렬(Merge Sort) 이란  (0) 2022.02.08
계수 정렬(Counting Sort) 이란  (0) 2022.02.07
퀵 정렬(Quick Sort) 이란  (0) 2022.02.07
선택정렬(Selection Sort) 이란  (0) 2022.02.04
    'DS & Algorithm/theory' 카테고리의 다른 글
    • 병합 정렬(Merge Sort) 이란
    • 계수 정렬(Counting Sort) 이란
    • 퀵 정렬(Quick Sort) 이란
    • 선택정렬(Selection Sort) 이란
    jiho_bae
    jiho_bae
    하루에 한 걸음씩

    티스토리툴바