What I Learned
  • Introduction
  • Introduction
  • Javascript
    • 클로저 (closure)
    • 프로토타입 (Prototype)
    • 정규표현식 (RegExp)
    • 날짜 (Date)
    • jQuery 분석
    • 스코프 (this)
    • 성능 최적화 (Optimization)
  • Style
    • CSS
      • Prevent user select
      • Aspect Ratio
      • Sticky Footer
    • SASS
      • for loop
      • mixin example
      • Media Query
  • Web
    • 웹의 동작 과정
    • Cross Browser
    • Document Reflows
    • Open Graph
    • 이미지 압축 (Image optimization)
    • SPA, SSR 비교
  • Algorithm and Data Structure
    • 자료구조 (Data Structure)
      • 큐 (Queue)
      • 스택 (Stack)
      • 링크드 리스트 (Linked List)
    • 기초 이론
      • 복잡도 분석
    • 수학 (Math)
      • factorial (계승)
      • 피보나치 수 (Fibonacci)
    • 정렬 (Sorting)
      • 버블 정렬 (Bubble Sort)
      • 선택 정렬 (Selection Sort)
      • 삽입 정렬 (Insertion Sort)
      • 합병 정렬 (Merge Sort)
      • 퀵 정렬 (Quick Sort)
    • 탐색 (Search)
      • 순차 탐색 (linear search)
      • 이진 탐색 (Banary search)
    • 문제 풀이
      • 땅따먹기
      • 가장 큰 원소의 합 구하기
      • JS with HTML
  • Software Engineering
    • OOP
    • Development Process
    • TDD / BDD
  • Interview
    • HTML
    • CSS
    • Javascript
    • Other
    • General Questions
  • DevOps
    • gulp
  • PHP
    • Basic
Powered by GitBook
On this page
  1. Algorithm and Data Structure
  2. 정렬 (Sorting)

삽입 정렬 (Insertion Sort)

Previous선택 정렬 (Selection Sort)Next합병 정렬 (Merge Sort)

Last updated 6 years ago

  • 주어진 데이터를 하나씩 뽑아, 나열된 데이터들이 항상 정렬된 형태를 가지도록, 뽑은 데이터를 바른 위치에 삽입해서 나열하는 방식

  • 시간복잡도 O(n²)

function insertionSort (array) {
  let temp, j;
  for (let i=1; i<array.length; i++) {
    temp = array[i]; // 새로운 숫자를 선택함
    for (j = i-1; j >= 0 && temp < array[j]; j--) { 
      // 선택한 숫자를 이미 정렬된 숫자들과 비교하며 넣을 위치를 찾는 과정
      // 선택한 숫자가 정렬된 숫자보다 작으면 한 칸씩 뒤로 밀어낸다
      array[j + 1] = array[j];
    }
    array[j + 1] = temp; // 마지막 빈 칸에 선택한 숫자를 넣어준다.
  }
  return array;
};
insertionSort([5, 6, 1, 2, 4, 3]); // [1, 2, 3, 4, 5, 6]