[C언어 자료구조] 선택정렬, 이진탐색 (술자리 게임처럼 간단하게 이해하기)

이진탐색은 리스트에 저장된 내용을 탐색하는 방법 중 하나로 쉽게 설명을 하면 대학교 술자리 게임인 병뚜껑 up/down게임을 생각하면 이해가 쉽다. 맥주병 뚜껑에 쓰여있는 1-50 사이의 숫자를 맞추기 위해서는 25, 12, 6, .. 또는 25, 37, 45, .. 으로 이어가는 것이 가장 합리적이란 것을 알고 있다. ( 술자리에서는 합리성이 사라지지만.. )

1. 리스트의 시작을 left, 끝을 right으로 지정하여 리스트에 탐색할 정수가 남아 있는지를 체크,

   (병뚜껑의 숫자가 50임으로 left 1, right 50)

2. 찾는 값과 중간 값(middle)을 비교하며 같은 경우 반환, 

   (찾는 값과 중간값인 25를 비교하여 정답이면 폭탄주)

3. middle 보다 작은 경우 left와 middle-1 사이의 리스트를 탐색, 

   (25보다 작은 경우에는 left는 그대로 1 right은 24, 중간 값을 12로 하여 1,2를 반복)

   반대로 middle보다 큰 경우 middle+1과 right 사이의 리스트를 탐색

   (25보다 큰 경우에는 left는 26, right은 그대로 50, 중간 값을 37로 하여 1,2를 반복)

하는 과정을 반복한다.

 

따라서 이진탐색을 구현하기 위해서는 반드시 배열에 저장된 데이터가 정렬되어 있어야 한다. 이번 자료구조에서는 선택정렬을 통하여 정렬을 수행하였다. 

 

이진탐색의 장점으로는 순차탐색(가장 앞에서부터 하나씩 비교)에 비하여 비교연산 횟수가 현저히 줄어든다는 점이다. 

이진탐색은 리스트를 1/2씩 줄여가며 비교연산을 진행하기 때문에 logN번 비교를 진행한다.

따라서 이진탐색의 성능은 O(logN) 이다.

 

main 함수에서 이진탐색을 위하여 정렬을 먼저 수행한다.

1. 사용자가 원하는 만큼 난수를 생성하여 배열에 저장하고 list[i] = (int)((rand() % 1000) + 1)

2. sort 함수를 난수를 저장한 리스트와 리스트의 길이를 통해 호출한다. sort(list, n)

 

sort함수는 선택정렬을 수행한다.

선택정렬이란 제자리 정렬 알고리즘 중 하나로 

정렬되지 않은 정수들 중에서 가장 작은 값을 찾아서 정렬된 리스트 다음 자리에 놓는다. 

1. 리스트의 가장 첫번째 인덱스를 min으로 세팅 

2. 리스트의 마지막까지 탐색하며 min보다 작은 값이 있으면 min 변수에 해당 인덱스를 저장하고 계속 진행.

3. 리스트의 첫 번째 데이터와 가장 작은 수의 데이터를 swap한다. 

비교횟수는 매우 많지만 자리 교환이 매우 적게 일어나기 때문에 매우 안정적이며 교환의 횟수가 적은 정렬에 적합하다. 따라서 내림차순 정렬을 오름차순으로 정렬할 때 최적이며, 이미 정렬되어 있는 배열에 데이터를 추가하여 재정렬할 때 최악의 성능을 보인다.

자료가 총 n개일 때 (n-1)..(n-2)...1만큼 비교하게 되어 n(n-2)/2 번 비교를 하게 되고 교환은 n번 추가적으로 수행한다.

따라서  n(n-2)/2+n으로 O(n^2)의 성능을 보인다.  

 

다시 메인함수로 돌아와서 선택정렬이 완료된 후 찾고 싶은 숫자를 입력받는다. 

binsearch 함수는 배열에 찾고자하는 숫자가 있을 때 해당 인덱스를 반환하며, 없을 경우 –1을 반환한다. 

위치 값이 반환된 경우 이는 배열의 인덱스이기 때문에 실제로 사용자에게 출력되는 위치는 result+1이다.

 

 

binsearch함수는 정렬된 리스트, 찾고 싶은 숫자(main 함수의 search), 배열의 시작과 끝(0, n-1)을 매개변수로 받는다.

1. 리스트의 범위가 left, right으로 설정된다.

2. 연산은 right이 left와 같거나 클 때 동안 반복한다. 

3. 현재 리스트(=검색범위)의 중간 인덱스를 계산한다. middle=(left+right)/2

4. compare함수를 통하여 list[middle]과 찾고자하는 값(searchnum)을 비교한다. 

   ⓵list[middle]보다 searchnum이 큰 경우, left에 middle+1을 저장하여 탐색범위를 줄인다.

   ⓶list[middle]과 searchnum이 같은 경우, 찾고자 하는 값의 인덱스인 middle을 main함수로 반환한다.

   ⓷searchnum이 작은 경우, right에 middle-1을 저장하여 탐색범위를 줄인다.

5. 반복

6.left와 right의 위치가 바뀔 때까지 searchnum을 발견하지 못하면 반복문에서 빠져나온다. 그리고 –1을 메인함수로 반환한다.