[자료구조] 삽입 정렬

 

자료구조의 기본 알고리즘

 

" 삽입정렬 "

 

이번에도 구현이 아주 쉽지만, 시간복잡도가 미친듯이 높은 한마디로 성능이 좋지않은 정렬 방법을 소개하려해요.

 

 

삽입정렬이란, 원본 데이터에서 값을 하나씩 꺼내서 새로운 리스트의 가장 마지막 값 또는 처음 값부터 끝까지 전체 데이터를 비교해서

해당 데이터에 맞는 자리에 삽입을 해주는 정렬이에요.

 

그래서 시간복잡도는 O(n²)

 

 

 

위 글 요약으로만 이해되셨을 수도 있지만, 이해가 잘 되지 않는 분을 위해 그림과 함께 다시 한번 더 설명해보도록 하죠.

 

 

그림처럼 정렬되지 않은 데이터가 [ 3 , 2 , 1 , 4 ] 일 때, 데이터를 하나씩 꺼내와서, 새로운 리스트에 들어가있는 모든 데이터와 비교를 하여 정렬하는 알고리즘입니다.

 

구현은 매우 쉽지만 실무에서는 거의 사용되지 않는다고 보시면 되겠죠.

아, 물론 예외는 있습니다 ㅎㅎㅎ 

 

 

그럼 구현한 샘플 소스를 확인해볼게요.

 

 

function InsertSort(data){     let rstData = [];      for(let i=0; i<data.length; i++){         rstData.push(data[i]);         if(rstData.length == 1){ continue; }                  let j = i;         while(j-- >= 0){             if(rstData[j-1] > rstData[j]){                 let temp = rstData[j];                 rstData[j] = rstData[j-1];                 rstData[j-1] = temp;             }         }     }      return rstData; }  var data = [3,2,1,4]; console.log("--Original Data :> " + data); console.log("InsertSort Data :> " + InsertSort(data));

 

InsertSortable.zip

다운로드

 

샘플 소스 파일이구요.

 

여기까지 간단한 삽입정렬 마칠게요 !