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

Q7 요소의 교환 과정을 자세하게 출력할 수 있도록 단순 선 +
연습 *
문제 택 정렬 프로그램을 수정하세요. 오른쪽처럼 정렬하지 않은 부 6 4 8 3 1 9 7
* +
분의 첫 번째 요소 위에는 기호 *를, 정렬하지 않은 부분의 가 1 4 8 3 6 9 7
장 작은 값의 요소 위에는 기호 +를 출력하세요. * +
1 3 8 4 6 9 7
이 문제는 6-4절의 ‘단순 선택 정렬’ 프로그램을 개선하는 연습문
…이하 생략…
제입니다.

Q8 요소의 삽입 과정을 자세하게 출력할 수 있도록 단순
6 4 8 5 2 9 7
삽입 정렬 프로그램을 수정하세요. 오른쪽처럼 현재 선택한 ^-----+
요소 아래에 기호 +, 삽입하는 위치의 요소 아래에 기호 ^, 그 4 6 8 5 2 9 7
+
사이에 기호 –를 출력하세요. 삽입하지 않는(요소의 이동이 필 4 6 8 5 2 9 7
^---------+
요 없는) 경우에는 선택한 요소 아래에 +만 출력하면 됩니다.
4 5 6 8 2 9 7
^-----------------+
…이하 생략…

Q9 단순 삽입 정렬에서 배열의 첫 번째 요소(a[0])부터 데이터를 저장하지 않고 a[1]부터 데
이터를 저장하면 a[0]을 보초로 하여 삽입을 마치는 조건을 줄일 수 있습니다. 이 아이디어를 적
용한 단순 삽입 정렬 함수를 수정하세요.

Q10 단순 삽입 정렬은 배열의 요소 개수가 많아지면 많아질수록 요소 삽입에 필요한 비교, 대
입 비용이 무시할 수 없을 정도로 커집니다. 이때 배열에서 이미 정렬된 부분은 이진 검색을 사용
할 수 있기 때문에 삽입할 위치를 더 빨리 찾을 수 있습니다. 이진 검색을 사용하여 프로그램을 수
정하세요.
이 정렬법은 이진 삽입 정렬(binary insertion sort)이라는 알고리즘입니다(안정적이지는 않습니다).

Q11 Q10의 알고리즘은 삽입할 위치의 검색은 빠르지만 삽입을 위해 요소를 하나씩 뒤쪽으로
미는 작업 비용이 단순 삽입 정렬 알고리즘과 같습니다. 요소를 뒤쪽으로 미는 작업을 표준 라이
브러리의 memmove 함수를 사용해서 구현하면 비용을 줄여 좀 더 빠른 속도를 얻을 수 있습니
다. 이 아이디어를 바탕으로 이진 삽입 정렬 함수를 수정하세요.

216 C 알고리즘