Page 64 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

을 {70, 68, 91, 32, 11, 57, 22}로 바꾸어 보겠습니다.

다음은 순서를 뒤바꾸는 과정을 나타낸 그림입니다. 먼저 그림 a 처럼 맨 앞의 요소 a[0]과 맨
뒤의 요소 a[6]의 값을 교환합니다. 이어서 그림 b 와 그림 c 처럼 각각 하나씩 안쪽의 요솟값
을 교환합니다.

１ ２ ３ ４ ５ 
a 22 57 11 32 91 68 70

교환
０  ２ ３ ４  ６
b 70 57 11 32 91 68 22 교환 횟수 = 요소 개수/2

교환
０ １  ３  ５ ６
c 70 68 11 32 91 57 22
교환

０ １ ２ ３ ４ ５ ６
d 70 68 91 32 11 57 22
[그림 2-9] 배열 요소를 역순으로 정렬

교환 횟수는 ‘요소 개수/2’이며, 이 나눗셈에서 나머지는 버립니다. 위 예제에서 볼 수 있듯이

요소 개수가 홀수인 경우 가운데 요소는 교환할 필요가 없기 때문입니다.
‘정수 / 정수’ 연산은 나머지를 버리고 정수부만 얻을 수 있으므로 나머지를 버리기에 좋습니다(요소 개수가 7인 경우
교환 횟수는 7/2, 곧 3입니다).

요소 개수가 n인 배열을 처리하는 과정을 변수 i의 값을 0, 1, …로 증가하는(increment)
방법을 통해 간단히 나타내면 다음과 같습니다.

1. 왼쪽 요소의 인덱스(그림의 ● 안의 값) … i n이 7이면 0 ⇨ 1 ⇨ 2
2. 오른쪽 요소의 인덱스(그림의 ● 안의 값) … n - i – 1 n이 7이면 6 ⇨ 5 ⇨ 4

그러므로 요소 개수가 n인 배열 요소를 역순으로 정렬하는 알고리즘을 간단히 나타내면 다음

과 같습니다.

for(i = 0; i < n / 2; i++)
//a[i]와 a[n - i - 1]의 값을 교환

64 C 알고리즘