[ Do it! 알고리즘 코딩 테스트 ] 6일차 _ 04. 삽입 정렬

삽입 정렬(Insertion Sort)이란?

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입해 정렬하는 방식 

시간 복잡도는 O(n^2)로 느린 편

 

매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입

 

삽입 정렬 수행과정

🔹현재 Index에 있는 데이터 값을 선택

🔹현재 선택한 데이터가 정렬된 데이터 범위에 삽입된 위치를 탐색

🔹삽입 위치부터 index에 있는 위치까지 shift 연산 수행

🔹삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산 수행

🔹전체 데이터의 크기만큼 index가 커질 때까지 수행 ( 선택할 데이터가 없을 때까지 반복 수행 )

 

탐색하는 부분에서 이진 탐색과 같은 탐색 알고리즘을 통해 시간 복잡도를 줄일 수 있다.

 

관련 문제

[ 백준 ] 11399번 그리디 - ATM