Find Mean Value

소개

Find Mean Value c code 포함

목차

1. 완성 code
2. 결과화면
3. 프로그래밍 실행 환경
4. 토의

본문내용

이 과정을 left와 right가 만날 때까지 반복하는데 이때 left 는 기준값보다 큰 값을 가리킨다. left와 기준값을 교환하여 left가 가리키는 값을 배열 끝으로 보내면 기준값의 왼쪽에는 이 값보다 작은 값만 있고 오른쪽에는 더 큰 값만 있을 것이다. 기준값이 있는 위치의 왼쪽 구간과 오른쪽 구간을 똑같은 방법으로 정렬하되 구간 크기가 1이 될 때까지 이 과정을 반복하면 전체 배열이 정렬된다. 그림으로 위 예제의 동작을 관찰해 보자.
이 예에서 기준값은 배열 제일 끝에 있는 15으로 선정되었다. left는 배열 선두에서부터 뒤쪽으로 이동하면서 15보다 더 큰 값을 찾고 right는 배열 끝에서부터 앞쪽으로 이동하면서 n보다 더 작은 값을 찾는다. for 문 안의 while루프가 이 검색을 수행하는데 이 예에서는 최초 left에 18이 검색되고 right에 1가 검색된다. 검색된 두 값을 교환하여 작은 값은 가급적 배열의 왼쪽으로 보내고 큰 값은 가급적 배열의 오른쪽으로 보낸다. 다음 루프에서 left와 right는 계속 중앙으로 이동하여 각각 30와 13을 찾아 두 값을 교환한다.
이 과정을 left가 right보다 더 작을 동안에 반복하는데 세 번째 단계에서 right가 90, left가 10을 가리킬 때 두 포인터는 이동을 중지한다. 그리고 기준값 15을 left 위치의 값(기준값보다는 더 크다)과 교환하면 기준값을 경계로 하여 왼쪽에는 15보다 더 작은 값만 남고 오른쪽에는 더 큰 값만 남게 된다. 이 상태를 만들면 왼쪽, 오른쪽 구간은 아직 정렬이 덜 되었지만 좌우 구간과 기준값 세 요소만 보면 정렬이 완료되었다.

남은 일은 좌우 구간을 개별적으로 다시 정렬하는 것인데 이 문제는 최초의 정렬 문제와 동일하므로 재귀 호출로 문제를 해결한다. 좌우 구간의 시작점과 길이를 적절히 계산해서 QuickSort 함수를 다시 호출한다. QuickSort 함수는 주어진 크기의 배열을 정렬하되 구간 길이가 1밖에 안될 때는 정렬이 이미 완료된 것으로 보고 곧바로 리턴한다. 그렇지 않다면 구간의 끝 값을 기준으로 다시 정렬하고 이 단계에서 생긴 또 다른 작은 구간들을 정렬하기 위해 재귀 호출이 발생할 것이다.

참고자료

· 없음