본문 바로가기

코드^학습/메모한 지식

Binary Insertion Sort

요즘 알고리즘을 재이수.....(크흑) 하면서


코딩감각을 다시 살려가고 있는데... 그전에는 몰랐던 Binary Insertion Sort에 대해 적어볼까 한다.


기존에 Insertion Sort는 잘 알려져있고 전역 후 복학한 해 배운 기억이 있는 Sorting 방법이다. 그러나 잘 알려진대로 Insertion Sort는 순차적으로 비교하면서 정렬하는 방법이다.

하나하나 비교하여 Sort한 영역을 점차 확대해 나가는 방법이다.


그런데 이 하나하나 비교하는 것은 선택한 key가 어디에 위치할지 위치를 찾는 것인데, 이 방법을 순차비교가 아니라 Binary Search를 이용할 수 있다는 것이다!

(몰랐다...)


코드 구조는 Insertion Sort를 수행할 때 위치를 찾는 부분에서 Binary Search를 적용하면 된다.(의...의외로 간단해...?)


Binary Search는 주어진 DataSet에서 반씩 토막내가면서 middle값을 정하고 middle값이 찾는값일때까지 범위를 좁혀나가는 방식이다. 물론 당연히 Sorted 된 DataSet에서만 쓸 수 있다.


코드를 참조해보자.


이렇게도 할 수 있구나...

굳어가는 머리를 깨우친거 같다 0_0