알고리즘 ) 1) 정렬된 데이터 집합의 중앙값을 선택한다. 2) 중앙값과 탐색키의 값을 비교하고, 아래와 같이 경우에 따른 계산방식을 따른다.

목차

없음

본문내용

[문제 1]
1) 정렬된 데이터 집합의 중앙값을 선택한다.
중앙값= (최소값+최대값)/2 => (30+70)=50
2) 중앙값과 탐색키의 값을 비교하고, 아래와 같이 경우에 따른 계산방식을 따른다.
[ 탐색키 < 중앙값 ] => 중앙값의 왼편에서 중앙값을 선택한다.
[ 탐색키 > 중앙값 ] => 중앙값의 오른편에서 중앙값을 선택한다.
- 탐색키(65) > 중앙값(50) => 중앙값의 오른편에서 탐색{55,60,65,70}
중앙값 = (55+70)/2 = 62.5
- 탐색키(65) > 중앙값(62.5) => 중앙값의 오른편에서 탐색{65,70}
중앙값 = (65+70)/2 = 67.5
- 탐색키(65) > 중앙값(67.5) => 중앙값의 왼편에서 탐색{65}
탐색키와 65로 일치하므로 마친다.

[문제 2]
1) 기준값(Pivot)을 정한다.
2) 조건에 따라 기준값과 비교하여 숫자를 이동함으로써 수행된다.(L와 H의 이동은 별개로 움직인다.)
- 조건 : L < 기준값 < H
3) 둘 다 조건에 맞지 않는 지점에 도착하면 L과 H를 교환한다.
4) 이 과정은 L과 H가 역전될 때까지 3)을 반복한다.
5) L과 H가 역전되면 H와 Pivot을 교환한다.
5) 4)까지 과정을 거쳤을 때 완전히 정렬이 되지 않는다면 될 때까지 과정을 반복한다.

참고 자료

없음