BLOG. 2won0

Binary Search 를 구현해 보겠다.

먼저 Binary Search란 

위의 그림처럼 배열의 중간값을 기준으로

찾고자 하는 값이 중간값보다 크면 기준의 오른쪽 배열을 선택, 찾고자 하는 값이 중간값보다 작으면 기준의 왼쪽 배열을 

선택해가며 원하는 숫자를 찾아내는 방법이다.

Binary Search에 대한 포스팅은

1. 사이즈가 10,000인 배열을 생성하고 배열에 겹치지 않는 랜덤한 숫자를 저장한 뒤 파일에 저장한다.

2. Binary Search를 Iterative한 방식으로 구현해 본다.

3. Binary Search를 Recursive한 방식으로 구현해 본 뒤 Iterative한 방식과 비교해 본다.

총 3개의 글로 나누어 포스팅 해 보겠다.

먼저 중복이 없이 오름차순으로 정렬된 10000개의 정수를 생성하여 data.txt 파일에 저장하였다.

처음에 랜덤하게 생성된 값을 기준으로 매번 이전값과 비교하여 이전값보다 클 경우에만 저장되는 방식으로 구현을 하려고

하였으나 이럴경우 처음 생성되는 기준값이 커질 수도 있고, 이전 값과 다음값의 차이가 엄청나게 클 수도 있는 문제점이 있었다.

따라서 간단하게 제일 첫번째 값은 무조건 1로 저장하고 이후 값부터는 이전값보다 최소 1에서 최대 3까지의 범위 내에서

플러스 되는 방식으로 10,000개의 정수를 생성해 보았다.

정수가 모두 생성된 뒤 data.txt 파일을 열어보면 10,000개의 정수가 오름차순으로 제대로 생성되어 있는 모습을 확인할 수 

있었다.

Insertion Sorting에 이어 이번에는 Selection Sorting의 시간을 측정해 보았다.

이번에도 마찬가지로 1,000,000개의 랜덤한 숫자를 생성한 뒤 Selection Sorting을 이용하여 정렬하고 시간을 측정해 보았다.

측정된 시간은 1772.119초, 약 29분 53초가 소요되었다.

역시 정렬되기 전 숫자들은 before.txt 파일에, 정렬된 후의 숫자들은 after.txt에 저장하고 제대로 정렬이 되었는지 또한 확인해 보았다.

제대로 정렬된 모습을 볼 수 있었다.

같은 1,000,000개의 숫자를 정렬 할 때 Insertion Sorting과 비교해 본다면 정렬해야 할 숫자의 양이 많아질 때는 

Selection Sorting이 비교적 느린 속도를 보여주었다.

그래프에서 보는 것 처럼 일정 범위내에서는 비슷한 속도를 보이지만 연산량이 많아질수록 Selection Sorting의 속도가

더 오래 걸리는 모습을 확인할 수 있었다.

소스코드

Sorting을 진행한 총 시간은 1059.978 sec 즉, 17분 6663초 정도가 소요 되었다.

before.txt파일과 after.txt 파일을 비교해 보면 정렬 또한 제대로 된 것을 확인 할 수 있다.

데이터의 양에 따른 Sorting 시간을 측정해 보았는데

일정 양을 넘어가면 Sorting 시간이 기하급수적으로 증가하는 모습을 볼 수 있었다.

다음 포스팅에는 Selection Sorting을 이용한 정렬 시간과 이에대한 결과로 Insertion Sorting과의 비교를 해 보도록 하겠다.

소스 코드

보통의 Swap 함수를 구현한다고 하면 두개의 변수를 포인터로 받아와 함수 내에서 temp 변수를 사용하는게 일반적이다.

void swap(int *pa, int *pb) {
    int temp;
    temp = *pa;
    *pa = *pb;
    *pb = temp;
}

하지만 temp변수를 사용하지 않고 Swap 함수를 구현할 수도 있다.

 

void swap(int *pa, int *pb) {	// without temp
    *pa = *pa + *pb; // a의 값에 b를 더한다.
    *pb = *pa - *pb; // b에는 a에서 b를 뺀 값을 저장한다. (즉, 처음 a의 값이 된다.)
    *pa = *pa - *pb; // a에는 처음 a와 b가 더해진 값에서 b를 뺀다 (b는 바뀐 a값이 저장되어 있다.)
    // 결국 a에는 처음 b의 값이 저장된것처럼 된다. 
}

 

  

 다음과 같이 구현하면 temp 변수를 사용하지 않은채로 Swap 함수를 구현할 수 있다.

 

이 두가지 방법에 차이가 있을지에 대해 측정해 보기 위해 Microsec 단위로 연산 시간을 비교해 보았다.

 

먼저 temp 변수를 사용하였을 때에는  

 

 

보통 0~1 microsec 의 시간을 보였고,

 

temp변수를 사용하지 않았을 때에는

 

 

비슷한 시간을 보였다.

 

좀더 작은 단위로 측정해 본다면 다른 결과를 보일 수 도 있겠지만 보통 1 microsec 내에서 연산되는 결과를 확인할 수 있었다.

 

 

결론적으로 temp변수를 사용할때와 사용하지 않을 때의 차이는 시간적인 면에서는 별 차이를 나타내지 않고, 

 

다만 temp 변수로 인한 integer 메모리 하나의 차이정도가 생기지 않을 까 라고 생각해 보았다.