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에서만 쓸 수 있다.

코드를 참조해보자.

#include <stdio.h>

#define max 100

...main 생략

다만 배열을 선언하고 그 배열에 데이터 채운 후에

배열을 파라미터로 넣어 함수를 실행한다.

int binary_search(int array[], int low, int high, int key)

{

int mid;

if(low == high)

return low;

mid = low + ((high-low) / 2);

if(key > array[mid])

return binary_search(array, mid+1, high, key);

else

return binary_search(array, low, mid, key);

return mid;

}

void binary_insertion_sort(int array[])

{

int i, j, find_one;

int temp;

for(i=1; i<max; i++)

{

find_one = binary_search(array, 0, i, array[i]);

if(find_one < i)

{

temp = array[i];

for(j=i-1; j>=find_one; j--)

{

array[j+1] = array[j];

}

array[find_one] = temp;

}

}

}

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

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